The Lumenary · First-year graduate

Axiomatic set theory: hierarchy, cardinal arithmetic and L

Name: ______________________

Date: ______________________

You will learn to

Define the cumulative hierarchy $V_\alpha$ by transfinite recursion and prove, using foundation and replacement, that every set lies in some $V_\alpha$
Compute with cofinality and prove König's theorem $\operatorname{cf}(2^\kappa) > \kappa$ , deducing $2^{\aleph_0} \neq \aleph_\omega$
State and prove the reflection principle and use it to show that ZF is not finitely axiomatisable (if consistent)
Outline Gödel's proof that if ZF is consistent then so is ZFC + GCH, using the constructible universe $L$
Distinguish a relative consistency proof from an absolute one

1.
How many elements does $V_5$ have? (Recall $V_0 = \varnothing$ and $V_{n+1} = \mathcal{P}(V_n)$ .)
2.
Assuming ZFC, which of these cardinals are singular? Choose all that apply.
- A. $\aleph_\omega$
- B. $\aleph_{\omega + \omega}$
- C. $\aleph_1$
- D. $\aleph_{\omega+1}$
- E. $\aleph_{\omega_1}$
3.
Which of these values of $2^{\aleph_0}$ does ZFC rule out? Choose all that apply.
- A. $\aleph_\omega$
- B. $\aleph_{\omega_\omega}$
- C. $\aleph_{\omega+1}$
- D. $\aleph_{\omega_1}$
- E. $\aleph_1$
4.
In the proof that every set lies in some $V_\alpha$ , we form $\alpha = \sup\{\alpha_z + 1 : z \in y\}$ . Which axiom guarantees that this supremum exists?
- A.Replacement
- B.Foundation
- C.Power set
- D.Choice
5.
What exactly did Gödel's work on $L$ establish?
- A.If ZF is consistent, then so is ZFC + GCH.
- B.ZFC proves GCH.
- C.ZFC + GCH is consistent.
- D.GCH is true.
6.
Which axioms hold in $(V_{\omega+\omega}, \in)$ ? Choose all that apply.
- A.Power set
- B.Infinity
- C.Separation
- D.Replacement
7.
Which Lean statement correctly formalises the generalised continuum hypothesis?
- A.∀ κ : Cardinal, ℵ₀ ≤ κ → 2 ^ κ = Order.succ κ
- B.∀ κ : Cardinal, ℵ₀ ≤ κ → 2 ^ κ = κ + 1
- C.∀ κ : Cardinal, ℵ₀ ≤ κ → κ < 2 ^ κ
- D.(2 : Cardinal) ^ ℵ₀ = ℵ₁
8.
The Lean proof of two_power_aleph0_ne_aleph_omega rewrites the inequality $\aleph_0 \lt \operatorname{cf}(2^{\aleph_0})$ using ord_aleph, cof_omega isSuccLimit_omega0 and cof_omega0. Which mathematical fact does this chain of rewrites establish?
- A. $\operatorname{cf}(\aleph_\omega) = \aleph_0$ , via $\operatorname{cf}(\omega_\omega) = \operatorname{cf}(\omega)$
- B.König's theorem $\kappa \lt \operatorname{cf}(2^\kappa)$
- C. $\aleph_\omega$ is regular
- D. $2^{\aleph_0} = \aleph_1$
9.
In Ackermann's coding, the natural number $x$ codes the set whose members are the numbers $y$ with bit $y$ of $x$ equal to $1$ . Write rank(x), computing $\operatorname{rank}(x) = \sup\{\operatorname{rank}(y) + 1 : y \in x\}$ (and $0$ for $x = 0$ ).
Computational — Practice

Answer key — Axiomatic set theory: hierarchy, cardinal arithmetic and L

1.
$|V_{n+1}| = 2^{|V_n|}$ gives $0, 1, 2, 4, 16$ and then $|V_5| = 2^{16} = 65\,536$ . The experiment builds all of them.
2.
$\aleph_\omega$ , $\aleph_{\omega+\omega}$ (cofinality $\omega$ ) and $\aleph_{\omega_1}$ (cofinality $\omega_1$ ) are singular; $\aleph_1$ and $\aleph_{\omega+1}$ are successor cardinals, hence regular.
3.
König's theorem says $\operatorname{cf}(2^{\aleph_0}) \gt \omega$ . So exactly the candidates of cofinality $\omega$ are excluded: $\aleph_\omega$ and $\aleph_{\omega_\omega}$ . The others are all consistent with ZFC (by Gödel's $L$ and Cohen's forcing).
4.
Replacement: $\{\alpha_z : z \in y\}$ is the image of the set $y$ under a definable class function, hence a set, and its union is an ordinal. Without replacement the argument fails — in $V_{\omega+\omega}$ , a model of Zermelo set theory, some definable images of sets are not sets.
5.
Gödel showed that $L \models \mathsf{ZFC} + \mathsf{GCH}$ , provably in ZF; so any contradiction in ZFC + GCH would yield one in ZF. That is $\mathrm{Con}(\mathsf{ZF}) \to \mathrm{Con}(\mathsf{ZFC} + \mathsf{GCH})$ , a relative consistency proof.
6.
Power set, infinity and separation hold (indeed $V_{\omega+\omega}$ is a model of Zermelo set theory with choice), but replacement fails: $\{\omega + n : n \in \omega\}$ would be the image of $\omega$ under a definable function, yet its rank is $\omega + \omega$ .
7.
∀ κ : Cardinal, ℵ₀ ≤ κ → 2 ^ κ = Order.succ κ: for every infinite cardinal, $2^\kappa$ is the successor cardinal. Ordinary addition κ + 1 equals κ for infinite cardinals.
8.
The rewrites compute $\operatorname{cf}(\aleph_\omega) = \operatorname{cf}(\omega_\omega) = \operatorname{cf}(\omega) = \aleph_0$ . Combined with König's $\aleph_0 \lt \operatorname{cf}(2^{\aleph_0})$ and the assumption $2^{\aleph_0} = \aleph_\omega$ , this gives $\aleph_0 \lt \aleph_0$ .
9.
```
def members(x):
    return [y for y in range(x.bit_length()) if x >> y & 1]


def rank(x):
    return max((rank(y) + 1 for y in members(x)), default=0)
```
Every member $y$ of $x$ satisfies $y \lt x$ (since $2^y \le x$ ), so the recursion is well-founded — a finite shadow of $\in$ -induction. The tests check that sampled codes below $65536 = |V_5|$ have rank at most $4$ , i.e. lie in $V_5$ , and that $65536 = 2^{16}$ , the code of $\{16\}$ , has rank $5$ .