Week 3 Sets Foundations, Operations, Power Sets, Products

Sources covered

Lecture 6 (Monday: naive set theory, Russell’s paradox, the formal set concept, equality, subsets, empty set, construction of $\mathbb{N}$) and Lecture 7 (Wednesday: element vs. subset revisited, transitivity of $\subseteq$, ordered pairs and lists, big unions/intersections, difference, Theorem 3.4, power set, Cartesian product). Script: §3.1 and §3.2 complete. Script-only material is marked (script only); reconstructions or additions of mine are marked (added). Next week: §3.3 Relations.

---

1. Executive Overview & Core Objectives

Chapter 3 rebuilds set theory (Mengenlehre) from the ground up. The motivation is Russell’s paradox: naive set theory, where any predicate defines a set, lets you derive a contradiction and therefore everything. The fix is to regulate which sets exist and how new sets are built from old ones. Formally, everything starts from a universe of sets and the elementhood predicate $\in$. Everything is a set, including the natural numbers.

On top of this foundation the lecture defines and proves:

• equality ($=$, via the same elements) and subset ($\subseteq$);
• the empty set (existence postulated, uniqueness proved);
• union, intersection, difference, and the laws of Theorem 3.4 (mirroring Lemma 2.1);
• ordered pairs and lists, built from sets;
• the power set and the Cartesian product.

The single most tested distinction is $\in$ (element of) vs. $\subseteq$ (subset of).

Learning objectives. After this week you should be able to:

• explain Russell’s paradox and why $\{x\mid P(x)\}$ is not always a set, while $\{x\in B\mid P(x)\}$ is;
• state Definitions 3.2–3.8 precisely as predicate-logic formulas;
• prove set equalities and inclusions by unfolding definitions and applying Lemma 2.1 and predicate-logic rules (Lemmas 3.1–3.3, 3.5, 3.6, Theorem 3.4);
• decide $\in$, $\subseteq$, $=$ between sets built from $\varnothing$ without confusing them;
• encode ordered pairs as sets (Kuratowski) and explain why $\{a,\{b\}\}$ fails;
• compute power sets (including of $\varnothing$, $\{\varnothing \}$) and Cartesian products (including with $\varnothing$);
• construct $0,1,2,\dots$ from $\varnothing$, apply the successor $s(n)=n\cup \{n\}$ and the recursive addition.

---

2. Core Concepts & Formal Definitions

2.1 Naive set theory and Russell’s paradox (Script §3.1; Lecture 6)

Cantor (1895): “Unter einer ‘Menge’ verstehen wir jede Zusammenfassung $M$ von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens (welche die ‘Elemente’ von $M$ genannt werden) zu einem Ganzen.”

Notation conventions:

• Lower-case letters for elements, upper-case for sets. The lecturer warned this blurs, since elements are sets too.
• $x\in A$: $x$ is an element of $A$. $x\notin A$ is short for $\neg (x\in A)$.
• $A\subseteq B$: $A$ is a subset of $B$.
• $\varnothing$: the empty set. Some write $\{\}$; the course uses $\varnothing$, which is more readable once $\varnothing$ itself appears as an element.
• $|A|$, cardinality (Kardinalität, Def. 3.1, informal): the number of elements of a finite set $A$.

Sets can be elements of sets. $B=\{A,4,5\}$ with $A=\{1,2,3\}$ has $A\in B$ but $A⊈B$, because $1\notin B$.

Sets that seem to contain themselves. The lecture used the set of all sets $M$ with $|M|>5$; the script uses $\ge 10$ elements. This set has more than 5 elements, so it seems to be an element of itself. The “set of all sets” would contain itself too. Around 1900 such constructions were accepted.

Russell's paradox (1903)

Let $R=\{A\mid A\notin A\}$ be the set of all sets that are not elements of themselves. Then exactly one of $R\in R$ or $R\notin R$ holds.

• If $R\in R$: $R$ satisfies the defining predicate, so $R\notin R$. Contradiction.
• If $R\notin R$: $R$ satisfies the predicate $A\notin A$, so $R\in R$. Contradiction.

Hence $R\in R⟺R\notin R$: naive set theory derives a false statement, and from a false statement anything follows. Frege, who had built his life’s work on formalizing mathematics on this basis, was devastated.

Diagnosis and fix

The false assumption of naive set theory is that every precise predicate $P$ defines a set $\{x\mid P(x)\}$.

• For a given set $B$, $\{x\in B\mid P(x)\}$ is a well-defined set: we select elements from an existing set.
• $\{x\mid P(x)\}$ over “everything” is not. The universe $U$ of all sets is not itself a set.

Fix (Zermelo, later Zermelo–Fraenkel (ZF) set theory): regulate the existence and construction of sets by axioms. Start from sets known to exist ($\varnothing$) and allow only specific construction steps. The resulting theory is believed to be free of contradictions, as the lecture put it. Footnote 4: the ZF axioms even exclude any set being an element of itself, so the “sets containing themselves” above do not exist in ZF.

The course does not do axiomatic set theory formally. It states the relevant axioms informally as definitions or postulates and flags where an axiom is hiding.

Intuition: what the students found (Lecture 6)

Students proposed that self-reference is the problem, or that no universe had been fixed, or that only elements already in some other set should be allowed. The lecturer said the last two together come close. The issue is not that "$M\notin M$" is an evil predicate; a predicate that is always false is harmless, since it just defines an empty set. The issue is forming a set from all objects satisfying a predicate without starting from a given set.

2.2 The formal set concept (Script §3.2.1)

Postulate: universe and elementhood predicate

There is a universe $U$ of sets and a binary predicate $E$, the elementhood predicate; $E(x,y)=1$ means ”$x$ is an element of $y$”, written $x\in y$ (infix).

• Everything is a set: elements of sets are sets as well. There is only one “data type”. Numbers, graphs, finite fields and so on will all be encoded as sets.
• $U$ is not known in advance. The postulates say step by step which sets exist.
• Under this fixed interpretation (universe of sets, $\in$), predicate-logic formulas are statements. That is why it is legitimate to write $\equiv$ and $⟺$ between them in set-theory proofs (Lecture 6 Q&A, recalling §2.5).

The arrow diagram (Lecture 6, reconstructed from the transcript)

Sets $A,\dots ,G$, where an arrow $x\to y$ means $x\in y$:
$E\in D,D\in A,A\in F,C\in B,D\in B.$
No arrows touch $G$. Treat the listed facts as the complete picture. Then:

• $D\in A$ but $A\notin D$; $\in$ is not symmetric.
• $A\subseteq B$: the only element of $A$ is $D$, and $D\in B$.
• $D⊈F$: $E\in D$ but $E\notin F$.
• $F⊈B$: $A\in F$ but $A\notin B$.
• $E\subseteq G$ and $G\subseteq E$ hold vacuously: neither has any element. So $E=G$, and both are $\varnothing$.
• The diagram is inconsistent here. $E\in D$ but $G\notin D$, although $E=G$. The same goes for $C$, which also has no elements (a student pointed this out). The lecturer crossed out $G$ and said the picture had reached its limits. Lesson: two sets with no elements are the same set (Lemma 3.5).

2.3 Equality, finite sets, subsets (Script §3.2.2–3.2.3)

Definition 3.2 (Set equality; axiom of extensionality)

$A=B\stackrel{\text{def}}{⟺}\forall x(x\in A\leftrightarrow x\in B).$
A set is completely determined by its elements, regardless of how it is described. In axiomatic set theory this is the axiom of extensionality (Extensionalitätsaxiom).

Postulate: finite sets exist

If $a$ is a set, then the set containing exactly $a$ exists, denoted $\{a\}$:
$\forall y(y\in \{a\}\leftrightarrow y=a).$
Analogously, for every finite list of sets $x_1,\dots ,x_n$ the set $\{x_1,\dots ,x_n\}$ exists (Script p. 42, right after Def. 3.2).

Consequences of Definition 3.2, since only membership counts:

• $\{a,a\}=\{a\}$: listing an element twice changes nothing.
• $\{a,b\}=\{b,a\}$: there is no order.
• $\{1,2,3\}=\{3,1,2\}=\{1,1+1,1+1+1\}$ (script footnote 6).

Definition 3.3 (Subset)

$A\subseteq B\stackrel{\text{def}}{⟺}\forall x(x\in A\to x\in B).$
Subset (Teilmenge = Untermenge; the two German words are synonyms). Every set is a subset of itself, since equality is allowed. $A⊈B$ means $\neg (A\subseteq B)$: some element of $A$ is not in $B$.

Exam Trap: $\in$ vs. $\subseteq$ (the lecturer's top exam warning)

• $x\in A$: the object $x$ itself appears as one element in $A$.
• $A\subseteq B$: every element of $A$ is an element of $B$.

They are logically independent. One can hold without the other, both can hold, or neither. Examples:

• $\{1\}\subseteq \{1,2\}$, but $\{1\}\notin \{1,2\}$.
• $\{1\}\in \{\{1\},2\}$, but $\{1\}⊈\{\{1\},2\}$, because $1\notin \{\{1\},2\}$.
• $\varnothing \in \{\varnothing \}$ and $\varnothing \subseteq \{\varnothing \}$.

The lecturer apologized for having said “enthalten” (contained) for $\subseteq$ in Lecture 6. Avoid the word for sets; say “element of” or “subset of”.

2.4 Union, intersection, difference (Script §3.2.4)

Definition 3.4 (Union, intersection)

$A\cup B\stackrel{\text{def}}{=}\{x\mid x\in A\vee x\in B\},A\cap B\stackrel{\text{def}}{=}\{x\mid x\in A\wedge x\in B\}.$
Union (Vereinigung) and intersection (Schnitt, Durchschnitt). Implicit axiom: these sets exist. This is not automatic for $\{x\mid \dots \}$ (Russell). Here it is guaranteed by axioms one level down.

Big union and intersection (Script §3.2.4)

Let $\mathcal{A}$ be a non-empty set of sets (finite or infinite). Then
$\bigcup \mathcal{A}\stackrel{\text{def}}{=}\{x\mid x\in A\text{ for some }A\in \mathcal{A}\},\bigcap \mathcal{A}\stackrel{\text{def}}{=}\{x\mid x\in A\text{ for all }A\in \mathcal{A}\}.$
Indexed version: $\mathcal{A}=\{A_i\mid i\in I\}$, written ${\bigcup }_{i\in I}{A}_i$ and ${\bigcap }_{i\in I}{A}_i$.

Why must $\mathcal{A}$ be non-empty (added)? $\bigcap \varnothing$ would be $\{x\mid \text{true}\}$, the “set of everything”, which is exactly the kind of non-set that Russell’s paradox rules out. The lecture did not mention this restriction.

Example 3.2

$\mathcal{A}=\{\{a,b,c,d\},\{a,c,e\},\{a,b,c,f\},\{a,c,d\}\}$:
$\bigcup \mathcal{A}=\{a,b,c,d,e,f\},\bigcap \mathcal{A}=\{a,c\}.$
$a$ and $c$ are the only letters appearing in every member.

Definition 3.5 (Difference)

$B\setminus A\stackrel{\text{def}}{=}\{x\in B\mid x\notin A\},$
i.e. all $x$ with $x\in B\wedge x\notin A$. This is the difference (Differenz), read ”$B$ without $A$”. This form selects from an existing set $B$, the safe form from §2.1.

Membership translations (Lecture 7, closing remarks). These are what you plug in when proving set identities:

Membership	Equivalent formula
$x\in A\cap B$	$x\in A\wedge x\in B$
$x\in A\cup B$	$x\in A\vee x\in B$
$x\in B\setminus A$	$x\in B\wedge x\notin A$
$x\in \mathcal{P}(A)$	$x\subseteq A$
$x\in \bigcup \mathcal{A}$	$\exists A(A\in \mathcal{A}\wedge x\in A)$
$x\in \bigcap \mathcal{A}$	$\forall A(A\in \mathcal{A}\to x\in A)$

2.5 The empty set (Script §3.2.5)

Definition 3.6 (Empty set)

A set $A$ is empty if it has no elements: $\forall x\neg (x\in A)$.
Axiom (implicit in the script, footnote 10): an empty set exists. It is the initial “spark”. Without it the universe could be empty: the postulates ”$\{a\}$ exists if $a$ exists” only produce new sets from existing ones.

Lemma 3.5

There is only one empty set, denoted $\varnothing$ (or $\{\}$).

Lemma 3.6

The empty set is a subset of every set: $\forall A(\varnothing \subseteq A)$.

(Proofs in §3.4.)

Exam Trap

• $\varnothing \subseteq A$ holds for every $A$. But $\varnothing \in A$ holds only if $\varnothing$ is listed among the elements of $A$, e.g. $\varnothing \notin \{1,2\}$.
• $\{\varnothing \}\ne \varnothing$: $|\{\varnothing \}|=1$ but $|\varnothing |=0$. A box containing an empty box is not an empty box.

2.6 Constructing sets and the natural numbers (Script §3.2.6–3.2.7)

From $\varnothing$ alone we get $\varnothing ,\{\varnothing \},\{\{\varnothing \}\},\{\{\{\varnothing \}\}\},\dots$. All except $\varnothing$ have cardinality 1, and they are pairwise distinct.

Example 3.3 (script only):

• $A=\{\varnothing ,\{\varnothing \}\}$ has $|A|=2$.
• $B=\{\{\varnothing ,\{\varnothing \}\}\}$ has $|B|=1$.
• $C=\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}$ has $|C|=3$.
• $A\subseteq C$ and $B\subseteq C$.

Natural numbers from sets (von Neumann construction)

Define the bold-face sets
$0\stackrel{\text{def}}{=}\varnothing ,1\stackrel{\text{def}}{=}\{\varnothing \},2\stackrel{\text{def}}{=}\{\varnothing ,\{\varnothing \}\},3\stackrel{\text{def}}{=}\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\},\dots$
and the successor (Nachfolger) of a set $\mathbf{n}$:
$s(\mathbf{n})\stackrel{\text{def}}{=}\mathbf{n}\cup \{\mathbf{n}\}.$
So $1=s(0)$, $2=s(1)$, and in general $\mathbf{n}=\{0,1,\dots ,\mathbf{n}-1\}$. Hence $|\mathbf{n}|=n$ and $|s(\mathbf{n})|=|\mathbf{n}|+1$, because $\mathbf{n}\notin \mathbf{n}$, so exactly one new element is added.

Addition, defined recursively:
$\mathbf{m}+0\stackrel{\text{def}}{=}\mathbf{m},\mathbf{m}+s(\mathbf{n})\stackrel{\text{def}}{=}s(\mathbf{m}+\mathbf{n}).$
Multiplication can be defined similarly. One can prove the usual commutative, associative and distributive laws.

Recursive, not circular (Lecture 7 addendum)

A student objected that ”$+$ is defined using $+$”. The definition is recursive: $\mathbf{m}+s(\mathbf{n})$ is reduced to $\mathbf{m}+\mathbf{n}$, whose second argument is one smaller. After finitely many steps the base case $\mathbf{m}+0=\mathbf{m}$ is reached, so every sum is determined. Compare the forbidden “ancestor” definition (Week 2). That one had no decreasing measure and no base case at the formula level. Here the recursion is over $\mathbf{n}$ and terminates.

Source note (Lectures 6 and 7)

• In the Lecture 7 recap the rule was stated as "$s(\mathbf{n})+\mathbf{m}$". The definition from Lecture 6 and the script is $\mathbf{m}+s(\mathbf{n})=s(\mathbf{m}+\mathbf{n})$.
• The opening example $\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\},\dots \}$ written on the board in Lecture 6 is exactly $\{0,1,2,\dots \}=\mathbb{N}$ in this encoding.
• Q&A: induction (Week 2) can be justified via this definition of $\mathbb{N}$. Integers could be built with a sign-flipping operation (the lecturer’s informal answer); rationals come later.

2.7 Ordered pairs and lists (Script §3.2.2, Example 3.1; Lecture 7)

Sets are unordered ($\{a,b\}=\{b,a\}$), but we need ordered pairs $(a,b)$ with $(a,b)\ne (b,a)$ for $a\ne b$.

Ordered pair (characteristic property)

$(a,b)=(c,d)\stackrel{\text{def}}{⟺}a=c\wedge b=d.$
The script takes this as the definition and treats lists conventionally (footnote 8). The lecture instead constructs pairs from sets and treats the property as a theorem.

Kuratowski pair (Example 3.1; the definition used in the lecture)

$(a,b)\stackrel{\text{def}}{=}\{\{a\},\{a,b\}\}.$
The first component is the element of the singleton; the second is the remaining element of the two-element set, or the same element again if $a=b$.

Candidate encodings:

Encoding	Works?	Reason
$\{a,b\}$	no	$\{a,b\}=\{b,a\}$
$\{a,\{b\}\}$	no	$\{\{b\},\{c\}\}$ is both $(\{b\},c)$ and $(\{c\},b)$
$\{\{0,a\},\{1,b\}\}$ (student)	yes, as far as checked	the lecturer agreed after thinking it through
$\{\{a\},\{a,b\}\}$ (Kuratowski)	yes	proof in §3.6

In the lecture, nobody found the collision for $\{a,\{b\}\}$; the script gives it (row 2). (added) I checked by computer on all $256$ pairs of sets of rank $\le 3$. $\{a,\{b\}\}$ produces collisions; the student’s tagged encoding and Kuratowski’s are injective on these pairs. That is evidence, not a proof, for the student’s encoding.

Longer lists (lecture): recursively,

$(a_1,a_2,a_3)\stackrel{\text{def}}{=}((a_1,a_2),a_3),$

and in general $(a_1,\dots ,a_k)$ is equal to $(b_1,\dots ,b_k)$ iff $a_i=b_i$ for all $i$. The script defines $k$-lists directly by this property.

Source note: associativity of $\times$

With the lecture’s encoding $(a_1,a_2,a_3)=((a_1,a_2),a_3)$, the triple product ${\times }_{i=1}^3{A}_i$ coincides with $(A_1\times A_2)\times A_3$. The script (§3.2.9) treats $k$-tuples as their own objects and states ${\times }_{i=1}^3{A}_i\ne (A_1\times A_2)\times A_3$ (“the Cartesian product is not associative”). Both agree that in general $(A_1\times A_2)\times A_3\ne A_1\times (A_2\times A_3)$ (see Question 5). For the exam, follow the script’s convention unless told otherwise.

2.8 Power set and Cartesian product (Script §3.2.8–3.2.9)

Definition 3.7 (Power set)

The power set (Potenzmenge) of $A$ is the set of all subsets of $A$:
$\mathcal{P}(A)\stackrel{\text{def}}{=}\{S\mid S\subseteq A\}.$
For $|A|=k$ finite: $|\mathcal{P}(A)|=2^k$. Hence the alternative notation $2^A$; English: power set.
Axiom: the existence of $\mathcal{P}(A)$ must be postulated (footnote 11).

The lecturer mentioned finitists and ultrafinitists: mathematicians, many of them serious, who reject such axioms or very large objects altogether. This course accepts power sets of power sets without hesitation.

Definition 3.8 (Cartesian product)

$A\times B\stackrel{\text{def}}{=}\{(a,b)\mid a\in A\wedge b\in B\},$
and for $k$ sets the $k$-fold product
${\times }_{i=1}^k{A}_i\stackrel{\text{def}}{=}\{(a_1,\dots ,a_k)\mid a_i\in A_i\text{ for }1\le i\le k\}.$
Cartesian product (kartesisches Produkt). For finite sets $|A\times B|=|A|\cdot |B|$.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Lemma 3.1: $\{a\}=\{b\}⟹a=b$ (Lecture 6)

Lemma 3.1

For any sets $a$ and $b$: $\{a\}=\{b\}⟹a=b$.

Proof (indirect, Def. 2.14; a student’s idea in the lecture). Fix $a,b$ and assume $a\ne b$. Show $\{a\}\ne \{b\}$:

1. $a\in \{a\}$ by the postulate defining $\{a\}$.
2. $a\in \{b\}$ would mean $a=b$ (the only element of $\{b\}$ is $b$), contradicting the assumption. So $a\notin \{b\}$.
3. So $x=a$ violates $\forall x(x\in \{a\}\leftrightarrow x\in \{b\})$. By Def. 3.2, $\{a\}\ne \{b\}$.

We have shown $a\ne b⟹\{a\}\ne \{b\}$, which by contraposition (Lemma 2.6) gives the claim. $\square$

Equality (Def. 3.2) was used twice: once for the sets, once for comparing $a$ with $b$.

Exam Trap

$\{a,b\}=\{c,d\}$ implies neither $a=c$ nor $b=d$. For example $\{1,2\}=\{2,1\}$, where $a=1\ne 2=c$. Only singletons behave like Lemma 3.1.

3.2 Lemma 3.2: equality via mutual inclusion (Lecture 6)

Lemma 3.2

$A=B⟺(A\subseteq B)\wedge (B\subseteq A).$
In practice this is the standard way to prove two sets equal: show "$\subseteq$" in both directions.

Proof (all steps are equivalences between statements about fixed sets $A$, $B$).

$$\begin{array}{rlrl}(A\subseteq B)\wedge (B\subseteq A)& \stackrel{\cdot }{⟺}\forall x(x\in A\to x\in B)\wedge \forall x(x\in B\to x\in A)& & \text{(Def. 3.3, twice)}\\ & \stackrel{\cdot }{⟺}\forall x((x\in A\to x\in B)\wedge (x\in B\to x\in A))& & (\forall xF\wedge \forall xG\equiv \forall x(F\wedge G))\\ & \stackrel{\cdot }{⟺}\forall x(x\in A\leftrightarrow x\in B)& & ((C\to D)\wedge (D\to C)\equiv C\leftrightarrow D)\\ & \stackrel{\cdot }{⟺}A=B& & \text{(Def. 3.2)}\end{array}$$

Why each step:

• Step 1 unfolds definitions. Always the first move.
• Step 2 is needed because the two conditions sit under separate quantifiers, and we want them combined into one, since the target definition has a single $\forall x$. The predicate-logic law from Week 2 does exactly that.
• Step 3 recognizes the body as a biconditional, provable with a 4-row truth table. The script renames the symbols to $C,D$ to avoid clashing with the sets $A,B$.
• Step 4 folds the definition back up.

All steps are equivalences, so both directions are proved. $\square$

3.3 Lemma 3.3: transitivity of $\subseteq$ (Lecture 7)

Lemma 3.3

For any sets $A,B,C$: $A\subseteq B\wedge B\subseteq C⟹A\subseteq C$.

Proof (direct).

$$\begin{array}{rlrl}A\subseteq B\wedge B\subseteq C& \stackrel{\cdot }{⟺}\forall x(x\in A\to x\in B)\wedge \forall x(x\in B\to x\in C)& & \text{(Def. 3.3, twice)}\\ & \stackrel{\cdot }{⟺}\forall x((x\in A\to x\in B)\wedge (x\in B\to x\in C))& & (\forall F\wedge \forall G\equiv \forall (F\wedge G))\\ & \stackrel{\cdot }{⟹}\forall x(x\in A\to x\in C)& & ((F\to G)\wedge (G\to H)\models F\to H)\\ & \stackrel{\cdot }{⟺}A\subseteq C& & \text{(Def. 3.3)}\end{array}$$

Step 3 uses Lemma 2.5 (Week 2) inside the $\forall x$ with $F=(x\in A)$, $G=(x\in B)$, $H=(x\in C)$. If the body implies the new body for each $x$, then “for all $x$ body” implies “for all $x$ new body”. $\square$

Q&A (Lecture 7)

• “Does step 3 need to be an equivalence?” No. A consequence is enough, since we only argue left to right. It is genuinely one-way: from $\forall x(x\in A\to x\in C)$ you cannot recover the intermediate $B$.
• “Aren’t steps 1, 2 and 4 equivalences?” Yes, and one may write $\stackrel{\cdot }{⟺}$ there. For proving an implication, $\stackrel{\cdot }{⟹}$ everywhere is sufficient.

3.4 Lemmas 3.5 and 3.6: uniqueness of $\varnothing$, and $\varnothing \subseteq A$

Lemma 3.5 (uniqueness). Let $\varnothing$ and ${\varnothing }^{\prime }$ both be empty. “Every $x\in \varnothing$ is in ${\varnothing }^{\prime }$” holds vacuously, since there is no such $x$, and vice versa. So $\forall x(x\in \varnothing \leftrightarrow x\in {\varnothing }^{\prime })$: both sides are always false, and $0\leftrightarrow 0=1$. By Def. 3.2, $\varnothing ={\varnothing }^{\prime }$. $\square$ A student asked this (“are all empty sets the same?”) right before the lecturer wrote it down.

Lemma 3.6, short proof (lecture). $\varnothing \subseteq A$ means $\forall x(x\in \varnothing \to x\in A)$. For every $x$ the premise $x\in \varnothing$ is false, so the implication is true (vacuous truth). $\square$

Lemma 3.6, proof by contradiction (script). Suppose some $A$ has $\varnothing ⊈A$. Then some $x$ has $x\in \varnothing$ and $x\notin A$, but no $x$ is in $\varnothing$. Contradiction. $\square$

Lemma 3.6, fully formal (script). Contradiction pattern (Def. 2.17) with $S$: $\varnothing \subseteq A$ and $T$: $\neg \forall x(x\notin \varnothing )$, which is false because it negates Def. 3.6.

$$\begin{array}{rlrl}\neg (\varnothing \subseteq A)& \stackrel{\cdot }{⟺}\neg \forall x(x\in \varnothing \to x\in A)& & \text{(def. of }\subseteq )\\ & \stackrel{\cdot }{⟺}\exists x\neg (x\in \varnothing \to x\in A)& & (\neg \forall xF\equiv \exists x\neg F)\\ & \stackrel{\cdot }{⟺}\exists x\neg (\neg (x\in \varnothing )\vee x\in A)& & \text{(def. of }\to )\\ & \stackrel{\cdot }{⟺}\exists x(x\in \varnothing \wedge \neg (x\in A))& & \text{(de Morgan, double negation)}\\ & \stackrel{\cdot }{⟹}\exists x(x\in \varnothing )\wedge \exists x\neg (x\in A)& & (\exists x(F\wedge G)\models \exists xF\wedge \exists xG)\\ & \stackrel{\cdot }{⟹}\exists x(x\in \varnothing )& & (F\wedge G\models F)\\ & \stackrel{\cdot }{⟺}\neg \forall x\neg (x\in \varnothing )& & (\neg \forall xF\equiv \exists x\neg F)\\ & \stackrel{\cdot }{⟺}\varnothing \text{ is not empty}& & \text{(Def. 3.6)}\end{array}$$

That is false, a contradiction. $\square$

Intuition

“Every element of $\varnothing$ is in $A$” is like “every unicorn in this room is purple”: true, because there is nothing to check. A universal claim over nothing is always true.

3.5 Theorem 3.4: laws for $\cap$, $\cup$, and the distributivity proof (Lecture 7)

Theorem 3.4

For all sets $A,B,C$:

• Idempotence: $A\cap A=A$, $A\cup A=A$
• Commutativity: $A\cap B=B\cap A$, $A\cup B=B\cup A$
• Associativity: $A\cap (B\cap C)=(A\cap B)\cap C$, $A\cup (B\cup C)=(A\cup B)\cup C$
• Absorption: $A\cap (A\cup B)=A$, $A\cup (A\cap B)=A$
• Distributivity: $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$, $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
• Consistency (script only): $A\subseteq B⟺A\cap B=A⟺A\cup B=B$

All equalities are set equalities (Def. 3.2). This is the set-theoretic twin of Lemma 2.1: $\cap$ is $\wedge$, $\cup$ is $\vee$, $=$ is $\equiv$.

Source note (Lecture 7)

When reading out the second distributive law, the lecturer said ”$A$ union $B$ intersect $C$ equals $A$ intersect $B$ union $A$ intersect $C$”. That is garbled; a student also pointed out a slip on the board. Correct: $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$.

Proof of the first distributive law (the starred law in the lecture):

$$\begin{array}{rlrl}A\cap (B\cup C)& =\{x\mid x\in A\wedge x\in B\cup C\}& & \text{(def. of }\cap )\\ & =\{x\mid x\in A\wedge x\in \{y\mid y\in B\vee y\in C\}\}& & \text{(def. of }\cup )\\ & =\{x\mid x\in A\wedge (x\in B\vee x\in C)\}& & (x\in \{y\mid P(y)\}⟺P(x))\\ & =\{x\mid (x\in A\wedge x\in B)\vee (x\in A\wedge x\in C)\}& & \text{(Lemma 2.1, 5)}\\ & =\{x\mid x\in A\cap B\vee x\in A\cap C\}& & \text{(def. of }\{\cdot \mid \cdot \}\text{, def. of }\cap \text{ twice)}\\ & =(A\cap B)\cup (A\cap C)& & \text{(def. of }\cup )\end{array}$$

The recipe for any such identity: unfold the set operations into membership formulas → apply a law of logic (Lemma 2.1) → fold back up. In step 4, Lemma 2.1(5) is applied with $A:=(x\in A)$, $B:=(x\in B)$, $C:=(x\in C)$, which is allowed by lifting (Week 1). $\square$

The script says the other laws follow the same way: associativity of $\cap ,\cup$ from that of $\wedge ,\vee$, and so on (left as an exercise). The consistency law is proved in Question 2.

3.6 Correctness of the Kuratowski pair (added; the script leaves it as an exercise, the lecturer stated it without proof)

Claim. $\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}⟹a=c\wedge b=d$.

Proof

Let $p=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$.
Case $a=b$. Then $\{a,b\}=\{a\}$, so $p=\{\{a\}\}$ has exactly one element. Hence $\{c\}=\{a\}$ and $\{c,d\}=\{a\}$. The first gives $c=a$ (Lemma 3.1); the second gives $d\in \{a\}$, so $d=a$. Thus $a=c$ and $b=a=d$.
Case $a\ne b$. Then $\{a\}\ne \{a,b\}$ (the latter has two elements), so $p$ has two elements: one with 1 element, one with 2. The same must hold for the right-hand description, so $c\ne d$ (otherwise $p$ would have one element).

• Matching the one-element members: $\{a\}=\{c\}$, so $a=c$ by Lemma 3.1.
• Matching the two-element members: $\{a,b\}=\{c,d\}=\{a,d\}$. Since $b\in \{a,d\}$ and $b\ne a$, we get $b=d$. $\square$

Why $\{a,\{b\}\}$ fails: $(\{b\},c)\mapsto \{\{b\},\{c\}\}$ and $(\{c\},b)\mapsto \{\{c\},\{b\}\}$ are the same set although the pairs differ (for $b\ne c$).

3.7 Power-set facts and $|\mathcal{P}(A)|=2^k$

Why $2^k$ (sketch, added). A subset $S\subseteq A=\{a_1,\dots ,a_k\}$ is determined by $k$ independent yes/no decisions ”$a_i\in S$?”. So there are $2^k$ subsets, i.e. bit strings in $\{0,1{\}}^k$. Induction on $k$ makes this rigorous: adding an element $a_{k+1}$ doubles the count, because each old subset $S$ yields $S$ and $S\cup \{a_{k+1}\}$.

Lemma (added): $A\cap \mathcal{P}(A)\ne \varnothing$ $⟺$ some element of $A$ is also a subset of $A$, since $x\in \mathcal{P}(A)⟺x\subseteq A$. Hence any $A$ with $\varnothing \in A$ works, because $\varnothing \subseteq A$ always.

---

4. Worked Examples & Applications

4.1 $\in$ and $\subseteq$ with symbols (Lecture 7, reconstructed)

The board used smiley and frowny faces. Write $s$ for the smiley and $f$ for the frowny. The sets are reconstructed so that every relation the lecture verified holds:

$A=\{s,f,\{s\}\},B=\{s,f,\{f\}\},C=\{s\}.$

Claim	True?	Reason
$C\subseteq A$	yes	the only element of $C$, $s$, is in $A$
$C\in A$	yes	the set $\{s\}$ itself is listed in $A$
$C\subseteq B$	yes	$s\in B$
$C\in B$	no	$\{s\}$ is not among $s,f,\{f\}$
$A\subseteq B$	no	$\{s\}\in A$ but $\{s\}\notin B$ (the inner set is the culprit, not $s$)
$B\subseteq A$	no	$\{f\}\in B$ but $\{f\}\notin A$
$A\cap B$	$=\{s,f\}$	only the bare symbols are in both
$A\cup B$	$=\{s,f,\{s\},\{f\}\}$	collect everything
$C\in A\cup B$	yes	$\{s\}$ is an element of $A$
$C\in A\cap B$	no	$\{s\}\notin B$

The reasons for $C\subseteq A$ and $C\in A$ are different. One is the bare $s$; the other is the boxed $\{s\}$.

Parsing (Q&A). $C\notin A\cap B$ needs no parentheses. The reading "$(C\notin A)\cap B$" is ill-typed, because $C\notin A$ is a statement and you cannot intersect a statement with a set. Adding $C\notin (A\cap B)$ for clarity is never wrong.

4.2 Example 3.4 (Lecture 6; Script)

$A=\{\{\varnothing \}\},B=\{\{\varnothing \},\{\varnothing ,\varnothing \}\},C=\{\varnothing ,\{\varnothing \}\},D=\{\varnothing ,\{\varnothing ,\{\varnothing \}\}\}.$

Answer: $B=A\subseteq C\in D$.

• $B=A$: $\{\varnothing ,\varnothing \}=\{\varnothing \}$ (repetition doesn’t count), so $B=\{\{\varnothing \},\{\varnothing \}\}=\{\{\varnothing \}\}=A$.
• $A\subseteq C$: the only element of $A$, namely $\{\varnothing \}$, is an element of $C$. But $A\notin C$: the elements of $C$ are $\varnothing$ and $\{\varnothing \}$, and neither equals $\{\{\varnothing \}\}$.
• $C\in D$: the second element of $D$ is $\{\varnothing ,\{\varnothing \}\}=C$.
• $C⊈D$ (student question): $\{\varnothing \}\in C$, but $\{\varnothing \}\notin D$, whose elements are $\varnothing$ and $C$.

“Can we be sure we found all relations?” Only by checking every ordered pair. There is no shortcut such as ”$C\in D$ excludes $C\subseteq D$”. Counterexample: $\varnothing \in \{\varnothing \}$ and $\varnothing \subseteq \{\varnothing \}$.

4.3 Power sets (Lecture 7; Script Examples 3.5, 3.6)

$A$	$\mathcal{P}(A)$	size
$\varnothing$	$\{\varnothing \}$	$1=2^0$
$\{\varnothing \}$	$\{\varnothing ,\{\varnothing \}\}$	$2=2^1$
$\{\varnothing ,\{\varnothing \}\}$	$\{\varnothing ,\{\varnothing \},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}\}$	$4=2^2$
$\{a,b,c\}$	$\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$	$8=2^3$

• $\mathcal{P}(\varnothing )=\{\varnothing \}\ne \varnothing$. In the lecture one student answered $\varnothing$ (wrong) and another $\{\varnothing \}$ (right). $\varnothing$ has exactly one subset, itself.
• $\mathcal{P}(\{\varnothing \})$: one student suggested $\{\varnothing \}$ again (wrong). The subsets of $\{\varnothing \}$ are $\varnothing$ (always a subset) and $\{\varnothing \}$ itself. Power sets always grow.
• Every power set contains $\varnothing$ and $A$ itself. Also $\{1,7,9\}\in \mathcal{P}(\mathbb{N})$.
• In the von Neumann encoding, $\mathcal{P}(0)=1$ and $\mathcal{P}(1)=2$.

Exam task (HS 2022, short-answer part)

Find a set $A$ with $A\cap \mathcal{P}(A)\ne \varnothing$.

• Lecturer’s intended answer: $A=\{\varnothing \}$. Then $\mathcal{P}(A)=\{\varnothing ,\{\varnothing \}\}$ and $A\cap \mathcal{P}(A)=\{\varnothing \}\ne \varnothing$.
• Student’s answer in the lecture: $A=\{b,\{b\}\}$. Then $\mathcal{P}(A)=\{\varnothing ,\{b\},\{\{b\}\},\{b,\{b\}\}\}$, and $\{b\}\in A$ with $\{b\}\subseteq A$, so $A\cap \mathcal{P}(A)\supseteq \{\{b\}\}$. Full marks.
• Non-example: $A=\varnothing$ gives $\varnothing \cap \{\varnothing \}=\varnothing$.
• General principle (§3.7): we need an element of $A$ that is also a subset of $A$.

4.4 Cartesian products (Lecture 7; Script Example 3.7)

• $\{1,2\}\times \{a,b,c\}=\{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}$, with $2\cdot 3=6$ elements.

• (i) $A\times \varnothing =\varnothing =\varnothing \times A$, true. A pair needs a second component from $\varnothing$, and there is none. In the lecture a student answered this immediately.

• (ii) $A\times B=B\times A$, false in general. Counterexample: $A=\{0\}$, $B=\{1\}$. Then $A\times B=\{(0,1)\}\ne \{(1,0)\}=B\times A$, since $(0,1)\ne (1,0)$.

  Equality does hold in the “pathological” cases $A=B$, $A=\varnothing$ or $B=\varnothing$ (lecture Q&A). These are the only cases (added): if both are non-empty and $a\in A\setminus B$, then $(a,b)\in A\times B$ but $(a,b)\notin B\times A$.

4.5 Computing with the von Neumann naturals

$2+1=2+s(0)=s(2+0)=s(2)=2\cup \{2\}=\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}=3.$

• Step 2 uses the recursive rule with $\mathbf{n}=0$.
• Step 3 uses the base rule.
• Step 4 uses the definition of $s$.

---

5. Intuition & Conceptual Bridges

Sets are predicate logic in disguise

Every set operation is a logical operator on membership:

Logic	Sets
$\wedge$, $\vee$, $\neg$	$\cap$, $\cup$, complement / $\setminus$
$\to$ under $\forall x$	$\subseteq$
$\leftrightarrow$ under $\forall x$	$=$
$\equiv$	$=$
$\models$	$\subseteq$
$\perp$, $\top$	$\varnothing$, (the non-set “everything”)

That is why Theorem 3.4 is Lemma 2.1 again, and why every proof this week follows unfold → logic → fold. Venn diagrams are the truth tables of set theory: three circles give the 8 regions of a 3-variable table.

Element vs. subset as boxes

Picture a set as a box. $x\in A$: the box $A$ has the object $x$ lying in it, and $x$ may itself be a closed box. $S\subseteq A$: everything lying in box $S$ also lies in box $A$. $\{\varnothing \}$ is a box containing one empty box. $\varnothing \subseteq A$ always, because an empty box has nothing that could fail to be in $A$.

Why build numbers from $\varnothing$?

To show that one primitive notion (sets and $\in$) suffices for all of mathematics. If numbers, pairs, functions, relations and graphs are all sets, then the consistency of set theory secures everything. The von Neumann choice $\mathbf{n}=\{0,\dots ,\mathbf{n}-1\}$ has nice properties: $|\mathbf{n}|=n$, $m<n⟺\mathbf{m}\in \mathbf{n}$, and $m\le n⟺\mathbf{m}\subseteq \mathbf{n}$.

Connections.

• Backwards:
  • Russell’s paradox is a cousin of the liar (“this statement is false”) and the barber (Week 1). All are self-reference plus negation.
  • The ban on self-referential definitions (ancestor, Week 2) has the same root.
  • Every proof this week uses Week 2 tools: $\forall F\wedge \forall G\equiv \forall (F\wedge G)$, $\neg \forall \equiv \exists \neg$, the indirect proof, the proof by contradiction.
  • Induction on $\mathbb{N}$ (Week 2) is now grounded in a concrete definition of $\mathbb{N}$.
• Forward (next week, §3.3–3.7):
  • A relation is a subset $\rho \subseteq A\times B$. The Cartesian product and the pair encoding are prerequisites.
  • The transitivity of $\subseteq$ (Lemma 3.3) is the first instance of a transitive relation. $\subseteq$ on $\mathcal{P}(A)$ will be the model partial order.
  • Functions are special relations.
  • §3.7 (countability) uses $\mathcal{P}(\mathbb{N})$ and $\{0,1{\}}^{\infty }$ to show that some infinite sets are strictly larger than others (Cantor’s diagonal argument). That is the precise version of ”$\mathbb{R}$ cannot be enumerated” from Week 2.

---

6. Summary & Self-Assessment Questions

Cheat sheet

Concept	Definition / fact
Russell	$R=\{A\mid A\notin A\}$ gives $R\in R⟺R\notin R$; fix: axioms regulate set existence
Safe comprehension	$\{x\in B\mid P(x)\}$ is a set; $\{x\mid P(x)\}$ need not be
Everything is a set	universe of sets, predicate $\in$
$A=B$	$\forall x(x\in A\leftrightarrow x\in B)$ (Def. 3.2, extensionality)
$A\subseteq B$	$\forall x(x\in A\to x\in B)$ (Def. 3.3)
Lemma 3.1	$\{a\}=\{b\}\Rightarrow a=b$ (not true for 2-element sets)
Lemma 3.2	$A=B⟺A\subseteq B\wedge B\subseteq A$
Lemma 3.3	$A\subseteq B\wedge B\subseteq C\Rightarrow A\subseteq C$
$\varnothing$	$\forall x\neg (x\in \varnothing )$; exists (axiom), unique (L. 3.5), subset of every set (L. 3.6)
$\cup$, $\cap$	$x\in A\vee x\in B$, $x\in A\wedge x\in B$ (Def. 3.4)
$\bigcup \mathcal{A}$, $\bigcap \mathcal{A}$	in some / every member; $\mathcal{A}$ non-empty
$B\setminus A$	$\{x\in B\mid x\notin A\}$ (Def. 3.5)
Theorem 3.4	idempotence, commutativity, associativity, absorption, distributivity, consistency
Repetition and order	$\{a,a\}=\{a\}$, $\{a,b\}=\{b,a\}$
Pair	$(a,b)=(c,d)⟺a=c\wedge b=d$; Kuratowski $(a,b)=\{\{a\},\{a,b\}\}$
$\mathcal{P}(A)$	$\{S\mid S\subseteq A\}$; $|\mathcal{P}(A)|=2^{|A|}$ (Def. 3.7)
Small power sets	$\mathcal{P}(\varnothing )=\{\varnothing \}$, $\mathcal{P}(\{\varnothing \})=\{\varnothing ,\{\varnothing \}\}$
$A\times B$	$\{(a,b)\mid a\in A\wedge b\in B\}$; size $|A|\cdot |B|$; $A\times \varnothing =\varnothing$ (Def. 3.8)
$A\times B$ vs. $B\times A$	in general $A\times B\ne B\times A$
Naturals	$0=\varnothing$, $s(\mathbf{n})=\mathbf{n}\cup \{\mathbf{n}\}$, $\mathbf{m}+0=\mathbf{m}$, $\mathbf{m}+s(\mathbf{n})=s(\mathbf{m}+\mathbf{n})$
Membership rules	$x\in A\cap B⟺x\in A\wedge x\in B$; $x\in \mathcal{P}(A)⟺x\subseteq A$

Source notes: where lecture and correct version differ

1. L6: the “set of all sets with more than 5 elements” was written with $|A|>5$ inside its own definition; the bound variable should be $M$: $\{M\mid |M|>5\}$. Such self-containing sets do not exist in ZF (footnote 4).
2. L6: the arrow diagram becomes inconsistent: $C$, $E$, $G$ are all empty, so they must be equal. The lecturer crossed out $G$.
3. L6/L7: “enthalten” was used for $\subseteq$; the lecturer retracted it. Say “element of” or “subset of”.
4. L7 recap: addition was stated as $s(\mathbf{n})+\mathbf{m}$. Correct: $\mathbf{m}+s(\mathbf{n})=s(\mathbf{m}+\mathbf{n})$.
5. L7: the second distributive law was misread aloud. Correct: $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$.
6. L7: the lecture encodes triples as $((a_1,a_2),a_3)$, under which ${\times }_{i=1}^3{A}_i=(A_1\times A_2)\times A_3$. The script says they differ, because it treats $k$-tuples as primitive.
7. L7: no collision was found for $\{a,\{b\}\}$ in the lecture; the script’s collision is $\{\{b\},\{c\}\}$.
8. Script only: the big intersection requires $\mathcal{A}\ne \varnothing$; the consistency law belongs to Theorem 3.4.

Self-assessment questions

Question 1. Let $A=\varnothing$, $B=\{\varnothing \}$, $C=\{\{\varnothing \}\}$, $D=\{\varnothing ,\{\varnothing \}\}$. For every ordered pair $(X,Y)$ of distinct sets among $A,B,C,D$, decide whether $X\in Y$ and whether $X\subseteq Y$.

Solution to Question 1

Elements: $A$ has none; $B$ has $\varnothing$; $C$ has $\{\varnothing \}$; $D$ has $\varnothing$ and $\{\varnothing \}$. Note $A=\varnothing =0$, $B=1$, $D=2$.

• $A$: $A\subseteq$ every set (Lemma 3.6). $A\in B$ and $A\in D$ ($\varnothing$ is listed). $A\notin C$ (the only element of $C$ is $\{\varnothing \}\ne \varnothing$).
• $B$: $B\in C$ (the element of $C$ is $\{\varnothing \}=B$) and $B\in D$. $B\subseteq D$ ($\varnothing \in D$). $B⊈C$ ($\varnothing \notin C$). $B⊈A$, $B\notin A$.
• $C$: $C\subseteq D$ (its only element $\{\varnothing \}$ is in $D$). $C\notin D$ ($D$‘s elements are $\varnothing ,\{\varnothing \}$, neither equals $\{\{\varnothing \}\}$). $C⊈B$ ($\{\varnothing \}\notin B$).
• $D$: $D$ is not an element or subset of any of $A,B,C$ (it has 2 elements; $B$ and $C$ have 1, so $D⊈$ them).

Summary: $A\in B$, $A\subseteq B$; $A\in D$, $A\subseteq D$; $A\subseteq C$; $B\in C$; $B\in D$, $B\subseteq D$; $C\subseteq D$. (Checked by computer.) Note that $A\in B$ and $A\subseteq B$ both hold, and so do $B\in D$ and $B\subseteq D$.

Question 2. Prove the consistency law of Theorem 3.4: $A\subseteq B⟺A\cap B=A$. Use Lemma 3.2 for the set equality.

Solution to Question 2

By Lemma 3.2, $A\cap B=A⟺(A\cap B\subseteq A)\wedge (A\subseteq A\cap B)$.
$A\cap B\subseteq A$ always holds: $x\in A\cap B⟺x\in A\wedge x\in B$, and $(x\in A\wedge x\in B)\to x\in A$ is a tautology ($F\wedge G\models F$). So $\forall x(x\in A\cap B\to x\in A)$.
Hence $A\cap B=A⟺A\subseteq A\cap B$, and

$$\begin{array}{rlrl}& & & \\ A\subseteq A\cap B& ⟺\forall x(x\in A\to (x\in A\wedge x\in B))& & (\text{Def. 3.3, Def. 3.4})\\ & ⟺\forall x(x\in A\to x\in B)& & (F\to (F\wedge G)\equiv F\to G)\\ & ⟺A\subseteq B& & (\text{Def. 3.3})\end{array}$$

The middle law is checked by truth table: both sides are $0$ exactly when $F=1,G=0$. $\square$ The second part, $A\subseteq B⟺A\cup B=B$, works the same way using $(G\vee F)\to G\equiv F\to G$.

Question 3. (a) Compute $\mathcal{P}(\mathcal{P}(\mathcal{P}(\varnothing )))$ and its cardinality. (b) Give a set $A$ with $A\subseteq \mathcal{P}(A)$ and $A\ne \varnothing$, and one with $A⊈\mathcal{P}(A)$. (c) Is $\mathcal{P}(A)\cap \mathcal{P}(B)=\mathcal{P}(A\cap B)$ for all $A,B$? What about $\cup$?

Solution to Question 3

(a) $\mathcal{P}(\varnothing )=\{\varnothing \}$, $\mathcal{P}(\{\varnothing \})=\{\varnothing ,\{\varnothing \}\}$, so
$\mathcal{P}(\mathcal{P}(\mathcal{P}(\varnothing )))=\mathcal{P}(\{\varnothing ,\{\varnothing \}\})=\{\varnothing ,\{\varnothing \},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}\},$
cardinality $2^2=4$ (checked by computer).
(b) $A\subseteq \mathcal{P}(A)$ means every element of $A$ is also a subset of $A$. $A=\{\varnothing \}=1$ works: $\varnothing \subseteq A$. So does $A=2=\{\varnothing ,\{\varnothing \}\}$: $\{\varnothing \}\subseteq 2$ since $\varnothing \in 2$. Non-example: $A=\{\{\varnothing \}\}$, because its element $\{\varnothing \}$ is not a subset of $A$ ($\varnothing \notin A$).
(c) Yes for $\cap$.
$S\in \mathcal{P}(A)\cap \mathcal{P}(B)⟺S\subseteq A\wedge S\subseteq B⟺\forall x(x\in S\to x\in A\wedge x\in B)⟺S\subseteq A\cap B.$
The middle step uses $(F\to G)\wedge (F\to H)\equiv F\to (G\wedge H)$ under $\forall$.
No for $\cup$. Only $\mathcal{P}(A)\cup \mathcal{P}(B)\subseteq \mathcal{P}(A\cup B)$ holds. Counterexample: $A=\{1\}$, $B=\{2\}$. Then $\{1,2\}\in \mathcal{P}(A\cup B)$, but $\{1,2\}$ is a subset of neither $A$ nor $B$.

Question 4. (a) Show that $(a,b):=\{a,\{b\}\}$ is not a valid pair encoding with a concrete collision using only sets built from $\varnothing$. (b) Using Kuratowski pairs, write out $(\varnothing ,\{\varnothing \})$ and $(\{\varnothing \},\varnothing )$ explicitly and verify they differ.

Solution to Question 4

(a) Take $b=\varnothing$, $c=\{\varnothing \}$. Then $(\{b\},c)=\{\{b\},\{c\}\}=\{\{\varnothing \},\{\{\varnothing \}\}\}$ and $(\{c\},b)=\{\{c\},\{b\}\}=\{\{\{\varnothing \}\},\{\varnothing \}\}$, the same set by Def. 3.2. But the pairs differ: first components $\{\varnothing \}\ne \{\{\varnothing \}\}$.
(b) $(\varnothing ,\{\varnothing \})=\{\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}$ and $(\{\varnothing \},\varnothing )=\{\{\{\varnothing \}\},\{\{\varnothing \},\varnothing \}\}$. The second members coincide ($\{\varnothing ,\{\varnothing \}\}=\{\{\varnothing \},\varnothing \}$), but $\{\varnothing \}$ is a member of the first set and not of the second, whose members are $\{\{\varnothing \}\}$ and $2$. So the sets differ, as they must, since $\varnothing \ne \{\varnothing \}$.

Question 5. (a) Compute $1+2$ step by step from the definitions and check that it equals $3$. (b) For $A=B=C=\{0\}$, show $(A\times B)\times C\ne A\times (B\times C)$ using Kuratowski pairs. (c) True or false: $|A\times B|=|B\times A|$ for finite sets, even though $A\times B\ne B\times A$ in general?

Solution to Question 5

(a) Since $2=s(1)$ and $1=s(0)$:
$1+2=1+s(1)=s(1+1)=s(1+s(0))=s(s(1+0))=s(s(1))=s(2)=2\cup \{2\}=3.$
Recursive rule twice, base rule once, then the definition of $s$.
(b) $(A\times B)\times C=\{((0,0),0)\}$ and $A\times (B\times C)=\{(0,(0,0))\}$.

• $(0,0)=\{\{\varnothing \},\{\varnothing ,\varnothing \}\}=\{\{\varnothing \}\}$.
• The first component of $((0,0),0)$ is $\{\{\varnothing \}\}$; that of $(0,(0,0))$ is $\varnothing$.
• These differ, so the pairs differ (Kuratowski property), and the singleton sets differ.

Hence $\times$ is not associative.
(c) True. $(a,b)\mapsto (b,a)$ matches the elements one-to-one, so both have $|A|\cdot |B|$ elements. Same size does not imply same set: e.g. $\{0\}\times \{1\}$ vs. $\{1\}\times \{0\}$.