Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Advanced undergraduate

ZFC: axiomatic set theory

Name: ______________________

Date: ______________________

You will learn to

State the ZFC axioms as first-order sentences in the language $\{\in\}$ and explain what each one contributes
Derive first theorems from the axioms, including that there is no set of all sets and that no set is a member of itself
Encode ordered pairs, relations, functions and the natural numbers as sets, and prove the characteristic property of Kuratowski pairs
Describe the cumulative hierarchy $V_\alpha$ and the role of Foundation and Replacement in it
Explain the difference between proving a theorem in ZFC and proving that ZFC is consistent

1.
Which axiom is used to show that for any sets $a$ and $b$ the intersection $a \cap b = \{z \in a \mid z \in b\}$ is a set?
- A.Separation
- B.Pairing
- C.Union
- D.Replacement
2.
The stages of the cumulative hierarchy are $V_0 = \varnothing$ and $V_{n+1} = \mathcal P(V_n)$ . We know $|V_4| = 16$ . How many elements does $V_5$ have?
3.
How many elements does the Kuratowski pair $(a, a) = \{\{a\}, \{a, a\}\}$ have?
4.
In the proof that there is no set $U$ containing every set, we form $R = \{x \in U \mid x \notin x\}$ . Which axiom guarantees that $R$ is a set?
- A.Separation, applied to $U$
- B.Unrestricted comprehension
- C.Foundation
- D.Power set
5.
Which of these proposed definitions of an ordered pair fail the requirement that $\langle a, b \rangle = \langle c, d \rangle$ implies $a = c$ and $b = d$ ? Select all that fail.
- A. $\{\{a\}, \{a, b\}\}$
- B. $\{a, \{b\}\}$
- C. $\{\{a\}, \{b\}\}$
- D. $\{\{\{a\}, \varnothing\}, \{\{b\}\}\}$
6.
Assume ZFC is consistent. Which of these statements does ZFC not prove? Select all.
- A. $\mathrm{Con}(\mathrm{ZFC})$ , the consistency of ZFC
- B.There is a strongly inaccessible cardinal
- C.The continuum hypothesis $2^{\aleph_0} = \aleph_1$
- D.There is no set of all sets
- E.Every vector space has a basis
7.
Zermelo's system ZC is ZFC without Replacement (and without Foundation). The stage $V_{\omega + \omega}$ is a model of ZC. Which set's existence can therefore not be proved in ZC?
- A. $\{\omega, \mathcal P(\omega), \mathcal P(\mathcal P(\omega)), \dots\}$
- B. $\R$ , built as Dedekind cuts
- C. $\omega$
- D.The set $\R^\R$ of all functions from $\R$ to $\R$
8.
Which Lean statement formalises “no set is a member of itself” for Mathlib's model ZFSet?
- A.∀ x : ZFSet, x ∉ x
- B.¬ ∀ x : ZFSet, x ∈ x
- C.∃ x : ZFSet, x ∉ x
- D.∀ x y : ZFSet, x ∈ y → y ∉ x
9.
Represent sets by Python frozensets. Write numeral(n) (von Neumann: 0 is the empty frozenset and n + 1 = n ∪ {n}), kpair(a, b) returning the Kuratowski pair $\{\{a\}, \{a, b\}\}$ , and first(p) and second(p) that recover $a$ and $b$ from such a pair. Hint: $a$ belongs to every element of $p$ ; $b$ is the element of $\bigcup p$ that is not $a$ — unless $\bigcup p = \{a\}$ .
Computational — Practice

Answer key — ZFC: axiomatic set theory

1.
Separation, applied to the set $a$ and the formula $\varphi(z) := z \in b$ (with $b$ as a parameter), gives a set whose elements are exactly the $z \in a$ with $z \in b$ . Extensionality shows this set is unique, which justifies the notation $a \cap b$ .
2.
$V_5 = \mathcal P(V_4)$ and $|V_4| = 16$ , so $|V_5| = 2^{16} = 65536$ . The next stage has $2^{65536}$ elements, a number with $19729$ decimal digits.
3.
$\{a, a\}$ and $\{a\}$ have the same elements, so by Extensionality they are equal. Hence $(a, a) = \{\{a\}, \{a\}\} = \{\{a\}\}$ has exactly one element. This degenerate case is exactly why the proof of the characteristic property splits into the cases $b = a$ and $b \neq a$ .
4.
Separation: for the set $U$ and the formula $\varphi(x) := x \notin x$ it gives the set $R = \{x \in U \mid x \notin x\}$ . Because $U$ contains every set, $R \in U$ , and then $R \in R \iff R \notin R$ , a contradiction. So the assumption that $U$ exists is false.
5.
$\{a, \{b\}\}$ fails (take $a = \{d\}, c = \{b\}$ with $b \neq d$ : both pairs are $\{\{b\}, \{d\}\}$ ), and $\{\{a\}, \{b\}\}$ fails because it is symmetric. Kuratowski's $\{\{a\}, \{a, b\}\}$ works (proved in the lesson) and so does Wiener's $\{\{\{a\}, \varnothing\}, \{\{b\}\}\}$ : its element with two members is $\{\{a\}, \varnothing\}$ (note $\{a\} \neq \varnothing$ ) and its element with one member is $\{\{b\}\}$ , and these determine $a$ and $b$ .
6.
ZFC proves that there is no universal set and that every vector space has a basis. If ZFC is consistent, it proves neither $\mathrm{Con}(\mathrm{ZFC})$ (Gödel's second incompleteness theorem), nor the existence of an inaccessible cardinal (which would give a model $V_\kappa$ of ZFC and hence $\mathrm{Con}(\mathrm{ZFC})$ ), nor CH (Cohen 1963). It does not refute CH either (Gödel 1938).
7.
The sets $\omega$ , $\R$ and $\R^\R$ all appear at stages $\omega + n$ for small finite $n$ , and are built with Infinity, Power set and Separation. The set $\{\mathcal P^n(\omega) \mid n \in \omega\}$ has elements at every stage $\omega + n$ , so it first appears at stage $\omega + \omega + 1$ and is not in $V_{\omega+\omega}$ . Since $V_{\omega+\omega}$ satisfies ZC, ZC cannot prove that this set exists. Replacement, applied to $n \mapsto \mathcal P^n(\omega)$ , proves it in ZF.
8.
“No set is a member of itself” means: for every set $x$ , $x \notin x$ — in Lean ∀ x : ZFSet, x ∉ x. Moving the negation outside the quantifier (¬ ∀ x, x ∈ x) or replacing ∀ by ∃ gives weaker statements, and the 2-cycle statement is stronger. The lesson proves it from Foundation applied to {x}.

def numeral(n):
    x = frozenset()
    for _ in range(n):
        x = x | frozenset([x])
    return x


def kpair(a, b):
    return frozenset([frozenset([a]), frozenset([a, b])])


def first(p):
    common = frozenset.intersection(*p)
    (a,) = common
    return a


def second(p):
    a = first(p)
    union = frozenset().union(*p)
    others = union - {a}
    if not others:
        return a
    (b,) = others
    return b

The decoding mirrors the proof of the characteristic property: $\bigcap (a, b) = \{a\}$ recovers $a$ , and $\bigcup (a, b) = \{a, b\}$ then recovers $b$ (with the degenerate case $\bigcup (a, a) = \{a\}$ ). Since $a$ and $b$ are computed from the set $(a, b)$ alone, equal pairs have equal components.