Kardinalna aritmetika Lecture notes

Let \[ \Class{R} = \{x \mid x \text{ is a set and } x \not\in x\} \] be a class. If \(\Class{R}\) were a set, then \[ \Class{R} \in \Class{R} \iff \Class{R} \not\in \Class{R}, \] a contradiction.

Define \[ \Class{X} \times \Class{Y} := \left\{ \left\{ \{x\}, \{x, y\} \right\} \mid x \in \Class{X},\, y \in \Class{Y} \right\} \] and \[ \pi_1(z) := \text{the unique } x \in \Class{X} \text{ such that } \exists y \in \Class{Y}.\, z = \{\{x\}, \{x,y\}\}, \] and similarly for \(\pi_2\).

These are well defined, and the required property holds, because \[ \{\{x\}, \{x,y\}\} = \{\{x'\}, \{x',y'\}\} \iff x = x' \land y = y', \] which is checked by Extensionality. So given \(x \in \Class{X}\) and \(y \in \Class{Y}\), the unique \(z \in \Class{X} \times \Class{Y}\) with \(\pi_1(z) = x\) and \(\pi_2(z) = y\) is \(z = \{\{x\},\{x,y\}\}\).

Construct \(\Class{N}\) as the class of Von Neumann natural numbers (see below).

Take \(\Class{N} := \mathrm{vN}\), \(0 := \emptyset\) and \(S(x) := x^{ +}\). Note that every element of a vN-number is again a vN-number, and that every vN-number \(X\) is transitive and satisfies \(X \not\in X\); all three follow by applying property 1. of the definition. We check the three conditions.

1. \(S\) is injective: if \(x^{ +} = y^{ +}\), then \(x \in y^{ +}\) and \(y \in x^{ +}\), so either \(x = y\), or \(x \in y\) and \(y \in x\) — and the latter gives \(x \in x\) by transitivity, a contradiction.
2. \(S(x) \neq 0\): we have \(x \in x^{ +}\), so \(x^{ +} \neq \emptyset\).
3. Induction: suppose \(\emptyset \in \Class{X}\) and \(z \in \Class{X} \implies z^{ +} \in \Class{X}\) for every \(z \in \mathrm{vN}\), and let \(X\) be a vN-number. Put \(Y := \{z \in X \mid z \in \Class{X}\}\), which is a set by Separation. Then \(\emptyset \in X \implies \emptyset \in Y\), and if \(z \in Y\) and \(z^{ +} \in X\), then \(z\) is a vN-number in \(\Class{X}\), so \(z^{ +} \in \Class{X}\) and hence \(z^{ +} \in Y\). By property 1. we get \(Y = X\), i.e. \(X \subseteq \Class{X}\). By property 2., either \(X = \emptyset \in \Class{X}\), or \(X = z^{ +}\) for some \(z \in X \subseteq \Class{X}\), and then \(X = z^{ +} \in \Class{X}\). So \(\mathrm{vN} \subseteq \Class{X}\).

Let \(f : A_0 \rightarrow B_0\) be injective. Define two sequences of subsets of

Define \(C_n = A_n \setminus B_n \) for every \(n \geq 0\). Likewise define \[ C = \bigcup\limits_n C_n \text{ and } D = A_0 \setminus C. \]

We have

So we have \[ f(C) = f\left(\bigcup\limits_{n\geq 0} C_n\right) = \bigcup\limits_{n \geq 0} f(C_n) = \bigcup\limits_{n \geq 0} C_{n+1} = C \setminus C_0 \] Then we have that \(f : C \rightarrow C \setminus C_0\) is a bijection. Then \[ B_0 = B \uplus C \setminus C_0 \cong D \uplus C = A_0. \]

Suppose \(\abs{A} \leq \abs{B}\) and \(\abs{B} \leq \abs{A}\). Then we have injective functions \[ f : A \rightarrow B \text{ and } g : B \rightarrow A. \] Define \(A_0 = A\) and \(B_0 = g(B)\). Then \[ g \circ f : A \rightarrow B_0 \] is injective so \(\abs{A_0} \leq \abs{B_0}\). By the lemma, we have \[ \abs{A} = \abs{A_0} = \abs{B_0} = \abs{B}. \]

Suppose first we have \(\abs{X} \leq \abs{Y}\) and \(\abs{Y} \ll \abs{Z}\). Let \(i : X \rightarrow Y\) and \(j : Y \rightarrow Z\) be injections. Then since \(j \circ i\) is injective we have \(\abs{X} \leq \abs{Z}\). Suppose, for contradiction, that there exists a surjection \(g : X \rightarrow Z\). We define \(h : Y \rightarrow Z\) by \[ h(y) = \begin{cases} g(x) & \text{ if } y = i(x) \\ j(y) & \text{ if } y \not\in i(x) \end{cases} \] Then \(h\) is well-defined because \(i\) is injective. Consider any \(z \in Z\). Because \(g\) is surjective, we have \(z = g(x)\) for some \(x \in X\). Then \(z = h(i(x))\). This shows \(h\) is surjective, contradicting \(\abs{Y} \ll \abs{Z}\).

Now suppose we have \(\abs{X} \ll \abs{Y}\) and \(\abs{Y} \leq \abs{Z}\). This gives us the injections \(i : X \rightarrow Y\) and \(j : Y \rightarrow Z\). Now suppose for contradiction that \(g : X \rightarrow Z\) is surjective. Define \(h: X \rightarrow Y\) by \[ h(x) = \begin{cases} y & \text{ if } j(y) = g(x) \\ i(x) & \text{ if } g(x) \not\in j(y) \end{cases} \] Then \(h\) is well-defined because \(j\) is injective. Consider any \(y \in Y\). Since \(g\) is surjective, there exists \(x \in X\) such that \(g(x) = j(y)\). Hence \(h(x) = y\). This shows \(h\) is surjective, contradicting \(\abs{X} \ll \abs{Y}\).

Let us prove the first statement. First, if we have \(m \leq n\), then \(k \mapsto k\) is an injection on \([m] \rightarrow [n]\).

We prove the right implication by induction on \(n\), i.e. showing \[ \forall n \in \N .\, \left[ \forall m \in \N .\, \abs{[m]} \leq \abs{[n]} \implies m \leq n\right]. \] Assume \(n = 0\). We need to show \(\forall m \in \N .\, \abs{[m]} \leq \abs{[0]} \implies m \leq 0\). Suppose \(j : [m] \rightarrow [0]\) is injective. Because the codomain \([0]\) is \(\emptyset\), the domain \([m]\) is also \(\emptyset\). Hence we must have \(m = 0\) since for \(m > 0\) we get \(0 \in [m]\).

For \(n > 0\) we assume the induction hypothesis \(\forall m \in \N .\, \abs{[m]} \leq \abs{[n - 1]} \implies m \leq n - 1\). We show \(\forall m \in \N .\, \abs{[m]} \leq \abs{[n]}\implies m \leq n\). Suppose \(j : [m] \rightarrow [n]\) is injective.

If \(n - 1 \not\in j([m])\), we have \(j([m]) \subseteq [n - 1]\). So \(j\) defines an injection \([m] \rightarrow [n - 1]\). By the induction hypothesis, we get \(m \leq n - 1 \leq n\).

Now if \(n - 1 \in j([m])\), because \(j\) is injective, there is exactly one \(u \in [m]\) such that \(j(u) = n - 1\). Define \(h : [m - 1] \rightarrow [n - 1]\) with \[ h(i) = \begin{cases} j(i) & \text{ if } i < u \\ j(i + 1) & \text{ if } i \geq u \end{cases} \] Because \(j\) is injective, so is \(h\). By the induction hypothesis, it follows that \(m - 1 \leq n - 1\). Therefore \(m \leq n\).

Let us now prove the second statement. Fix \(n \in \N\). The inclusion \(k \mapsto k : [n] \rightarrow \N\) is injective, so \(\abs{[n]} \leq \abs{\N}\). It remains to show that there is no surjection from \([n]\) to \(\N\). If \(n = 0\), then \([0] = \emptyset\) and there is no surjection \(\emptyset \rightarrow \N\), since \(0 \in \N\). So suppose \(n > 0\) and let \(g : [n] \rightarrow \N\) be any function. By induction on \(n\), the image \(g([n])\) is a nonempty set of naturals with a greatest element \(k\). Then \(k + 1 \in \N\) but \(k + 1 \not\in g([n])\), so \(g\) is not surjective. Hence \(\abs{[n]} \ll \abs{\N}\).

In particular \(\N\) is not finite: if we had \(\abs{\N} = \abs{[n]}\) for some \(n \in \N\), this would contradict \(\abs{[n]} \ll \abs{\N}\), which gives \(\abs{[n]} \neq \abs{\N}\).

\leavevmode First, the equivalence \(2 \iff 3\) is easy. For \(4 \implies 3\), suppose \(e : \N \rightarrow X\) is injective. Define \(i : X \rightarrow X\) by \[ i(x) = \begin{cases} x & \text{if } x \neq e(\N) \\ e(n + 1) & \text{if } x = e(n) \end{cases} \] Then \(i\) is a proper injection because \(e(0) \not\in i(x)\).

For \(3 \implies 4\) suppose \(i : X \rightarrow X\) is a proper injection. Because it's proper, there exists a \(x_0 \in X \setminus i(x)\). Define \(e : \N \rightarrow X\) by \[ e(0) = x_0 \text{ and } e(n + 1) = i(e(n)). \] The injectivity of \(e\) is left as an exercise.

For \(4 \implies 1\) suppose that \(\abs{\N} \leq \abs{X}\). Suppose for contradiction that \(X\) is finite. Then there exists \(n\) with \(\abs{X} = \abs{[n]}\). So \(\abs{\N} \leq \abs{X} = \abs{[n]}\), showing that \(\abs{\N} \leq \abs{[n]}\). Since we also have \(\abs{[n]} \leq \abs{\N}\), we have \(\abs{\N} = \abs{[n]}\). This contradicts \(\abs{[n]} \ll \abs{\N}\) from the previous proposition.

Finally, for \(1 \implies 4\), suppose \(X\) is infinite. We define an injection, that is, a sequence \((x_n)_{n\in \N}\) of distinct elements of \(X\). Suppose \((x_i)_{0 \leq i < n}\) is given. Since \(X\) is infinite, the function \(i \mapsto x_i : [n] \rightarrow X\) is not a bijection, but it is an injection, hence it cannot be surjective. Thus we can choose \[ x_n \in X \setminus \{x_i \mid 0 \leq i < n\} \neq \emptyset. \] The above defines an infinite sequence \((x_n)_{n \in \N}\) of distinct elements of \(X\). This gives the injection \(i : \N \rightarrowtail X\) defined by \(i(n) = x_n\).

Note that this version of the proof relies on the axiom of dependent choice. The relation is defined on finite sequences of elements from \(X\), relating two sequences if the second extends the first. In particular, we apply dependent choice to the set \[ S = \left\{ s \mid s \text{ is a finite sequence of distinct elements of } X \right\} \] with the relation \[ sRs' \iff \abs{s'} = 1 + \abs{s} \text{ and } s \text{ and } s'\vert_{\abs{s}} \] where \(\abs{s}\) is the length of the sequence \(s\) and \(s\vert_n\) restricts a sequence \(s\) with \(\abs{s} \geq n\) to its first \(n\) elements.

We have the injection \(i : X \rightarrowtail \pot X\) defined by \(i(x) = \{x\}\). Thus \(\abs{X} \leq \abs{\pot X}\). Now suppose \(g : X \twoheadrightarrow \pot X\) is a surjection. Define \[ S = \{x \in X \mid x \not\in g(x)\}. \] So \(S \in \pot X\) and \[ \forall x \in X .\, x\in S \iff x \not\in g(x). \] Since \(g\) is a surjection, there exists \(y \in X\) such that \(g(y) = S\). But then \(y \in g(y) \iff y \in S \iff y \not\in g(y)\), a contradiction. Thus there is no surjection from \(X\) to \(\pot X\), so indeed \(\abs{X} \ll \abs{\pot X}\).

What the statements above are saying is that if \(f : X \rightarrow Y\) is a bijection or injection respectively, so is \(\pot f : \pot X \rightarrow \pot Y\). This is easy to verify directly, but a more methodological approach is to derive them via the functoriality of the powerclass map, since functors preserve isomorphisms and split monomorphisms.

In particular,

• A function \(f : X \rightarrow Y\) is bijective if and only if it is an isomorphism, i.e. \[ \exists f^{-1} : Y \rightarrow X \text{ such that } f^{-1} \circ f = \operatorname{id}_X \text{ and } f \circ f^{-1} = \operatorname{id}_{Y} \]
• Functors always preserve isomorphisms.
• A function \(f : X \rightarrow Y\) where \(X \neq \emptyset\) is injective if and only if it is a section, i.e. \[ \exists g : Y \rightarrow X \text{ such that } g\circ f = \operatorname{id}_X. \]
• Functors always preserve sections.
• Since \(\pot \emptyset = \left\{ \emptyset \right\}\) is a singleton, every function \(\pot \emptyset \rightarrow Z\) is likewise injective.

For instance, to prove \(\abs{X}^{\abs{Y} \cdot \abs{Z}} = (\abs{X}^{\abs{Y}})^{\abs{Z}}\), we establish the bijection \(\Lambda : X^{Y \times Z} \rightarrow (X^Y)^Z\) \[ \Lambda(g : Y \times Z \rightarrow X) := \lambda z \in Z . \lambda y \in Y . g(y, z). \]

Let's show the second point first. We have \[ \abs{X} \leq \abs{X} + \abs{X} \] since we have two obvious injections. Next, \[ \abs{X} + \abs{X} = \abs{X} \cdot 2 \leq \abs{X} \cdot \abs{X} = \abs{X} \] first by distributivity and then by assumption. Thus \(\abs{X} = \abs{X} + \abs{X}\) by the Cantor-Schröder-Bernstein theorem.

For the first point, note that \(X\) is Dedekind infinite, since we have the injection \[ x \mapsto f(0, x) \] by the bijection \(f : X \times X \rightarrow X\). Here \(0\) and \(1\) denote two distinct elements of \(X\), which exist since \(\abs{X} \geq 2\). This map is injective because \(f\) is, and it is not surjective, since \(f(1, x)\) is never of the form \(f(0, x')\), again because \(f\) is injective. So \(X\) is Dedekind infinite, and hence \(\aleph_0 \leq \abs{X}\).

We have

Consider the following diagram: \[ Y \xrightarrow{\subseteq} X \xrightarrow{f} X \times X \xrightarrow{\pi_1} X \] Because \(\abs{Y} \ll \abs{X}\), the composition is not a surjection. Indeed, if it were, then choosing a preimage for each \(x \in X\) would give an injection \(X \rightarrow Y\), so that \(\abs{X} \leq \abs{Y}\), and hence \(\abs{X} = \abs{Y}\) by the Cantor-Schröder-Bernstein theorem, contradicting \(\abs{Y} \ll \abs{X}\).

So there exists \(x_0 \in X\) such that for all \(y \in Y\), we have \(f(y) = (x_1, x_2)\) where \(x_1 \neq x_0\). We therefore have an injective function \[ X \xrightarrow{x \mapsto (x_0, x)} (X \times X) \setminus f(Y). \] Then \[ \abs{X} \leq \abs{(X \times X) \setminus f(Y)} = \abs{X \setminus Y} \] because \(f\) is a bijection.

Clearly we also have \(\abs{X \setminus Y} \leq \abs{X}\). By the Cantor-Schröder-Bernstein theorem, we have \(\abs{X \setminus Y} = \abs{X}\).

By definition \(2^{\abs{X}} = \abs{[2]^X}\), and \(\abs{[2]^X} = \abs{\pot X}\) via the bijection \(\pot X \rightarrow [2]^X\) sending a subset \(A \subseteq X\) to its characteristic function. So it suffices to show that \(\abs{X} \ll \abs{\pot X}\).

First, \(\abs{X} \leq \abs{\pot X}\), since \(x \mapsto \left\{ x \right\}\) is an injection \(X \rightarrow \pot X\).

It remains to show \(\abs{X} \neq \abs{\pot X}\). In fact, no function \(f : X \rightarrow \pot X\) is surjective. Given such an \(f\), put \[ A := \left\{ x \in X \mid x \notin f(x) \right\} \in \pot X. \] If we had \(A = f(x_0)\) for some \(x_0 \in X\), then \(x_0 \in A\) if and only if \(x_0 \notin f(x_0) = A\), which is absurd. So \(A\) is not in the image of \(f\).

In particular there is no bijection \(X \rightarrow \pot X\), so \(\abs{X} \neq \abs{\pot X}\), and therefore \(\abs{X} \ll 2^{\abs{X}}\).

Let \(\beta \in \Ord\) be arbitrary. We will prove that \[ \alpha \leq \beta \lor \beta \leq \alpha \] holds for all \(\alpha \in \Ord\) by transfinite induction on \(\alpha\).

1. (Base case): When \(\alpha = 0\), we have \(0 \leq \beta\) by axiom.

2. (Step case): By induction hypotheses, we have \(\alpha \leq \beta\) or \(\beta \leq \alpha\). If \(\alpha \leq \beta\), then either \(\alpha = \beta\) or \(\alpha + 1 \leq \beta\) by the successor axiom. So either \(\beta \leq \alpha + 1\) or \(\alpha + 1 \leq \beta\) as required.

   If \(\beta \leq \alpha\), then we have \(\beta \leq \alpha < \alpha + 1\), so we have \(\beta \leq \alpha + 1\).

3. (Supremum case): Suppose that \(A\) is a set of ordinals \(\alpha\) satisfying \(\alpha \leq \beta \lor \beta \leq \alpha\). We need to show \[ \sup A \leq \beta \lor \beta \leq \sup A. \] There are two possible cases.
   • If \(\forall \alpha \in A\), we have \(\alpha \leq \beta\), then we have \(\sup A \leq B\).
   • Elsewise we have \(\exists \alpha \in A\) such that \(\beta \leq \alpha\). In this case, we have \(\beta \leq \alpha \leq \sup A\).

We proceed by transfinite induction.

1. (Base case): For \(\alpha = 0\), we have \([0] = \emptyset\) which is a set.
2. (Step case): If \([\alpha]\)is a set, then \[ [s(\alpha)] = [\alpha] \cup \left\{ \alpha \right\}, \] which is clearly a set.
3. (Supremum case): Suppose \([\alpha]\) is a set for every every \(\alpha \in A \subseteq \text{\Class{A}}\) is a set. Then \[ [\sup A] = \bigcup\limits_{\alpha \in A} [\alpha] \] is a set, because sets are closed under set-indexed unions.

Suppose \(\Ord\) is a set.

Then \(\sup(\Ord)\) is a maximum element in the set of ordinals. But this cannot be, because \(s(\sup(\Ord))\) is strictly larger.

By transfinite induction, left as exercise.

First note that \(\sup \emptyset = 0\). Indeed \(\emptyset \leq 0\) holds vacuously, so \(\sup \emptyset \leq 0\), and \(0 \leq \sup \emptyset\) because \(0\) is minimal.

(Existence). Let \[ \Class{X} = \left\{ \alpha \in \Ord \mid \alpha \text{ is a successor ordinal or } \alpha = \sup [\alpha] \right\} \] and apply transfinite induction.

1. (Base case): \([0] = \emptyset\) and \(\sup \emptyset = 0\), so \(0 = \sup [0]\) is a limit ordinal and \(0 \in \Class{X}\).
2. (Step case): \(s(\alpha)\) is a successor ordinal by definition, so \(s(\alpha) \in \Class{X}\) for every \(\alpha \in \Ord\).
3. (Supremum case): Let \(A \subseteq \Class{X}\) be a set and put \(\mu = \sup A\). If \(\mu \in A\), then \(\mu \in \Class{X}\) already. Otherwise every \(\alpha \in A\) satisfies \(\alpha \leq \mu\) and \(\alpha \neq \mu\), i.e. \(A \subseteq [\mu]\), and then \(\mu = \sup A\) exhibits \(\mu\) as a limit ordinal.

Hence \(\Class{X} = \Ord\), i.e. every ordinal is a successor ordinal or a limit ordinal.

(Exclusivity). Suppose \(\alpha\) were both, say \(\alpha = s(\alpha')\) and \(\alpha = \sup A\) with \(A \subseteq [\alpha]\). Let \(\beta \in A\), so \(\beta < s(\alpha')\). By linearity either \(\beta \leq \alpha'\), or \(\alpha' \leq \beta\); in the latter case the successor axiom gives \(\beta = \alpha'\) or \(s(\alpha') \leq \beta\), and \(s(\alpha') = \alpha \leq \beta\) contradicts \(\beta < \alpha\). So \(\beta \leq \alpha'\) in every case, i.e. \(\alpha'\) is an upper bound of \(A\). But then \[ \alpha = \sup A \leq \alpha' < s(\alpha') = \alpha, \] which is absurd.

Suppose \(\Class{X}\) satisfies 1, 2 and 3, and put \[ \Class{Y} = \left\{ \alpha \in \Ord \mid [s(\alpha)] \subseteq \Class{X} \right\}, \] so that \(\alpha \in \Class{Y}\) says that \(\alpha\) together with every ordinal below it lies in \(\Class{X}\). We show \(\Class{Y} = \Ord\) by transfinite induction in the original form.

1. (Base case): \([s(0)] = \left\{ 0 \right\} \subseteq \Class{X}\) by 1, so \(0 \in \Class{Y}\).
2. (Step case): Let \(\alpha \in \Class{Y}\). Then \(\alpha \in [s(\alpha)] \subseteq \Class{X}\), so \(s(\alpha) \in \Class{X}\) by 2, and therefore \[ [s(s(\alpha))] = [s(\alpha)] \cup \left\{ s(\alpha) \right\} \subseteq \Class{X}, \] i.e. \(s(\alpha) \in \Class{Y}\).
3. (Supremum case): Let \(A \subseteq \Class{Y}\) be a set and \(\mu = \sup A\). As in the proof that \([\alpha]\) is a set, \([\mu] = \bigcup_{\alpha \in A} [\alpha]\), and each \([\alpha] \subseteq [s(\alpha)] \subseteq \Class{X}\), so \([\mu] \subseteq \Class{X}\). It remains to see that \(\mu \in \Class{X}\). By the previous proposition \(\mu\) is either a successor or a limit ordinal. If \(\mu = s(\mu')\), then \(\mu' < \mu\), so \(\mu' \in [\mu] \subseteq \Class{X}\) and \(\mu = s(\mu') \in \Class{X}\) by 2. If \(\mu\) is a limit ordinal with \(\mu > 0\), then \(\mu \in \Class{X}\) by 3, and if \(\mu = 0\), then \(\mu \in \Class{X}\) by 1. Either way \([s(\mu)] = [\mu] \cup \left\{ \mu \right\} \subseteq \Class{X}\), i.e. \(\mu \in \Class{Y}\).

So \(\Class{Y} = \Ord\), and since \(\alpha \in [s(\alpha)]\) for every ordinal \(\alpha\), we conclude \(\Class{X} = \Ord\).

Suppose \(\Class{X} \subseteq \Ord\) satisfies \([\alpha] \subseteq \Class{X} \implies \alpha \in \Class{X}\), and put \[ \Class{W} = \left\{ \alpha \in \Ord \mid [\alpha] \subseteq \Class{X} \right\}. \] We show \(\Class{W} = \Ord\) by transfinite induction in the original form.

1. (Base case): \([0] = \emptyset \subseteq \Class{X}\), so \(0 \in \Class{W}\).
2. (Step case): If \(\alpha \in \Class{W}\), then \([\alpha] \subseteq \Class{X}\), hence \(\alpha \in \Class{X}\) by assumption, and so \([s(\alpha)] = [\alpha] \cup \left\{ \alpha \right\} \subseteq \Class{X}\), i.e. \(s(\alpha) \in \Class{W}\).
3. (Supremum case): If \(A \subseteq \Class{W}\) is a set, then, as in the proof that \([\alpha]\) is a set, \([\sup A] = \bigcup_{\alpha \in A} [\alpha] \subseteq \Class{X}\), so \(\sup A \in \Class{W}\).

Hence \(\Class{W} = \Ord\). Now let \(\alpha \in \Ord\) be arbitrary. Then \(\alpha \in \Class{W}\), i.e. \([\alpha] \subseteq \Class{X}\), and the assumption gives \(\alpha \in \Class{X}\). So \(\Class{X} = \Ord\).

The second formulation is a restatement of the first, since \(\forall x < y .\, x \in \Class{Y}\) says exactly that \([y] \subseteq \Class{Y}\).

Let \(a \in \Class{A}\), \(F : \Class{A} \rightarrow \Class{A}\) and \(L : \mathcal{P} \Class{A} \rightarrow \Class{A}\) as above. We need to prove the existence of a suitable \(T : \Ord \rightarrow \Class{A}\).

We proceed by defining a set of approximations to \(T\) for every \(\alpha\).

For an ordinal \(\gamma\), a \(\gamma\)-approximation is a function \(t : [\gamma] \rightarrow \Class{A}\) that satisfies

Note that if \(t : [\gamma] \rightarrow \Class{A}\) is a \(\gamma\)-approximation, then \[ t\vert_{[\beta]} : [\beta] \rightarrow A \] is a \(\beta\)-approximation for any \(\beta < \gamma\).

We will prove: \[ \forall \gamma \in \Ord. \, \exists! \gamma-\text{approximation } t_{\gamma} : [\gamma] \rightarrow \Class{A}. \] Once we prove this, we can define \[ T(\alpha) := t_{\alpha + 1}(\alpha). \]

We prove the above statement using transfinite induction.

For uniqueness, suppose \(t, t' : [\gamma] \rightarrow \Class{A}\) are both \(\gamma\)-approximations. We show \(t(\alpha) = t'(\alpha)\) for every \(\alpha < \gamma\) by transfinite induction on \(\alpha\). If \(\alpha = 0\) then both equal \(a\). If \(\alpha = s(\beta)\) then \(t(\alpha) = F(t(\beta)) = F(t'(\beta)) = t'(\alpha)\) by the induction hypothesis. If \(\alpha\) is a limit, then \(t\) and \(t'\) agree below \(\alpha\) by the induction hypothesis, so the sets \(\left\{ t(\beta) \mid \beta < \alpha \right\}\) and \(\left\{ t'(\beta) \mid \beta < \alpha \right\}\) are equal and hence so are their images under \(L\).

For existence, we induct on \(\gamma\) using the zero-successor-limit form of transfinite induction.

• (Case \(\gamma = 0\)): \([0] = \emptyset\), so the empty function is a \(0\)-approximation, vacuously.

• (Case \(\gamma = s(\delta)\)): let \(t_{\delta} : [\delta] \rightarrow \Class{A}\) be the \(\delta\)-approximation. Since \([s(\delta)] = [\delta] \cup \left\{ \delta \right\}\), it suffices to say what the value at \(\delta\) is, and we do so by cases on \(\delta\):

  \begin{align*} t_{s(\delta)}(\delta) &:= a & \text{if } \delta = 0 \\ t_{s(\delta)}(\delta) &:= F(t_{\delta}(\beta)) & \text{if } \delta = s(\beta) \\ t_{s(\delta)}(\delta) &:= L(\left\{ t_{\delta}(\alpha) \mid \alpha < \delta \right\}) & \text{if } \delta > 0 \text{ is a limit,} \end{align*}

  and \(t_{s(\delta)}\vert_{[\delta]} := t_{\delta}\). Each defining condition for an \(s(\delta)\)-approximation mentions only ordinals \(\leq \delta\): below \(\delta\) it holds because \(t_{\delta}\) is a \(\delta\)-approximation, and at \(\delta\) it holds by construction.

• (Case \(\gamma > 0\) a limit): by the induction hypothesis and uniqueness, the approximations cohere, i.e. \(t_{\delta'}\vert_{[\delta]} = t_{\delta}\) whenever \(\delta < \delta' < \gamma\). By replacement \(\left\{ t_{\delta} \mid \delta < \gamma \right\}\) is a set, and coherence makes \[ t_{\gamma} := \bigcup\limits_{\delta < \gamma} t_{\delta} \] a function \([\gamma] \rightarrow \Class{A}\). It is a \(\gamma\)-approximation because each of the three conditions constrains \(t_{\gamma}\) only at ordinals \(\alpha < \gamma\), and any such condition already holds in \(t_{s(\alpha)}\).

This proves the statement, so \(T(\alpha) := t_{\alpha + 1}(\alpha)\) is well defined. Note first that \(T\) agrees with every approximation: if \(\alpha < \gamma\) then \(t_{\gamma}\vert_{[s(\alpha)]}\) is an \(s(\alpha)\)-approximation, so by uniqueness it is \(t_{s(\alpha)}\) and therefore \(t_{\gamma}(\alpha) = T(\alpha)\).

It remains to check the three equations. We have \(T(0) = t_{1}(0) = a\). For a successor, \[ T(s(\alpha)) = t_{s(s(\alpha))}(s(\alpha)) = F\big(t_{s(s(\alpha))}(\alpha)\big) = F(T(\alpha)), \] using the agreement just noted. For \(\lambda > 0\) a limit, \[ T(\lambda) = t_{s(\lambda)}(\lambda) = L\big(\left\{ t_{s(\lambda)}(\alpha) \mid \alpha < \lambda \right\}\big) = L\big(\left\{ T(\alpha) \mid \alpha < \lambda \right\}\big). \]

Finally, \(T\) is unique: if \(T'\) also satisfies the three equations, then \(T(\alpha) = T'(\alpha)\) for all \(\alpha\) by exactly the transfinite induction used for uniqueness of approximations above.

Exercise.

The proof is essentially the same as the non-parametrised version.

We define \(\Class{\mathrm{vNOrd}}\) as the class of von Neumann ordinals, namely

In particular, we define a structure with the three operations

• \(0 := \emptyset\)
• \(s(\alpha) := \alpha \cup \left\{ \alpha \right\}\) and
• \(\sup(A) := \bigcup A \)
• and taking \(\leq ~ := ~ \subseteq\).

We can prove that the smallest class of sets closed unser the above operations is an ordinal structure.

Suppose \(\Class{X}\) does not have a minimum element. We prove by transfinite induction, that \(\Ord \setminus \Class{X} = \Ord\). It is enough to show \(\Ord \setminus \Class{X}\) is progressive.

Suppose \(y \in \Ord \setminus \Class{X}\) satisfies \[ \forall x < y . \, x \in \Ord \setminus \Class{X}. \] Clearly \(y \not\in \Class{X}\) because if \(y \in \Class{X}\) it would be a minimum element. Indeed, every \(x < y\) lies in \(\Ord \setminus \Class{X}\), so no element of \(\Class{X}\) is strictly below \(y\); were \(y \in \Class{X}\), it would then be the minimum of \(\Class{X}\), which we assumed does not exist.

So \(\Ord \setminus \Class{X}\) is progressive, and transfinite induction gives \(\Ord \setminus \Class{X} = \Ord\), i.e. \(\Class{X}\) is empty. This contradicts the assumption that \(\Class{X}\) is nonempty.

• \((1. \implies 2.)\): We prove the contrapositive. Suppose \(\Class{Y} \subseteq \Class{X}\) is nonempty with no \(\Class{R}\)-minimal element, and consider \(\Class{Z} = \Class{X} \setminus \Class{Y}\). We claim \(\Class{Z}\) is \(\Class{R}\)-progressive. Let \(x \in \Class{X}\) be such that every \(y \in \Class{X}\) with \(y \Class{R} x\) lies in \(\Class{Z}\). If \(x\) were in \(\Class{Y}\), then \(x\) would not be \(\Class{R}\)-minimal in \(\Class{Y}\), so there would be \(z \in \Class{Y}\) with \(z \Class{R} x\); but then \(z \in \Class{Z}\), contradicting \(z \in \Class{Y}\). Hence \(x \in \Class{Z}\). So \(\Class{Z}\) is progressive and \(\Class{Z} = \Class{X}\), i.e. \(\Class{Y}\) is empty — a contradiction. Thus 1. fails.
• \((2. \implies 1.)\): Let \(\Class{Y} \subseteq \Class{X}\) be \(\Class{R}\)-progressive and suppose \(\Class{Y} \neq \Class{X}\). Then \(\Class{X} \setminus \Class{Y}\) is nonempty, so it has an \(\Class{R}\)-minimal element \(x\). Every \(y \in \Class{X}\) with \(y \Class{R} x\) must lie in \(\Class{Y}\), since otherwise \(y \in \Class{X} \setminus \Class{Y}\) would contradict the \(\Class{R}\)-minimality of \(x\). By progressivity \(x \in \Class{Y}\), contradicting \(x \in \Class{X} \setminus \Class{Y}\). Hence \(\Class{Y} = \Class{X}\).
• \((2. \implies 3.)\): We prove the contrapositive. Suppose \((x_n)\) is \(\Class{R}\)-decreasing. The set \(\left\{ x_n \mid n \in \N \right\}\) is clearly nonempty and has no \(\Class{R}\)-minimal element.
• \((3. \implies 2.)\): Suppose \(\Class{Y} \subseteq \Class{X}\) is nonempty and has no \(\Class{R}\)-minimal element. Define
  1. \(x_0\) as some element in \(\Class{Y}\).
  2. \(x_{n+1}\) as some chosen element such that \(x_{n+1} \Class{R} x_n\), which exists because \(x_n\) is not minimal. By dependent choice we get the required sequence \((x_n)\).

• \((1. \implies 2.)\): Let \(S \subseteq X\) be nonempty. Since \(<\) is well-founded, \(S\) has a \(<\)-minimal element \(m\). As \(\leq\) is total, no \(x \in S\) satisfies \(x < m\), hence every \(x \in S\) satisfies \(m \leq x\); so \(m\) is a minimum.
• \((2. \implies 1.)\): First, \(\leq\) is total: for \(x, y \in X\) the set \(\left\{ x, y \right\}\) has a minimum, so \(x \leq y\) or \(y \leq x\). Second, every nonempty \(S \subseteq X\) has a minimum, which is in particular a \(<\)-minimal element of \(S\); by the characterization of progressivity this makes \(<\) well-founded. Hence \((X, \leq)\) is a well-order.

If \(A \cong B\), then \(A \cong B \cong [\operatorname{Ord}(B)]\), so \(\operatorname{Ord}(B)\) is an ordinal whose standard set is isomorphic to \(A\); by the uniqueness part of the classification theorem \(\operatorname{Ord}(A) = \operatorname{Ord}(B)\). Conversely, if \(\operatorname{Ord}(A) = \operatorname{Ord}(B)\), then \(A \cong [\operatorname{Ord}(A)] = [\operatorname{Ord}(B)] \cong B\).

Write \(\alpha = \operatorname{Ord}(A)\) and \(\beta = \operatorname{Ord}(B)\).

• \((2. \implies 1.)\): If \(A \cong I\) for an initial segment \(I \subseteq B\), then the composite \(A \cong I \hookrightarrow B\) is an embedding.
• \((1. \implies 3.)\): Let \(f : A \rightarrow B\) be an embedding and suppose, for a contradiction, that \(\beta < \alpha\). Then \([\beta]\) is a proper initial segment of \([\alpha]\), so transporting along \(A \cong [\alpha]\) and \(B \cong [\beta]\) we obtain an embedding \(g : B \rightarrow A\) whose image is a proper initial segment of \(A\), which by Lemma B is \([a]\) for some \(a \in A\). Then \(g \circ f : A \rightarrow A\) is an embedding with \((g \circ f)(a) \in [a]\), that is \((g \circ f)(a) < a\), contradicting Lemma A. Hence \(\alpha \leq \beta\).
• \((3. \implies 2.)\): If \(\alpha \leq \beta\), then \([\alpha]\) is an initial segment of \([\beta]\), and its image \(I\) under an isomorphism \([\beta] \cong B\) is an initial segment of \(B\) with \(A \cong [\alpha] \cong I\).

1. By the comparison theorem the two embeddings give \(\operatorname{Ord}(A) \leq \operatorname{Ord}(B)\) and \(\operatorname{Ord}(B) \leq \operatorname{Ord}(A)\), so \(\operatorname{Ord}(A) = \operatorname{Ord}(B)\), and hence \(A \cong B\).
2. The ordinals are totally ordered, so either \(\operatorname{Ord}(A) \leq \operatorname{Ord}(B)\) or \(\operatorname{Ord}(B) \leq \operatorname{Ord}(A)\); the comparison theorem turns this into an embedding one way or the other.

Write \(\alpha = \operatorname{Ord}(X, \leq_X)\) and \(\beta = \operatorname{Ord}(Y, \leq_Y)\), and let \(i : X \rightarrow [\alpha]\) and \(j : Y \rightarrow [\beta]\) be the isomorphisms given by the classification theorem. By uniqueness of the order type it suffices to produce an isomorphism \(X + Y \cong [\alpha + \beta]\). Define

• \(h\) lands in \([\alpha + \beta]\): for \(x \in X\) we have \(i(x) < \alpha \leq \alpha + \beta\), and for \(y \in Y\) we have \(j(y) < \beta\), hence \(\alpha + j(y) < \alpha + \beta\) since addition is strictly monotone in its right argument.
• \(h\) preserves and reflects the order: on the two summands separately this is because \(i\) and \(j\) are isomorphisms and \(\gamma \mapsto \alpha + \gamma\) is strictly monotone; and across the summands \(i(x) < \alpha \leq \alpha + j(y)\), which matches \(\iota_0(x) <_{X + Y} \iota_1(y)\).
• \(h\) is surjective: let \(\gamma < \alpha + \beta\). If \(\gamma < \alpha\) then \(\gamma = i(x)\) for a (unique) \(x \in X\). Otherwise \(\alpha \leq \gamma\), and then \(\gamma = \alpha + \delta\) for a unique ordinal \(\delta\), which satisfies \(\delta < \beta\); so \(\gamma = h(\iota_1(j^{-1}(\delta)))\).

Thus \(X + Y \cong [\alpha + \beta]\), and therefore \(\operatorname{Ord}(X + Y, \leq_{X + Y}) = \alpha + \beta\).

Write \(\alpha = \operatorname{Ord}(X, \leq_X)\) and \(\beta = \operatorname{Ord}(Y, \leq_Y)\), with isomorphisms \(i : X \rightarrow [\alpha]\) and \(j : Y \rightarrow [\beta]\). Recall that \((x, y) \leq_{X \times Y} (x', y')\) iff \(y <_Y y'\), or \(y = y'\) and \(x \leq_X x'\). Define \(h : X \times Y \rightarrow [\alpha \cdot \beta]\) by \[ h(x, y) = \alpha \cdot j(y) + i(x). \]

• \(h\) lands in \([\alpha \cdot \beta]\): writing \(\delta = j(y) < \beta\) and \(\varepsilon = i(x) < \alpha\), we get \(\alpha \cdot \delta + \varepsilon < \alpha \cdot \delta + \alpha = \alpha \cdot (\delta + 1) \leq \alpha \cdot \beta\), using that \(\delta + 1 \leq \beta\) and that multiplication is monotone in its right argument.
• \(h\) is surjective, hence bijective: by division with remainder for ordinals, every \(\gamma < \alpha \cdot \beta\) can be written as \(\gamma = \alpha \cdot \delta + \varepsilon\) with \(\varepsilon < \alpha\), and such a decomposition is unique; from \(\alpha \cdot \delta \leq \gamma < \alpha \cdot \beta\) we get \(\delta < \beta\). So \(\gamma = h(i^{-1}(\varepsilon), j^{-1}(\delta))\).
• \(h\) preserves and reflects the order: for \(\delta, \delta' < \beta\) and \(\varepsilon, \varepsilon' < \alpha\) we have \[ \alpha \cdot \delta + \varepsilon < \alpha \cdot \delta' + \varepsilon' \iff \delta < \delta' \, \text{ or } \, (\delta = \delta' \text{ and } \varepsilon < \varepsilon'), \] since \(\alpha \cdot \delta + \varepsilon < \alpha \cdot \delta + \alpha = \alpha \cdot (\delta + 1) \leq \alpha \cdot \delta'\) whenever \(\delta < \delta'\), and addition is strictly monotone in its right argument. Transported along \(i\) and \(j\), the right hand side is exactly the reverse lexicographic comparison of \((x, y)\) and \((x', y')\).

Thus \(X \times Y \cong [\alpha \cdot \beta]\), and therefore \(\operatorname{Ord}(X \times Y, \leq_{X \times Y}) = \alpha \cdot \beta\).

Suppose \(f\) is not inflationary. Then there exists some element where \(x > f(x)\). But then the set \[ B = \left\{ x \mid x > f(x) \right\} \] is nonempty. Let \(x_0\) be the smallest element such that \(x_0 > f(x_0)\). Since \(f\) is an embedding, it preserves the strict order, so we have \[ f(x_0) > f(f(x_0)), \] so \(f(x_0) \in B\), contradicting the fact that \(x_0\) is the smallest element of \(B\).

1. Since \(I\) is proper, \(A \setminus I\) is nonempty, so it has a minimum \(a\). If \(x < a\), then \(x \in I\), since otherwise \(x \in A \setminus I\) would be below its minimum. Conversely, if \(x \in I\), then \(a \not\leq x\), because \(I\) is down-closed and \(a \not\in I\); as \(A\) is totally ordered this gives \(x < a\). Hence \(I = [a]\).
2. The same argument, with the least ordinal principle in place of minima: \(\Ord \setminus I\) is nonempty (a set is never all of \(\Ord\)), so it has a least element \(\alpha\), and the two inclusions above give \(I = [\alpha]\).

1. Suppose \(A\) is isomorphic to \([a]\) for some \(a \in A\). Let \(i : A \rightarrow [a]\) be an isomorphism. \[ A \xrightarrow{i} [a] \xrightarrow{\subseteq} A \] is an embedding but \(i(a) \in [a]\), which means \(i(a) < a\). This contradicts that embeddings are inflationary.
2. Suppose \(f : A \rightarrow A\) is an automorphism. Then \(f\) and \(f^{-1}\) are embeddings, so in particular inflationary. This means \[ x \leq f(x) \text{ and } x \leq f^{-1}(x) \] so we have \[ x \leq f(x) \leq f^{-1}(f(x)) = x \] so \(f\) is the identity.
3. Is trivial. If \(i, j : A \rightarrow B\) are isomorphisms, then \(j^{-1} \circ i : A \rightarrow A\) is an automorphism, hence the identity by 2., so \(i = j\).

For uniqueness, suppose \([\alpha] \cong A \cong [\alpha']\). If \(\alpha < \alpha'\), then \([\alpha']\) is isomorphic to a proper initial segment, namely \([\alpha]\). Contradiction. Likewise for \(\alpha' < \alpha\). Thus \(\alpha = \alpha'\).

It remains to show than an \(\alpha\) such that \(A \cong [\alpha]\) exists. By transfinite recursion, define \(f : \Ord \rightarrow A \uplus \left\{ e \right\}\) by \[ f(\alpha) = \begin{cases} \min A \setminus \left\{ f(\beta) \mid \beta < \alpha \right\} & \text{when this set is nonempty} \\ e & \text{otherwise} \end{cases} \] This satisfies transfinite induction.

Note that \(f\) is strictly increasing wherever it takes a value in \(A\). Indeed, let \(\beta < \alpha\) with \(f(\alpha) \neq e\) and \(f(\beta) \neq e\). Then \[ f(\alpha) \in A \setminus \left\{ f(\gamma) \mid \gamma < \alpha \right\} \subseteq A \setminus \left\{ f(\gamma) \mid \gamma < \beta \right\}, \] so \(f(\beta) \leq f(\alpha)\) by minimality of \(f(\beta)\), while \(f(\alpha) \neq f(\beta)\) because \(f(\alpha)\) avoids \(\left\{ f(\gamma) \mid \gamma < \alpha \right\}\). Hence \(f(\beta) < f(\alpha)\), and in particular \(f\) is injective on \(\left\{ \alpha \mid f(\alpha) \neq e \right\}\).

Now \(f\) takes the value \(e\) at some ordinal: otherwise \(f : \Ord \rightarrow A\) would be injective, and by replacement \(\Ord\) would be a set, which it is not. By the least ordinal principle, let \(\alpha\) be the least ordinal with \(f(\alpha) = e\). Then \(f\) restricts to a strictly increasing — hence order-embedding — map \(f : [\alpha] \rightarrow A\), and this restriction is surjective, since \(f(\alpha) = e\) says precisely that \(A \setminus \left\{ f(\beta) \mid \beta < \alpha \right\}\) is empty. So \(f : [\alpha] \rightarrow A\) is an isomorphism and \(A \cong [\alpha]\).

Consider the set \[ W := \left\{ R \subseteq A \times A \mid R \text{ is a well-order on a subset of } A \right\} \] Consider the function \(W \rightarrow \Ord\) \[ R \mapsto \operatorname{Ord}(A', R) \] where \(A' \subseteq A\) is the subset of \(A\) that \(R\) well-orders.

The image of the function is a set of ordinals. As a set it is not the whole of \(\Ord\), so we can define \[ \underline{h}(A) := \text{ the smallest ordinal outside this image}. \] It remains to see that this ordinal is the one we asked for. We claim that an ordinal \(\beta\) lies in the image exactly when \(\abs{\beta} \leq \abs{A}\).

If \(\beta = \operatorname{Ord}(A', R)\) for some \(R \in W\), then \([\beta] \cong A' \subseteq A\), so \(\abs{\beta} \leq \abs{A}\). Conversely, if \(\abs{\beta} \leq \abs{A}\), take an injection \([\beta] \rightarrow A\) and let \(A' \subseteq A\) be its image. Transporting the ordering of \([\beta]\) along the induced bijection gives a well-order \(R \subseteq A \times A\) on \(A'\) with \(\operatorname{Ord}(A', R) = \beta\), so \(\beta\) is in the image.

So the image is exactly \(\left\{ \beta \in \Ord \mid \abs{\beta} \leq \abs{A} \right\}\), and hence \(\underline{h}(A)\) is the smallest ordinal with \(\abs{\underline{h}(A)} \not\leq \abs{A}\). We call this function the Hartogs' function.

By the proof of Hartogs' lemma, \(\underline{h}(\alpha) := \underline{h}([\alpha])\) is the smallest ordinal \(\beta\) with \(\abs{\beta} \not\leq \abs{\alpha}\). So we only need to see that, for ordinals, \(\abs{\beta} \not\leq \abs{\alpha}\) says the same thing as \(\abs{\beta} > \abs{\alpha}\).

Any two ordinals are comparable: either \(\beta \leq \alpha\) or \(\alpha \leq \beta\), and the corresponding inclusion \([\beta] \subseteq [\alpha]\) or \([\alpha] \subseteq [\beta]\) is an injection. So for ordinals we always have \(\abs{\beta} \leq \abs{\alpha}\) or \(\abs{\alpha} \leq \abs{\beta}\) — note that this needs no choice.

Hence \(\abs{\beta} \not\leq \abs{\alpha}\) forces \(\abs{\alpha} \leq \abs{\beta}\), and the two cannot be equal, so \(\abs{\beta} > \abs{\alpha}\). Conversely \(\abs{\beta} > \abs{\alpha}\) certainly gives \(\abs{\beta} \not\leq \abs{\alpha}\). Taking the smallest such \(\beta\) on either side gives the statement.

Suppose \(\underline{h}(A)\) is not an initial ordinal. Then we have \(\beta < \abs{\underline{h}(A)}\) with \(\abs{\beta} = \abs{\underline{h}(A)}\), so there is a bijection \([\beta] \cong [\underline{h}(A)]\). Via the isomorphism, we get \(\abs{\beta} \not \leq \abs{A}\) which contradicts \(\underline{h}(A)\) being the Hartogs' ordinal.

Spelled out: \(\underline{h}(A)\) is by construction the smallest ordinal whose cardinality does not inject into \(A\), and we have produced a strictly smaller \(\beta < \underline{h}(A)\) with the same property. So no such \(\beta\) exists, and \(\underline{h}(A)\) is initial.

For a successor infinite ordinal \(\beta + 1\) we have \(\abs{\beta + 1} = \abs{1 + \beta} = \abs{\beta}\).

Here \(\beta\) is itself infinite, so \(1 + \beta = \beta\); and \([\beta + 1] = [\beta] \uplus \{\beta\}\) gives the first equality. Since \(\beta < \beta + 1\) with \(\abs{\beta} = \abs{\beta + 1}\), the ordinal \(\beta + 1\) is not initial.

An infinite ordinal is not \(0\), and by the above it is not a successor if it is initial. So every infinite initial ordinal is a limit ordinal.

Suppose \(I\) is a set of initial ordinals. Suppose \(\beta < \sup I\). Then there exists some \(\alpha \in I\) such that \(\beta < \alpha\). Then it must hold that \(\abs{\beta} < \abs{\alpha}\) because \(\alpha\) is initial. Thus \[ \abs{\beta} < \abs{\alpha} \leq \abs{\sup I}. \] The second inequality holds because \(\alpha \leq \sup I\), so \([\alpha] \subseteq [\sup I]\). Thus every \(\beta < \sup I\) has \(\abs{\beta} < \abs{\sup I}\), which is exactly what it means for \(\sup I\) to be initial.

Proposition A shows that \(\abs{\omega_{\alpha}} < \abs{\omega_{\alpha + 1}}\). If \(\alpha < \beta\), then \(\beta \geq \alpha + 1\), so we get \[ \abs{\omega_{\alpha}} < \abs{\omega_{\alpha+1}} \leq \abs{\omega_{\beta}}. \] using the monotonicity of \(\omega_{(-)}\).

Monotonicity itself is a transfinite induction on \(\beta\): we have \(\omega_{\beta + 1} = \underline{h}([\omega_{\beta}]) > \omega_{\beta}\), and for a limit \(\lambda\) we have \(\omega_{\lambda} = \sup_{\beta < \lambda} \omega_{\beta} \geq \omega_{\beta}\) for every \(\beta < \lambda\).

Finally, the cardinality inequality gives the ordinal one: if we had \(\omega_{\beta} \leq \omega_{\alpha}\), then \([\omega_{\beta}] \subseteq [\omega_{\alpha}]\) would give \(\abs{\omega_{\beta}} \leq \abs{\omega_{\alpha}}\). So \(\omega_{\alpha} < \omega_{\beta}\).

1. We prove this using transfinite induction using our propositions and lemmas.
   • (Case \(0\)): \(\omega_0 = \omega\) is infinite, and it is initial because every \(n < \omega\) is finite, so \(\abs{n} < \abs{\omega}\).
   • (Case \(\alpha + 1\)): \(\omega_{\alpha + 1} = \underline{h}([\omega_{\alpha}])\) is initial by proposition B, and it is infinite because \(\abs{\omega_{\alpha+1}} > \abs{\omega_{\alpha}} \geq \aleph_0\).
   • (Case \(\lambda\) limit): \(\omega_{\lambda} = \sup_{\alpha < \lambda} \omega_{\alpha}\) is a supremum of a set of initial ordinals, hence initial by lemma F. It is infinite because \(\omega_{\lambda} \geq \omega_0 = \omega\).

2. Uniqueness follows from proposition E. We now only need show every infinite initial ordinal arises as \(\omega_{\alpha}\) for some \(\alpha\). Let \(\gamma\) be an infinite initial ordinal. We need to find \(\alpha\) with \(\gamma = \omega_{\alpha}\). We define \[ I = \left\{ \beta \in \Ord \mid \omega_{\beta} < \gamma \right\}. \] \(I\) is a set because otherwise \(\beta \mapsto \omega_{\beta}\) would be an order embedding of \(\Ord\) in \([\gamma]\). Note that \(I\) is an initial segment set of \(\Ord\), so \(I = [\alpha]\). We have found \(\alpha\). We now need to show \(\gamma = \omega_{\alpha}\).

   First note that \(\omega_{\alpha} \geq \gamma\) because \(\alpha\) is not in \(I\). We need only prove \(\omega_{\alpha} \leq \gamma\). This follows by case analysis on \(\alpha\) being either 0, \(\alpha' + 1\) or a limit ordinal.

   • (Case \(\alpha = 0\)): \(\omega_0 = \omega \leq \gamma\) because \(\gamma\) is infinite.
   • (Case \(\alpha = \alpha' + 1\)): Then \(\alpha' \in I\), so \(\omega_{\alpha'} < \gamma\). As \(\gamma\) is initial, this gives \(\abs{\omega_{\alpha'}} < \abs{\gamma}\), and in particular \(\abs{\gamma} \not\leq \abs{\omega_{\alpha'}}\). Since \(\omega_{\alpha} = \underline{h}([\omega_{\alpha'}])\) is the smallest ordinal with that property, \(\omega_{\alpha} \leq \gamma\).
   • (Case \(\alpha\) limit): Every \(\beta < \alpha\) lies in \(I\), so \(\omega_{\beta} < \gamma\). Hence \(\gamma\) is an upper bound and \(\omega_{\alpha} = \sup_{\beta < \alpha} \omega_{\beta} \leq \gamma\).

   In all three cases \(\omega_{\alpha} \leq \gamma\), so \(\gamma = \omega_{\alpha}\) as required.

We want to show \[ \aleph_{\alpha} = \aleph_{\alpha} \cdot \aleph_{\alpha}. \] First, \((\leq)\) is obvious. We prove \(\aleph_{\alpha} \cdot \aleph_{\alpha} \leq \aleph_{\alpha}\) by transfinite induction on \(\alpha\).

• (Case \(\alpha = 0\)): We already know \(\aleph_0 = \aleph_0 \cdot \aleph_0\).

• (Case \(\alpha > 0\)): For all \(\beta < \alpha\), we have \(\aleph_{\beta} \cdot \aleph_{\beta} = \aleph_{\beta}\). The main step is to establish \(\operatorname{Ord}([\omega_{\alpha}] \times [\omega_{\alpha}], \prec) \leq \omega_{\alpha}\). Once we have proved this, we conclude the proof by \[ \aleph_{\alpha} \cdot \aleph_{\alpha} = \abs{[\omega_{\alpha}] \times [\omega_{\alpha}]} = \abs{\operatorname{Ord}([\omega_{\alpha}] \times [\omega_{\alpha}])} \leq \abs{\omega_{\alpha}} = \aleph_{\alpha}. \]

  Let us prove \(\operatorname{Ord}([\omega_{\alpha}] \times [\omega_{\alpha}], \prec) \leq \omega_{\alpha}\).

  By Lemma A, \(\prec\) is a strict order in which every nonempty subclass has a minimum, so it well-orders any set it restricts to and the order type \(\delta := \operatorname{Ord}([\omega_{\alpha}] \times [\omega_{\alpha}], \prec)\) is defined. By Lemma B, \([\omega_{\alpha}] \times [\omega_{\alpha}]\) is an initial segment of \(\Ord \times \Ord\) under \(\prec\).

  Suppose for contradiction that \(\delta > \omega_{\alpha}\). Let \[ f : [\omega_{\alpha}] \times [\omega_{\alpha}] \rightarrow [\delta] \] be the order isomorphism. Since \(\omega_{\alpha} < \delta\), the set \(f^{-1}([\omega_{\alpha}])\) is a proper initial segment of \(([\omega_{\alpha}] \times [\omega_{\alpha}], \prec)\) of order type \(\omega_{\alpha}\), so it is of the form \[ S = \left\{ (\xi_1, \xi_2) \in [\omega_{\alpha}] \times [\omega_{\alpha}] \mid (\xi_1, \xi_2) \prec (\gamma_1, \gamma_2) \right\} \] for some \((\gamma_1, \gamma_2) \in [\omega_{\alpha}] \times [\omega_{\alpha}]\).

  Now put \(\gamma := \max(\gamma_1, \gamma_2) + 1\). Since \(\omega_{\alpha}\) is an infinite initial ordinal it is a limit ordinal by proposition D, so \(\gamma < \omega_{\alpha}\). By the very definition of \(\prec\), if \((\xi_1, \xi_2) \prec (\gamma_1, \gamma_2)\) then \(\max(\xi_1, \xi_2) \leq \max(\gamma_1, \gamma_2) < \gamma\), so both \(\xi_1, \xi_2 < \gamma\). Hence \[ S \subseteq [\gamma] \times [\gamma]. \]

  Taking cardinalities, and using that \(S\) has order type \(\omega_{\alpha}\), \[ \aleph_{\alpha} = \abs{\omega_{\alpha}} = \abs{S} \leq \abs{[\gamma] \times [\gamma]} = \abs{\gamma} \cdot \abs{\gamma}. \]

  It remains to see that \(\abs{\gamma} \cdot \abs{\gamma} < \aleph_{\alpha}\), which is the promised contradiction. If \(\gamma\) is finite then so is \(\abs{\gamma} \cdot \abs{\gamma}\), and \(\aleph_{\alpha}\) is infinite. If \(\gamma\) is infinite, then \(\abs{\gamma}\) is the cardinality of an infinite well-orderable set, so \(\abs{\gamma} = \aleph_{\beta}\) for some \(\beta\); and \(\gamma < \omega_{\alpha}\) with \(\omega_{\alpha}\) initial gives \(\aleph_{\beta} = \abs{\gamma} < \abs{\omega_{\alpha}} = \aleph_{\alpha}\), so \(\beta < \alpha\) by proposition E. The induction hypothesis at \(\beta\) then yields \[ \abs{\gamma} \cdot \abs{\gamma} = \aleph_{\beta} \cdot \aleph_{\beta} = \aleph_{\beta} < \aleph_{\alpha}. \]

  Either way \(\aleph_{\alpha} \leq \abs{\gamma} \cdot \abs{\gamma} < \aleph_{\alpha}\), a contradiction. Therefore \(\delta \leq \omega_{\alpha}\), which is what we needed.

For the case \((1 \implies 2)\), let \(<\) be a well-order on \(X\). One choice function is \[ Y \neq \emptyset \mapsto \text{ the minimum element of } Y \text{ under } <. \] Now for \((2 \implies 1)\), define by transfinite recursion \(y_{(-)} : \Ord \rightarrow X \uplus \left\{ e \right\}\) by \[ y_{\alpha} = \begin{cases} g(X \setminus \left\{ y_{\beta} \mid \beta < \alpha \right\}) & \text{if } X \setminus \left\{ y_{\beta} \mid \beta < \alpha \right\} \neq \emptyset \\ e & \text{otherwise} \end{cases} \] By transfinite induction we prove

1. \(\left\{ \alpha \mid y_{\alpha} \in X \right\}\) is an initial segment of \(\Ord\).
2. If \(y_{\alpha} = y_{\beta} \in X\), then \(\alpha = \beta\).
3. \(\left\{ \alpha \mid y_{\alpha} \in X \right\} = [\gamma]\) for some \(\gamma \in \Ord\).
4. \(\{y_{\alpha} \mid \alpha < \gamma\} = X\)

It follows that \(y_{(-)} : [\gamma] \rightarrow X\) is a bijection. Hence \(X\) is well-orderable.

• \((1) \iff (2)\) by the previous theorem.
• \((3) \implies 1\): Let \(S\) be a set of nonempty sets. We want to construct a choice function for \(S\). Define a partial order \(F\) where \[ F = \left\{ f \mid f \text{ is a choice function on a subset } S' \subseteq S \right\} \] and \[ f \subseteq f' \iff \left( \dom(f) \subseteq \dom(f') \text{ and } \forall x \in \dom(f).\, f(x) = f'(x) \right). \] Let \(C \subseteq F\) be a chain. Then an upper bound is simply \[ \bigcup C, \text{ i.e. } X \mapsto f(X) \text{ for } f \in C \text{ and } x \in \dom(f). \] This is well-defined. Then \(F\) has a maximal element \(f_{\max}\). But \(\dom(f_{\max}) = S\).
• \((2) \implies (3)\): Let \(X, \leq\) be a partial order stisfying the assumptions of Zorn's Lemma. By (2) and the previous theorem, let \(g\) be a choice function for \(\pot X\). Define \(y_{(-)} : \Ord \rightarrow X \uplus \left\{ e \right\}\) by transfinite recursion. \[ y_{\alpha} = \begin{cases} g(\left\{ x \in X \mid x \text{ is a strict upper bound for } \left\{ y_{\beta} \mid \beta < \alpha \right\} \right\}) \\ \text{if } \left\{ y_{\beta} \mid \beta < \alpha \right\} \subseteq X \text{ and the set of strict upper bounds is nonempty.} \\ e & \text{otherwise} \end{cases} \] By transfinite induction we prove that \(\left\{ \alpha \in \Ord \mid y_{\alpha} \in X \right\}\) is an initial segment of\(\Ord\) and equals \([\gamma]\) for some \(\gamma\) and \(\left\{ y_{\alpha} \mid \alpha < \gamma \right\}\) is a chain whose upper bound is a maximal element. Indeed, each \(y_{\alpha}\) is a strict upper bound of all the earlier ones, so \(\alpha \mapsto y_{\alpha}\) is injective on that initial segment. By Hartogs' lemma the initial segment cannot be the whole of \(\Ord\), so it is \([\gamma]\) for some ordinal \(\gamma\). Since \(y_{\gamma} = e\), the chain \(\left\{ y_{\alpha} \mid \alpha < \gamma \right\}\) has no strict upper bound, while by assumption it does have an upper bound \(u\). If \(u < z\) for some \(z \in X\), then \(z\) would be a strict upper bound of the chain, which is impossible. Hence \(u\) is a maximal element of \(X\).

For each \(n \in \N\) put \[ A_n := \left\{ f : [n] \rightarrow X \mid f \text{ is injective} \right\}. \] Every \(A_n\) is nonempty, since an empty \(A_n\) would mean that \(X\) is in bijection with some \([m]\) for \(m < n\), i.e. that \(X\) is finite. By countable choice applied to \(\left\{ A_n \mid n \in \N \right\}\) we obtain a family \((f_n)_{n \in \N}\) with \(f_n \in A_n\). Consider \[ U := \bigcup\limits_{n \in \N} f_n([n]) \subseteq X. \] Since \(\abs{f_n([n])} = n\) for every \(n\), the set \(U\) is not finite. On the other hand \[ \N \times \N \rightarrow U, \quad (n, k) \mapsto \begin{cases} f_n(k) & \text{if } k < n \\ f_1(0) & \text{otherwise} \end{cases} \] is surjective, and \(\abs{\N \times \N} = \aleph_0\), so \(U\) is countable. An infinite countable set has cardinality \(\aleph_0\), hence \[ \aleph_0 = \abs{U} \leq \abs{X}. \] By the characterisation of infinite sets, \(X\) is Dedekind infinite.

Let \((A_n)_{n \in \N}\) be a family of countable sets and put \(A := \bigcup\limits_{n \in \N} A_n\). If every \(A_n\) is empty then \(A = \emptyset\) is countable, so we may discard the empty members and assume every \(A_n \neq \emptyset\). For each \(n\) put \[ S_n := \left\{ e : \N \rightarrow A_n \mid e \text{ is surjective} \right\}, \] which is nonempty because \(A_n\) is countable and nonempty. By countable choice applied to \(\left\{ S_n \mid n \in \N \right\}\) we obtain a family \((e_n)_{n \in \N}\) with \(e_n \in S_n\). Then \[ \N \times \N \rightarrow A, \quad (n, k) \mapsto e_n(k) \] is surjective, and \(\abs{\N \times \N} = \aleph_0\). Since a surjective image of a countable set is countable, \(A\) is countable.

We prove the contrapositive. Suppose the relation \(R \subseteq X \times X\) is not well-founded, so some nonempty \(Y \subseteq X\) has no \(R\)-minimal element. Consider the converse relation on \(Y\), \[ y \; R' \; y' \iff y' R y. \] It is total on \(Y\): given \(y \in Y\), it is not \(R\)-minimal in \(Y\), so there is some \(y' \in Y\) with \(y' R y\), that is \(y R' y'\). Pick any \(y_0 \in Y\). By dependent choice there is a sequence \((y_n)_{n \in \N}\) in \(Y\) with \(y_n R' y_{n + 1}\) for every \(n\), i.e. with \[ \cdots R y_2 R y_1 R y_0. \] This is a descending chain.

For \((\mathrm{AC}) \implies (\mathrm{DC})\), let \(R \subseteq X \times X\) be total and let \(x_0 \in X\). Let \(g\) be a choice function for \(\pot X\) and define \((x_n)_{n \in \N}\) by recursion, \[ x_{n + 1} := g(\left\{ y \in X \mid x_n R y \right\}). \] This is well-defined, since \(\left\{ y \in X \mid x_n R y \right\} \neq \emptyset\) by totality of \(R\), and it satisfies \(x_n R x_{n + 1}\) for every \(n \in \N\).

First note that (CC) is equivalent to the statement that a countable product of nonempty sets is nonempty. Let us prove \((\mathrm{DC}) \implies \mathrm{CC}\). Suppose \((A_n)_{n \in \N}\) is a sequence of nonempty sets. Consider the relation on the set \(\sum\limits_{n \in N} A_n := \left\{ (n, x) \mid n \in \N, x \in A_n \right\}\). Then \[ (m, x)R(n, y) \iff n = m + 1 \] By (DC), \(\exists f : \N \rightarrow \sum\limits_{n \in \N} A_n\) such that \(f(0) = (0, x_0)\) and \(f(n) R f(n + 1)\). Then \[ \pi_2 \circ f \in \prod\limits_{n \in \N} A_n. \] Hence the product is nonempty.

First assume the axiom of choice. Suppose \[ R \subseteq \left( \bigcup\limits_{\beta < \alpha} X^{[\beta]} \right) \times X \] is total. Let \(g\) be a choice function for \(\pot(X)\). We define

By transfinite induction this satisfies the \(\mathrm{DC}_{\alpha}\) property.

Now suppose \(X\) is not well-orderable. Let \(\alpha = \underline{h}(X)\) be the Hartogs' ordinal. Define \(R \subseteq \left( \bigcup\limits_{\beta < \alpha} X^{[\beta]} \right) \times X\) by \[ (x_{\gamma})_{\gamma < \beta} R y \iff y \in X \setminus \left\{ x_{\gamma} \mid \gamma < \beta \right\}. \] Then \(R\) is total because for any \(\beta < \alpha\) there is no surjective \(x_{(-)} : [\beta] \rightarrow X\) because \(X\) is not well-orderable. By \(\mathrm{DC}_{\alpha}\) there exists a sequence \((x_{\beta})_{\beta < \alpha}\) satisfying the \(\mathrm{DC}_{\alpha}\) property. By transfinite infuction that property and the one defined here imply \((x_{(-)}) : [\alpha] \rightarrow X\) is injective. This contradicts that \(\alpha = \underline{h}(X)\) is the Hartogs' ordinal.

By assumption, for every \(i \in I\), there is an injection \(f_i : X_i \rightarrow Y_i\). Applying functorial actions to \((f_i : X_i \rightarrow Y_i)\), we get functions \(\sum\limits_{_{i\in I}} f_i : \sum\limits_{i\in I} X_i \rightarrow \sum\limits_{i\in I} Y_i\) and \(\prod\limits_{_{i\in I}} f_i : \prod\limits_{i\in I} X_i \rightarrow \prod\limits_{i\in I} Y_i\). It is easily checked that both functions are injective.

CSB. Explicitly, from \(\abs{X_i} = \abs{Y_i}\) we get both \(\abs{X_i} \leq \abs{Y_i}\) and \(\abs{Y_i} \leq \abs{X_i}\) for every \(i \in I\), so the proposition applied in both directions gives \(\abs{\sum\limits_{i\in I} X_i} \leq \abs{\sum\limits_{i\in I} Y_i}\) and \(\abs{\sum\limits_{i\in I} Y_i} \leq \abs{\sum\limits_{i\in I} X_i}\), and likewise for the products. Cantor-Schröder-Bernstein then turns each pair of inequalities into an equality.

We need to prove \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \lambda \cdot \kappa. \] where \(\kappa := \sup_{\alpha < \lambda} \kappa_{\alpha}\). We prove this by showing the two inequalities. Since \(\kappa_{\alpha} \leq \kappa\) we have \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \leq \sum\limits_{\alpha < \lambda}^{} \kappa = \lambda \cdot \kappa. \] by proposition.

We have \(\kappa_{\alpha} \leq \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha}\) so \(\kappa \leq \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha}\) because \(\kappa\) is a supremum. Also we have \(\lambda = \sum\limits_{\alpha < \lambda}^{} 1 \leq \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha}\) so we get \[ \lambda \cdot \kappa \leq \left( \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \right) \cdot \left( \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \right) = \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \] because \(\sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} \) is its own square.

Write \(\kappa = \sup_{\alpha < \lambda} \kappa_{\alpha}\). By the theorem, \(\sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \lambda \cdot \kappa\). Since \(\lambda\) is infinite and \(\lambda \leq \kappa\), also \(\kappa\) is infinite, so \[ \lambda \cdot \kappa = \max(\lambda, \kappa) = \kappa. \]

\[ \kappa = \sum\limits_{\alpha < \kappa}^{} 1 < \prod\limits_{\alpha < \kappa}^{} 2 = 2^{\kappa} \] where we use König's theorem for the strict inequality.

We prove the strict inequality by showing the nonstrict inequality and showing it is not equality.

We define an injective function

It's easily checked that this is injective.

We prove there is no bijection \(\sum\limits_{i \in I}^{} [\kappa_i] \cong \prod\limits_{i \in I}^{} [\lambda_i]\). Suppose for contradiction there is. Note that we can view the sum set as an \(I\)-indexed partition of the whole sum set. If we transport this via the bijection, we end up transporting the partition in the product. This would give us an isomorphism to a disjoint union \[ \prod\limits_{i \in I}^{} [\lambda_i] = \bigcup\limits_{i \in I}^{} X_i \] where \(X_i\) is the image of \(\left\{ i \right\} \times [\kappa_i]\) under the bijection.

For every \(i \in I\) the set \[ Y_i = \left\{ x_i \mid x_{(-)} \in X_i \right\} \subseteq [\lambda_i] \] Since \(x_{(-)} \mapsto x_i\) is a surjection from \(X_i \rightarrow Y_i\), we have \(\abs{Y_i} \leq \abs{X_i} = \kappa_i < \lambda_i\). Therefore \([\lambda_i] \setminus Y_i\) is nonempty, hence has a least element. Consider now the function \[ i \mapsto \text{the smallest ordinal in } [\lambda_i] \setminus Y_i. \] This is clearly in \(\prod\limits_{i \in I}^{} [\lambda_i]\). On the other hand it is not in any \(X_i\). This is a contradiction to the partition isomorphism.

For the first claim, take the constant family \(X_{\alpha} = [\kappa]\) indexed by \(\alpha < \lambda\). A choice function for this family is precisely a function \([\lambda] \rightarrow [\kappa]\), so \(\prod\limits_{\alpha < \lambda}^{} [\kappa]\) is the set of functions from \([\lambda]\) to \([\kappa]\), whose cardinality is \(\kappa^{\lambda}\).

For the first law, a function \(g\) from \([\lambda]\) into \(\prod\limits_{i \in I}^{} [\kappa_i]\) is the same thing as a family \((i \mapsto (\alpha \mapsto g(\alpha)_i))\) of functions \([\lambda] \rightarrow [\kappa_i]\), one for each \(i \in I\); swapping the two arguments is a bijection \(\left( \prod\limits_{i \in I}^{} [\kappa_i] \right)^{[\lambda]} \cong \prod\limits_{i \in I}^{} [\kappa_i]^{[\lambda]}\).

For the second law, a function \(f\) defined on the sum \(\sum\limits_{i \in I}^{} [\lambda_i]\) is determined by its restrictions \(\alpha \mapsto f(i, \alpha)\) to the summands, i.e. by a family of functions \([\lambda_i] \rightarrow [\kappa]\), and conversely. This is again a bijection, and taking cardinalities gives the law.

For (A), Cantor's theorem gives \(\aleph_{\alpha} < 2^{\aleph_{\alpha}}\). Using choice, \(2^{\aleph_{\alpha}}\) is itself an aleph, say \(2^{\aleph_{\alpha}} = \aleph_{\gamma}\). From \(\aleph_{\alpha} < \aleph_{\gamma}\) we get \(\alpha < \gamma\), hence \(\alpha + 1 \leq \gamma\) and therefore \(\aleph_{\alpha + 1} \leq \aleph_{\gamma} = 2^{\aleph_{\alpha}}\).

For (B), suppose \(\alpha \leq \beta\), so that \(\aleph_{\alpha} \leq \aleph_{\beta}\) and thus \(\aleph_{\alpha} + \aleph_{\beta} = \max(\aleph_{\alpha}, \aleph_{\beta}) = \aleph_{\beta}\). By the law for exponentiation over sums, \[ 2^{\aleph_{\beta}} = 2^{\aleph_{\alpha} + \aleph_{\beta}} = 2^{\aleph_{\alpha}} \cdot 2^{\aleph_{\beta}} \geq 2^{\aleph_{\alpha}}, \] since \(2^{\aleph_{\beta}} \geq 1\).

Write \(\gamma = \operatorname{cf}(\alpha)\) and let \((\alpha_{\beta})_{\beta < \gamma}\) be an increasing sequence with \(\alpha = \lim_{\beta \rightarrow \gamma} \alpha_{\beta}\). Note that every \(\alpha_{\beta} < \alpha\), since \(\alpha\) is a limit ordinal.

First, \(\gamma\) is infinite: if \(\gamma\) were finite, or more generally a successor \(\delta + 1\), then \(\alpha_{\delta}\) would be the largest term of the sequence, so \(\alpha = \sup_{\beta < \gamma} \alpha_{\beta} = \alpha_{\delta} < \alpha\), a contradiction.

Second, \(\gamma\) is initial. Suppose not, so that \(\abs{\gamma'} = \abs{\gamma}\) for some \(\gamma' < \gamma\), and fix a bijection \(f : [\gamma'] \rightarrow [\gamma]\). Consider the sequence \[ \delta \mapsto \sup_{\xi \leq \delta} \alpha_{f(\xi)} \quad (\delta < \gamma'). \] It is nondecreasing, and its supremum is \(\sup_{\beta < \gamma} \alpha_{\beta} = \alpha\) because \(f\) is onto. Discarding the repetitions leaves an increasing sequence with the same limit \(\alpha\), necessarily of limit length \(\gamma'' \leq \gamma' < \gamma\). This contradicts the minimality of \(\gamma = \operatorname{cf}(\alpha)\).

So \(\operatorname{cf}(\alpha)\) is an infinite initial ordinal, i.e. an \(\aleph\).

By the definition of cofinality, we have \(\kappa = \lim_{\alpha \rightarrow \operatorname{cf}(\kappa)} \beta_{\alpha}\) where \((\beta_{\alpha})_{\alpha < \operatorname{cf}(\kappa)}\) is an increasing sequence. If we look at all the ordinals between \(\beta_i\) and \(\beta_{i+1}\), we can partition \([\kappa]\) as the disjoint union \[ [\kappa] = \biguplus_{\alpha < \operatorname{cf}(\kappa)} \left( [\beta_{\alpha}] \setminus \bigcup\limits_{\alpha' < \alpha}^{} [\beta_{\alpha'}] \right) = \biguplus\limits_{\alpha < \operatorname{cf}(\kappa)}^{} B_{\alpha} \] Each \(B_{\alpha}\) is a subset of \([\beta_{\alpha}]\) and \(\abs{B_{\alpha}} \leq \abs{\beta_{\alpha}} < \kappa\). Since this is a disjoint union, we have \[ \kappa = \abs{\biguplus\limits_{\alpha < \operatorname{cf}(\kappa)}^{} B_{\alpha}} = \sum\limits_{\alpha < \operatorname{cf}(\kappa)}^{} \abs{B_{\alpha}} \] So \(\kappa = \sum\limits_{\alpha < \operatorname{cf}(\kappa)}^{} \abs{B_{\alpha}}\) and each \(\abs{B_{\alpha}} < \kappa\).

We need to show \(\operatorname{cf}(2^{\aleph_{\alpha}}) > \aleph_{\alpha}\). By the lemma, we have that \[ 2^{\aleph_{\alpha}} = \sum\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} \kappa_{\beta} \] where every \(\kappa_{\beta} < 2^{\aleph_{\alpha}}\). By König's theorem we have \[ 2^{\aleph_\alpha} = \sum\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} \kappa_{\beta} < \prod\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} 2^{\aleph_{\alpha}} = \left( 2^{\aleph_{\alpha}} \right)^{\operatorname{cf}(2^{\aleph_{\alpha}})} \]

Suppose for contradiction that we \(\operatorname{cf}(2^{\aleph_{\alpha}}) \leq \aleph_{\alpha}\). Then we continue the inequality chain above as \[ 2^{\aleph_\alpha} = \sum\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} \kappa_{\beta} < \prod\limits_{\beta < \operatorname{cf}(2^{\aleph_{\alpha}})}^{} 2^{\aleph_{\alpha}} = \left( 2^{\aleph_{\alpha}} \right)^{\operatorname{cf}(2^{\aleph_{\alpha}})} \leq \left( 2^{\aleph_{\alpha}} \right)^{\aleph_{\alpha}} = 2^{\aleph_{\alpha} \cdot \aleph_{\alpha}} = 2^{\aleph_{\alpha}}. \] We proved \(2^{\aleph_{\alpha}} < 2^{\aleph_{\alpha}}\) which is a contradiction.

1. The sequence \((\beta)_{\beta < \alpha}\) is increasing with \(\lim_{\beta \rightarrow \alpha} \beta = \alpha\), so \(\operatorname{cf}(\alpha) \leq \alpha\) by minimality of the cofinality.
2. If \(\alpha\) is not an initial ordinal, then \(\abs{\alpha} < \alpha\), so there is a bijection \(f : [\abs{\alpha}] \rightarrow [\alpha]\). Its image is all of \([\alpha]\) and in particular cofinal in \(\alpha\). Recursively discarding every \(f(\gamma)\) which does not exceed all the previous ones, we thin \(f\) out to an increasing sequence with limit \(\alpha\) of length at most \(\abs{\alpha}\). Hence \(\operatorname{cf}(\alpha) \leq \abs{\alpha} < \alpha\).
3. Applying 1 to \(\operatorname{cf}(\alpha)\) gives \(\operatorname{cf}(\operatorname{cf}(\alpha)) \leq \operatorname{cf}(\alpha)\). Conversely, take \((\gamma_{\delta})_{\delta < \operatorname{cf}(\operatorname{cf}(\alpha))}\) increasing with limit \(\operatorname{cf}(\alpha)\), and \((\beta_{\gamma})_{\gamma < \operatorname{cf}(\alpha)}\) increasing with limit \(\alpha\). The composite \((\beta_{\gamma_{\delta}})_{\delta < \operatorname{cf}(\operatorname{cf}(\alpha))}\) is again increasing, and since the \(\gamma_{\delta}\) are cofinal in \(\operatorname{cf}(\alpha)\), its limit is \(\alpha\). So \(\operatorname{cf}(\alpha) \leq \operatorname{cf}(\operatorname{cf}(\alpha))\).

It follows from points 2 and 3 in the cofinality lemma.

Suppose for contradiction that \(\aleph_{\alpha + 1}\) is singular. By lemma B, we have that \[ \aleph_{\alpha + 1} = \sum\limits_{i \in I}^{} \kappa_i \] where \(\abs{I}, \kappa_i < \aleph_{\alpha + 1}\). So \(\abs{I}\) and \(\kappa_i \leq \aleph_{\alpha}\) and \[ \aleph_{\alpha + 1} \leq \sum\limits_{\beta < \aleph_{\alpha}}^{} \aleph_{\alpha} = \aleph_{\alpha} \cdot \aleph_{\alpha} = \aleph_{\alpha}. \] So \(\aleph_{\alpha + 1} \leq \aleph_{\alpha}\), which is a contradiction. Hence \(\aleph_{\alpha + 1}\) is regular.

To show \((1) \implies (2)\), consider the limit \(\sup \left\{ \alpha \in \Ord \mid \operatorname{vN}(\alpha) \in \mathcal{U} \right\}\). This is a strongly inaccessible cardinal. Write \(\kappa\) for it. It is uncountable, since an infinite \(X \in \mathcal{U}\) already forces \(\operatorname{vN}(\omega) \in \mathcal{U}\). It is a strong limit, since \(\mathcal{U}\) is closed under powersets. And it is regular, since \(\mathcal{U}\) is closed under \(\mathcal{U}\)-indexed unions, so no family of fewer than \(\kappa\) many ordinals below \(\kappa\) can be cofinal in \(\kappa\).

On the other hand, if \(\kappa\) is strongly inaccessible, then \(V_{\kappa}\) is a Grothendieck universe. Indeed, \(V_{\kappa}\) is transitive and closed under unordered pairs because \(\kappa\) is a limit ordinal, it is closed under powersets because \(\kappa\) is a strong limit cardinal, and it is closed under indexed unions because \(\kappa\) is regular.

• Monotonicity is by transfinite induction on \(\beta\), using that every \(V_{\alpha}\) is transitive, so \(V_{\alpha} \subseteq \pot V_{\alpha} = V_{\alpha + 1}\).
• The cardinality of \(V_n\) follows from \(\abs{V_0} = 0\) and \(\abs{V_{n + 1}} = 2^{\abs{V_n}}\).
• Every \(V_n\) is therefore finite, so every element of \(V_{\omega}\) is hereditarily finite; conversely every hereditarily finite set lands in some \(V_n\) by induction on its elements.
• \(\operatorname{vN}(\alpha) \in V_{\alpha + 1}\) is again transfinite induction: \(\operatorname{vN}(\alpha) = \left\{ \operatorname{vN}(\beta) \mid \beta < \alpha \right\} \subseteq V_{\alpha}\), so \(\operatorname{vN}(\alpha) \in \pot V_{\alpha} = V_{\alpha + 1}\).
• If \(X \in V_{\alpha}\), then \(X \subseteq V_{\beta}\) for some \(\beta\) with \(\beta + 1 \leq \alpha\), so \(\pot X \subseteq \pot V_{\beta} = V_{\beta + 1} \subseteq V_{\alpha}\), giving \(\pot X \in V_{\alpha + 1}\).

Granting Theorems 2 and 3 below, let \(A \subseteq \R\) be closed. If \(A\) is countable, then \(\abs{A}\) is finite or \(\aleph_0\). If \(A\) is uncountable, then by Theorem 2 it contains a perfect subset \(P \subseteq A\), and by Theorem 3 we have \(\abs{P} = 2^{\aleph_0}\). Hence \[ 2^{\aleph_0} = \abs{P} \leq \abs{A} \leq \abs{\R} = 2^{\aleph_0}, \] so \(\abs{A} = 2^{\aleph_0}\) by Cantor–Schröder–Bernstein.

Both \(A \cap [a, \infty)\) and \(A \cap (a, \infty)\) contain \(x\), so both are nonempty. Moreover, no \(y \in A\) with \(y > a\) is isolated in either of them: \(y\) is not isolated in \(A\), and every point of \(A\) close enough to \(y\) is again \(> a\).

Now \(A \cap [a, \infty)\) is an intersection of two closed sets, hence closed, so by the above the only point at which it can fail to be perfect is \(a\) itself. So suppose it is not perfect. Then \(a \in A\) and \(a\) is isolated in it, i.e. there is an \(\varepsilon > 0\) with \((a, a + \varepsilon) \cap A = \emptyset\). But then \[ A \cap (a, \infty) = A \cap [a + \varepsilon, \infty) \] is closed, and it is nonempty with no isolated points by the above, hence perfect.

We construct a family of bounded perfect subsets of \(A\), namely \((A_w)_{w \in \left\{ 0, 1 \right\}}^{ * }\). Then \[ A_{\varepsilon} = \text{ some bounded subset of } A \text{ obtained using lemma}. \] Suppose we have \(A_w\). We define \(a = \min(A_w)\) and \(b = \max(A_w)\). Then we get \[ A_{w0} =\begin{cases} [a, \frac{2}{3} a + \frac{1}{3}b] \cap A_w & \text{ if perfect} [a, \frac{2}{3} a + \frac{1}{3}b) \cap A_w & \text{otherwise} \end{cases} \] and \[ A_{w1} = \begin{cases} [a, \frac{1}{3} a + \frac{2}{3}b] \cap A_w & \text{ if perfect} [a, \frac{1}{3} a + \frac{2}{3}b) \cap A_w & \text{otherwise} \end{cases} \] Define \[ A_{\infty} = \bigcap\limits_{n \in \N}^{} \bigcup\limits_{\overset{\left\{ 0, 1 \right\}^{ * }}{\abs{w} = n}}^{} A_w. \] This works by the same arguments as for the Cantor set \(\abs{A_{\infty}} = 2^{\aleph_0}\).

For every closed set \(A\) define \[ A' = A \setminus \left\{ x \in A \mid x \text{ isolated in } A \right\} \] It follows that \(A'\) is again closed.

To construct our perfect subset, let's define

But even \(A_{\omega}\) might still have some isolated points. So instead we consider transfinite induction

Then we can define \[ A_{\infty} = \bigcap\limits_{\alpha \in \Ord}^{} A_{\alpha}. \]

Let us define \(F_\alpha = A_{\alpha} \setminus A_{\alpha + 1}\), i.e. the isolated points in \(A_{\alpha}\). Likewise, since the \(F_\alpha\) are pairwise disjoint, \[ F = \biguplus\limits_{\alpha \in \Ord}^{} F_\alpha. \] Then \(F\) is a countable set (which will let \(A_{\infty}\) remain uncountable). To see this, consider a function \(f : F \rightarrow I\) where \(I = \left\{ (p, q)\in \Q \times \Q \mid p < q \right\}\) where that \(f\) maps \[ y \in F_{\alpha} \mapsto \text{ some interval} (p_y, q_y) \text{ such that } (p_y, q_y) \cap A_\alpha = \left\{ y \right\}. \] This does not require choice since we can always map to the smallest such interval. This function is injective. Hence \(F\) is countable.

If for all \(\alpha < \omega_1\), \(F_{\alpha}\) were nonempty, then \[ \bigcup\limits_{\alpha <\omega_1}^{} F_{\alpha} \] would be uncountable. So \[ \exists \gamma < \omega_1 \text{ such that } F_{\gamma} = \emptyset. \] Let \(\gamma\) be the smallest such. But this means that \(A_\gamma' = A_{\gamma}\), in particular \(A_{\gamma}\) has no isolated points. This means for all \(\beta > \gamma\), we still have \(A_{\beta} = A_{\gamma}\).

This means that \(A_{\infty} = A_{\gamma}\) is closed. It has no isolated points. Because we started with an uncountable set \(A\) and removed a countable subset, our \(A \setminus F\) is still uncountable and in particular nonempty.

This means that \(A \setminus F\) is the perfect set we are looking for.

1. Given \(A \in \Sigma_{\alpha}\), take the constant family \(A_n = A\) for every \(n \in \N\). Then \(A = \bigcap_n A_n\) is a countable intersection of sets in \(\Sigma_{\alpha}\), so \(A \in \Pi_{\alpha + 1}\). Dually, the constant countable union witnesses \(\Pi_{\alpha} \subseteq \Sigma_{\alpha + 1}\).
2. It is enough to show \(\Sigma_{\alpha} \subseteq \Sigma_{\alpha + 1}\) and \(\Pi_{\alpha} \subseteq \Pi_{\alpha + 1}\) for every \(\alpha\), since the limit stages absorb all earlier ones by definition (a set of \(\Sigma_{\alpha}\), \(\alpha < \lambda\), is a constant countable union of sets from stages below \(\lambda\), hence in \(\Sigma_{\lambda}\)). For the base case: in a metric space every open \(U\) is a countable union of closed sets, \[ U = \bigcup\limits_{n \in \N}^{} \left\{ x \in X \mid d(x, X \setminus U) \geq \tfrac{1}{n} \right\}, \] so \(\Sigma_1 \subseteq \Sigma_2\), and \(\Pi_1 \subseteq \Pi_2\) by complements. The induction step is then immediate: if \(\Pi_{\alpha} \subseteq \Pi_{\alpha + 1}\), then a countable union of \(\Pi_{\alpha}\) sets is a countable union of \(\Pi_{\alpha + 1}\) sets, i.e. \(\Sigma_{\alpha + 1} \subseteq \Sigma_{\alpha + 2}\), and dually.
3. and 4. are proved simultaneously by transfinite induction on \(\alpha\). For 4. it suffices to note that \(X \setminus \bigcup_n A_n = \bigcap_n (X \setminus A_n)\) and dually, so complementation exchanges the two clauses of the definition. For 3., a countable union of countable unions is again a countable union, which gives closure of \(\Sigma_{\alpha}\) under countable unions; for finite intersections use distributivity, \[ \left( \bigcup_n B_n \right) \cap \left( \bigcup_m C_m \right) = \bigcup_{n, m} (B_n \cap C_m), \] together with the induction hypothesis for \(\Pi_{\alpha}\), and then read off the statement for \(\Pi_{\alpha}\) using 4.
4. Since \(\operatorname{cf}(\omega_1) = \omega_1\), every countable family of ordinals below \(\omega_1\) is bounded by some \(\alpha < \omega_1\). Hence, by 2., every countable family of sets from \(\Sigma_{\omega_1}\) already lies in a single \(\Sigma_{\alpha}\) with \(\alpha < \omega_1\), and its union and its intersection are then in \(\Sigma_{\alpha + 1}\) and \(\Pi_{\alpha + 1}\), so again in \(\Sigma_{\omega_1}\) by 2. So \(\Sigma_{\omega_1}\) is closed under countable unions, countable intersections and (by 4.) complements, which gives \(\Sigma_{\omega_1} = \Pi_{\omega_1}\) and, applying the definition once more, \(\Sigma_{\omega_1 + 1} = \Sigma_{\omega_1}\). The hierarchy is therefore constant from \(\omega_1\) on.

• \(B \subseteq \Sigma_{\omega_1}\) by the definition of \(B\)
• \(\Sigma_{\omega_1} \subseteq B\) is proved by taking \(\Sigma_{\alpha} \subseteq B\) by transfinite induction.

We cannot induct along the hierarchy directly, so we reduce to the closed case in \(\N^{\N}\). By transfinite induction on \(\alpha < \omega_1\) one shows that every Borel set \(B \subseteq X\) is the image of a closed set \(C \subseteq \N^{\N}\) under a continuous injection \(f : C \rightarrow X\).

Let now \(B\) be uncountable. Then \(C\) is uncountable as well, since \(f\) is a bijection onto \(B\). As \(\N^{\N}\) is Polish and \(C\) is closed in it, Theorem 2 gives a perfect \(P \subseteq C\), and running the construction of Theorem 3 inside \(P\) with the diameters of the pieces shrinking to \(0\) produces a copy \(K \subseteq P\) of the Cantor set: \(K\) is compact, nonempty and has no isolated points. Being a continuous injection on a compact set, \(f\) restricted to \(K\) is a homeomorphism onto its image, so \(f(K) \subseteq B\) is again compact, hence closed, nonempty and without isolated points. So \(f(K)\) is a perfect subset of \(B\).

We prove by transfinite induction that for all \(\alpha\) we have \(\abs{\Sigma_{\alpha}} \leq 2^{\aleph_0}\) and \(\Pi_{\alpha} \leq 2^{\aleph_0}\).

For the base case \(\alpha = 1\), separability gives a countable base \((U_n)_{n \in \N}\) of the topology of \(X\), and every open set is a union of basic opens, so we have a surjection \(\pot(\N) \rightarrow \Sigma_1\) and hence \(\abs{\Sigma_1} \leq 2^{\aleph_0}\). Complementation is a bijection \(\Sigma_1 \rightarrow \Pi_1\), so \(\abs{\Pi_1} \leq 2^{\aleph_0}\) too.

For the step case \(\alpha + 1\), note that we have a surjection \(\Pi_{\alpha}^{\N} \xrightarrow{\cup} \Sigma_{\alpha + 1}\) so \[ \abs{\Sigma_{\alpha + 1}} \leq \Pi_{\alpha^{\N}} \leq (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}. \] The bound for \(\Pi_{\alpha + 1}\) is the same, by complementation.

For a limit \(\lambda \leq \omega_1\), every set of \(\Sigma_{\lambda}\) is a countable union of sets taken from \(\bigcup\limits_{\alpha < \lambda}^{} \Pi_{\alpha}\), and by the induction hypothesis \[ \abs{\bigcup\limits_{\alpha < \lambda}^{} \Pi_{\alpha}} \leq \abs{\lambda} \cdot 2^{\aleph_0} = 2^{\aleph_0}, \] so the same surjection argument as in the step case gives \(\abs{\Sigma_{\lambda}} \leq (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}\), and dually for \(\Pi_{\lambda}\).

Since \(B = \Sigma_{\omega_1}\), this proves \(\abs{B} \leq 2^{\aleph_0}\). Conversely every singleton \(\left\{ x \right\}\) is closed, hence Borel, so \(\abs{B} \geq \abs{\R} = 2^{\aleph_0}\). By Cantor–Schröder–Bernstein, \(\abs{B} = 2^{\aleph_0}\).

There are \(2^{\aleph_0}\)-many perfect sets. We can enumerate all perfect sets \((P_{\alpha})_{\alpha < 2^{\aleph_0}}\), treating \(2^{\aleph}\) itself as an aleph. Proceed by transfinite recursion. Set \(A_0, B_0 := \emptyset\) and set\(A_{\alpha + 1}, B_{\alpha + 1}\) by choosing \[ a_{\alpha} \neq b_{\alpha} \in P_{\alpha} \setminus \bigcup\limits_{\beta \leq \alpha}^{} (A_{\beta} \cup B_\beta). \] Such a choice is possible: \(P_{\alpha}\) is perfect, so \(\abs{P_{\alpha}} = 2^{\aleph_0}\) by last week's theorem, whereas \[ \abs{\bigcup\limits_{\beta \leq \alpha}^{} (A_{\beta} \cup B_{\beta})} \leq \abs{\alpha} \cdot 2 < 2^{\aleph_0}, \] so the set we are choosing from still has cardinality \(2^{\aleph_0}\), and in particular contains two distinct points. Having chosen them, we set \(A_{\alpha + 1} := A_{\alpha} \cup \left\{ a_{\alpha} \right\}\) and \(B_{\alpha + 1} := B_{\alpha} \cup \left\{ b_{\alpha} \right\}\), and \[ A_{\lambda} := \bigcup\limits_{\alpha < \lambda}^{} A_{\alpha}, \quad B_{\lambda} := \bigcup\limits_{\alpha < \lambda}^{} B_{\alpha}. \] By transfinite induction we prove that \(A_{\alpha} \cap B_{\alpha} = \emptyset\) and \(\abs{A_{\alpha} = \abs{B_{\alpha}} = \abs{\alpha}}\).

Define \[ A = \bigcup\limits_{\alpha < 2^{\aleph_0}}^{} A_{\alpha}. \] Since the \(a_{\alpha}\) are pairwise distinct, \(\abs{A} = 2^{\aleph_0}\), so \(A\) is uncountable. Writing \(B = \bigcup\limits_{\alpha < 2^{\aleph_0}}^{} B_{\alpha}\), the induction above gives \(A \cap B = \emptyset\).

A then does not contain any perfect subset because for any \(\alpha < 2^{\aleph_0}\) since \(b_{\alpha} \in P_\alpha\), but we have \(b_{\alpha} \not\in A\). Indeed \(b_{\alpha} \in B_{\alpha + 1} \subseteq B\), and \(A \cap B = \emptyset\). So \(b_{\alpha} \in P_{\alpha} \setminus A\) and hence \(P_{\alpha} \not\subseteq A\). As every perfect subset of \(\R\) appears as some \(P_{\alpha}\) in the enumeration, \(A\) is an uncountable set with no perfect subset.

Consider the first point's \((\impliedby)\). Suppose \(X\) has a(n initial) perfect subset \(P_0 \subseteq \R\), then \(I\) plays as follows. Given \(A_{n-1} \supseteq P_{n - 1}\). Using the properties from last week we find \(p < q < p' < q'\) such that

• \([p, q]\) contains a perfect subset \(L \subseteq P_{n-1}\),
• \([p', q']\) contains a perect subset \(R \subseteq P_{n-1}\),

and both \(q - p < \frac{1}{2^n}\) and \(q' - p' < \frac{1}{2^n}\). If player II chooses 0, we take \(P_n = L\), if 1, take \(P_n = R\).

Player I wins because \[ \bigcap\limits_n^{} A_n = \bigcap\limits_{n }^{} P_n \subseteq X. \]

Consider the first point's \((\implies)\). Suppose \(\sigma\) is a winning strategy for player I. For a word \(w \in \left\{ 0, 1 \right\}^{ * }\) let \(A_w\) be the interval reached when player I follows \(\sigma\) and player II answers with the bits of \(w\), one in each round. By the rules of the game \(A_{w0}\) and \(A_{w1}\) are disjoint closed subintervals of \(A_w\), each of length \(< \frac{1}{2^{\abs{w} + 1}}\). Hence for every \(b \in \left\{ 0, 1 \right\}^{\N}\) the intersection \[ \bigcap\limits_{n \in \N}^{} A_{b(0) \cdots b(n - 1)} \] is a single point, which we call \(f(b)\), and \(f(b) \in X\) because \(\sigma\) is winning for player I. The map \(f\) is injective: if \(b \neq b'\) differ first at place \(n\), then \(f(b)\) and \(f(b')\) lie in the disjoint intervals \(A_{b(0)\cdots b(n)}\) and \(A_{b'(0) \cdots b'(n)}\). It is also continuous: if \(b\) and \(b'\) agree on their first \(n\) bits, then \(f(b), f(b') \in A_{b(0)\cdots b(n-1)}\), so \(\abs{f(b) - f(b')} < \frac{1}{2^n}\). Let \(P\) be the image of \(f\). Then \(P \subseteq X\), and \(P\) is nonempty and closed, being the continuous image of the compact space \(\left\{ 0, 1 \right\}^{\N}\). It has no isolated points, because every neighbourhood of \(f(b)\) contains \(f(b')\) for all \(b' \neq b\) agreeing with \(b\) on a long enough initial segment. So \(P\) is a perfect subset of \(X\). Note that no choice was needed here, as \(\sigma\) tells us how player I moves.

Consider the second point's \((\impliedby)\). Suppose \(X = \left\{ x_1, x_2, \dots \right\}\) is a countable set. Player II has the following strategy. At round \(n\), given player I's move \(p < q < p' < q'\), II chooses 0 if \(x_n \not\in [p, q]\) and 1 otherwise.

Now suppose player II has a winning strategy. We want to show \(X\) is countable. Let \(x \in X\) be arbitrary. Player I tries to force the play to \(\left\{ x \right\}\) as follows. Assuming we're at round \(n\)with \(x \in A_{n - 1}\) if possible we choose \(p_n < q_n < p'_n < q_n'\) such that after II's response we have \(x \in A_n\). Otherwise, we give up on \(x\) at position \(p_1 < q_1 < p'_1 < q'_1, \dots, p_{n-1} < q_{n - 1} < p'_{n - 1} < q'_{n - 1}.\)

Suppose we give up on \(x\) and \(y\) at position \(m_1, \dots, m_{n-1}\). This means \(x, y \in A_{n-1}\). Suppose \(x < y\). We choose \(p_n < q_n < p'_n < q'_n\) such that \(x \in [p_n, q_n]\) and \(y \in [p'_n, q'_n]\).

At any position in our play we give up on at most one element of \(X\). For every element \(x \in X\), there exists a position on which we give up on \(x\). Indeed, if player I could keep \(x \in A_n\) at every round \(n\), then the play would end with \(\bigcap\limits_n^{} A_n = \left\{ x \right\}\) and \(x \in X\), so player I would win a play in which player II followed their strategy, contradicting that this strategy is winning. \(X\) is then countable because there are only countably many positions. A position is a finite sequence of rationals together with player II's answers, and there are only countably many of those. The assignment of \(x\) to the position at which we give up on it is therefore an injection of \(X\) into a countable set.

Suppose \(G \subseteq \N^{\N}\) is closed. We say that a player has a winning strategy from a position \(w \in \N^{ * }\) if they have a winning strategy in the game whose plays are those beginning with the moves of \(w\). Define \(\sigma_\mathrm{I}(w)\) for an even-length word as \[ \sigma_\mathrm{I}(w) = \begin{cases} n & \text{ if such an } n \text{ exists}\\ 0 & \text{otherwise} \end{cases} \] where \(n\) is the smallest number such that II does not have a winning strategy from \(w_n\) if such an \(n\) exists. The idea is that player I keeps the play in positions from which player II cannot win.

We will prove that if II does not have a winning strategy, then \(\sigma_{\mathrm{I}}\) is winning for 1.

Suppose II does not have a winning strategy. Let \(s = s_0s_1s_2\cdots\) be any play following \(\sigma_{\mathrm{I}}\). We need to prove \(s \in G\). Proceed by induction on \(n\) that II does not have a winning strategy from \(s_0\cdots s_{n-1}\).

If \(n = 0\), our prefix word is empty, so II does not have a winning strategy by assumption. If \(n > 0\) and \(n\) is odd, so \(s_0, \dots, s_{n-1}\) is even, it's I's move, so the property holds by definition. For this we need to know that at the position \(s_0 \cdots s_{n-2}\) a move as in the definition of \(\sigma_{\mathrm{I}}\) exists at all. And it does: if II had a winning strategy from \(s_0 \cdots s_{n-2}m\) for every move \(m \in \N\), then II would have a winning strategy from \(s_0\cdots s_{n-2}\) as well, namely wait for I to play some \(m\) and then follow the corresponding strategy. (Collecting these into one strategy is an appeal to countable choice. One avoids it by replacing strategies with the quasi-strategy that allows player I every move keeping the position non-losing, but we will not fuss over this.) If \(n\) is even, it's II's move. Since they don't currently have a winning strategy, this is preserved by any continuation. For if II had a winning strategy from \(s_0\cdots s_{n-1}\), then playing \(s_{n-1}\) and continuing with it would be a winning strategy from \(s_0 \cdots s_{n-2}\).

There is a sequence of winning plays for I.

Here \(t^{(n)}\) is a continuation of the position \(s_0 \cdots s_{n-1}\) with \(s_0 \cdots s_{n-1}t^{(n)} \in G\), and such a continuation has to exist: if every play extending \(s_0\cdots s_{n-1}\) were outside \(G\), then any strategy whatsoever would be winning for II from \(s_0 \cdots s_{n-1}\), and we have just shown that II has no winning strategy there.

Then this is a Cauchy sequence in \(G\). Since \(G\) is closed, its limit is also in \(G\). Its limit is \(s\), because \(s_0\cdots s_{n-1}t^{(n)}\) agrees with \(s\) in its first \(n\) entries, so that \[ d(s_0 \cdots s_{n-1}t^{(n)}, s) \leq \frac{1}{2^n}. \] Hence \(s \in G\), which is what we had to prove.

So either II has a winning strategy, or II has none and then \(\sigma_{\mathrm{I}}\) is a winning strategy for I. In both cases \(G\) is determined.

Let \(I\) be maximal. Then \(I\) is proper, so \(1 \not\in I\). Suppose \(p \cdot q \in I\) and \(p \not\in I\). Consider \[ J := \left\{ x + r \cdot p \mid x \in I,\, r \in R \right\}. \] This is an ideal, it contains \(I\) (take \(r = 0\)) and it contains \(p\) (take \(x = 0, r = 1\)), so \(I \subsetneq J\). By maximality of \(I\), \(J\) is not proper, so \(1 \in J\), say \(1 = x + r \cdot p\) with \(x \in I\) and \(r \in R\). Multiplying by \(q\), \[ q = q \cdot x + r \cdot (p \cdot q) \in I, \] since \(x \in I\) and \(p \cdot q \in I\). So \(q \in I\), and \(I\) is prime.

We prove the theorem using Zorn's lemma. Consider the set \(P := \left\{ K \mid K \text{ is a proper ideal and } K \supseteq I \right\}\). Partially order \(P\) by \(\subseteq\). It is easily checked that the conditions of ZL are satisfied. Indeed \(P \neq \emptyset\), since \(I \in P\). And if \(C \subseteq P\) is a nonempty chain, then \(\bigcup C\) is an ideal: \(0 \in \bigcup C\); if \(x, y \in \bigcup C\), then \(x, y\) lie in a common \(K \in C\) because \(C\) is a chain, so \(x + y \in K \subseteq \bigcup C\); and if \(x \in K \in C\) and \(y \in R\), then \(x \cdot y \in K\). It is proper, since \(1 \not\in K\) for every \(K \in C\), and it contains \(I\). So \(\bigcup C \in P\) is an upper bound for \(C\). By Zorn's lemma, \(P\) has a maximal element. Call it \(J\), so \(J\) is a proper ideal with \(J \supseteq I\). If \(J \subseteq J'\) with \(J'\) proper, then \(J' \supseteq I\), so \(J' \in P\), and \(J' = J\) by maximality of \(J\) in \(P\). So \(J\) is a maximal ideal extending \(I\).

Suppose 1 holds. Recall that in any lattice we have the absorption laws \(a \lor (a \land c) = a\) and \((a \lor b) \land a = a\). So

which is 2. The implication from 2 to 1 is the same argument with \(\land\) and \(\lor\) interchanged.

Note first that in any boolean ring \(x + x = 0\), since \[ x + x = (x + x) \cdot (x + x) = x + x + x + x. \] So \(-1 = 1\), and \(a + b - a \cdot b = a + b + a \cdot b\).

For 1, the operation \(\oplus\) is commutative and associative with \(a \oplus \bot = a\), and \(a \oplus a = (a \land a^{c}) \lor (a^{c} \land a) = \bot\), so \((P, \oplus, \bot)\) is an abelian group in which every element is its own inverse. Meets are commutative, associative and idempotent with unit \(\top\), and \(a \land (b \oplus c) = (a \land b) \oplus (a \land c)\) by distributivity of the lattice. So \(P\) becomes a boolean ring.

For 2, the relation \(a \leq b :\iff a \cdot b = a\) is reflexive by idempotence, antisymmetric because \(a = a \cdot b = b \cdot a = b\), and transitive because \(a \cdot c = (a \cdot b) \cdot c = a \cdot (b \cdot c) = a \cdot b = a\). With respect to it \(0\) is least and \(1\) is greatest, \(a \cdot b\) is the meet of \(a\) and \(b\), and \(a + b + a \cdot b\) is their join. Moreover \(1 + a\) is a complement of \(a\), since \[ a \land (1 + a) = a + a \cdot a = a + a = 0 \] and \[ a \lor (1 + a) = a + (1 + a) + a \cdot (1 + a) = 1 + (a + a) + (a + a) = 1, \] and distributivity is a direct calculation with the ring operations. So \(P\) becomes a boolean algebra.

For 3, going from an algebra to a ring and back returns \(a \land b = a \cdot b\) and \(a^{c} = 1 + a\), i.e. the original meet and complement, hence the original order. Going from a ring to an algebra and back returns \[ a \oplus b = (a \land b^{c}) \lor (a^{c} \land b) = a \cdot (1 + b) + (1 + a) \cdot b + a \cdot (1 + b) \cdot (1 + a) \cdot b = a + b, \] since \(a \cdot (1 + a) = a + a = 0\) kills the last term. So the two constructions are mutually inverse.

For 4, a ring homomorphism preserves \(\cdot = \land\) and \(1 = \top\), and \(f(a^{c}) = f(1 + a) = 1 + f(a) = f(a)^{c}\), so it preserves complements and hence, by de Morgan, joins. Conversely a boolean algebra homomorphism preserves \(\land = \cdot\) and \(\top = 1\), and it preserves \(\oplus = +\) because \(\oplus\) is defined from meets, joins and complements.

Throughout we use the ring structure \(0 = \bot\), \(1 = \top\), \(a \cdot b = a \land b\) and \(a + b = a \oplus b\) from the previous theorem.

Suppose \(I\) is an ideal of the ring. Then \(\bot = 0 \in I\). If \(a \in I\) and \(b \in P\), then \(a \land b = a \cdot b \in I\), which gives 3. If \(a, b \in I\), then \(a \lor b = a + b + a \cdot b \in I\), which gives 2.

Conversely, suppose 1, 2 and 3 hold. Then \(0 = \bot \in I\). If \(a \in I\) and \(b \in P\), then \(a \cdot b = a \land b \in I\) by 3. If \(a, b \in I\), then \(a \lor b \in I\) by 2, and \(a + b \leq a \lor b\), so \(a + b \in I\) by down-closedness.

For the two formulations of 3: if \(I\) is down-closed and \(a \in I\), \(b \in P\), then \(a \land b \leq a\), so \(a \land b \in I\); conversely if 3 holds and \(b \leq a \in I\), then \(b = a \land b \in I\).

Finally, \(I\) is proper iff \(1 = \top \not\in I\), which is the ring condition, and the ring condition for primality, \(a \cdot b \in I \implies (a \in I \lor b \in I)\), is exactly \(a \land b \in I \implies (a \in I \lor b \in I)\).

We show \(1 \implies 3 \implies 2 \implies 1\).

Suppose \(I\) is maximal, so in particular proper, and let \(a \in P\). If \(a \in I\) we are done, so suppose \(a \not\in I\) and consider \[ J := \left\{ x \in P \mid x \leq a \lor i \text{ for some } i \in I \right\}, \] which is an ideal containing \(I\) and \(a\), so \(I \subsetneq J\). By maximality \(J\) is not proper, so \(\top \in J\), i.e. \(a \lor i = \top\) for some \(i \in I\). Then \[ a^{c} = a^{c} \land (a \lor i) = (a^{c} \land a) \lor (a^{c} \land i) = a^{c} \land i \leq i, \] so \(a^{c} \in I\) by down-closedness. This gives 3.

Now suppose 3, and let \(a \land b \in I\) with \(a \not\in I\), so \(a^{c} \in I\). Then \[ b = b \land \top = b \land (a \lor a^{c}) = (b \land a) \lor (b \land a^{c}) \in I, \] since \(b \land a \in I\) by assumption and \(b \land a^{c} \in I\) by down-closedness. As \(I\) is proper, it is prime.

Finally suppose \(I\) is prime, and let \(J \supseteq I\) be a proper ideal with some \(a \in J \setminus I\). Since \(a \land a^{c} = \bot \in I\) and \(a \not\in I\), primality gives \(a^{c} \in I \subseteq J\). But then \(\top = a \lor a^{c} \in J\), contradicting properness of \(J\). So no such \(J\) exists and \(I\) is maximal.

Regard \(P\) as a boolean ring. By the previous proposition, \(I\) is a proper ideal of that ring, so by Krull's theorem it extends to a maximal ideal \(J \supseteq I\), which is prime by Proposition A.

This is Proposition A read upside down. Complementation \(a \mapsto a^{c}\) is an order-reversing bijection of \(P\) with itself, so \[ F \mapsto F^{c} := \left\{ a^{c} \mid a \in F \right\} \] is an inclusion-preserving bijection between the filters and the ideals of \(P\): \(\top \in F \iff \bot \in F^{c}\), and by de Morgan \((a \land b)^{c} = a^{c} \lor b^{c}\), so \(F\) is closed under binary meets iff \(F^{c}\) is closed under binary joins, and \(F\) is up-closed iff \(F^{c}\) is down-closed. Under this bijection \(F\) is proper iff \(F^{c}\) is proper, \(F\) is prime iff \(F^{c}\) is prime, \(F\) is ultra iff \(F^{c}\) satisfies condition 3 of Proposition A, and \(F\) is maximal iff \(F^{c}\) is maximal, since the bijection preserves inclusion in both directions. So the three conditions are equivalent by Proposition A.

By the bijection of the previous proposition, \(F^{c} = \left\{ a^{c} \mid a \in F \right\}\) is a proper ideal. By PIT there is a prime ideal \(J \supseteq F^{c}\), and then \(U := J^{c} = \left\{ a^{c} \mid a \in J \right\}\) is a prime, hence ultra, filter with \(U \supseteq F\). Conversely, the same translation derives PIT from the ultrafilter theorem.

For 1, suppose \(X\) is finite and let \(U\) be an ultrafilter on \(X\). Since \(\pot X\) is finite, \(A := \bigcap U\) is an intersection of finitely many elements of \(U\), so \(A \in U\). Also \(A \neq \emptyset\), since \(U\) is proper. Pick \(x \in A\). Then \(U \subseteq [x]\), because every \(S \in U\) contains \(A \ni x\). Conversely, if \(x \in S\) but \(S \not\in U\), then \(X \setminus S \in U\) as \(U\) is ultra, so \(A \subseteq X \setminus S\) and hence \(x \not\in S\), a contradiction. So \(U = [x]\) is principal.

Let us prove 2. We define \(K \subseteq \pot X\) by \[ K = \left\{ S \subseteq X \mid S \text{ is cofinite} \right\}. \] Here \(S\) being cofinite means that \(X \setminus S\) is finite.

Then \(K\) is a filter: \(X \in K\); if \(S, T \in K\), then \(X \setminus (S \cap T) = (X \setminus S) \cup (X \setminus T)\) is finite; and if \(S \in K\) and \(S \subseteq T\), then \(X \setminus T \subseteq X \setminus S\) is finite. It is proper, since \(X\) is infinite and so \(\emptyset \not\in K\). So the ultrafilter theorem applies. There exists an ultrafilter \(U \supseteq K\). We show \(U\) does not contain any singleton, hence is nonprincipal. Suppose for contradiction that \(\left\{ x \right\} \in U\). Then \(X \setminus \left\{ x \right\} \in K \subseteq U\), so \[ (X \setminus \left\{ x \right\}) \cap \left\{ x \right\} \in U. \] This would lead to \(\emptyset \in U\) which leads to a contradiction.

Suppose we have \(X\) as in the theorem. Let \(\kappa \leq \abs{X}\) be the smallest cardinality such that \([\kappa]\) has a \(\sigma\)-complete nonprincipal ultrafilter \(\mathcal{U}\). We show that \(\mathcal{U}\) is \(\kappa\)-complete.

Suppose, for contradiction, that this is not so. By the second point of lemma A there is some \(\mathcal{A} \subseteq \mathcal{V}\) such that \(\abs{A} < \kappa\) and \(\bigcup \mathcal{A} \in \mathcal{U}\), where \(\mathcal{A}\) is pairwise disjoint. Define \(\mathcal{U} ' \subseteq \pot \mathcal{A}\) by \(\mathcal{U}' := \left\{ \mathcal{S} \subseteq \mathcal{A} \mid \bigcup\limits_{}^{} \mathcal{S} \in \mathcal{U} \right\}\). One can verify that \(\mathcal{U}'\) is a \(\sigma\)-complete non-principal ultrafilter on \(\mathcal{A}\). Then \(\mathcal{A}\) carries a \(\sigma\)-complete nonprincipal ultrafilter \(\abs{\mathcal{A}} < \kappa\), contradicting the smallness of \(\kappa\). So no such \(\mathcal{A}\) exists, and \(\mathcal{U}\) is \(\kappa\)-complete after all.

Thus \(\kappa > \aleph_0\) by the third point of Lemma A. Indeed, \(\mathcal{U}\) is nonprincipal and \(\sigma\)-complete, so every countable subset of \([\kappa]\) lies in \(\mathcal{V}\); were \(\kappa = \aleph_0\), this would give \([\kappa] \in \mathcal{V}\), which is absurd. Hence \([\kappa]\) carries a \(\kappa\)-complete nonprincipal ultrafilter and \(\kappa > \aleph_0\), i.e. \(\kappa\) is a measurable cardinal with \(\kappa \leq \abs{X}\).

Suppose \(\kappa\) is measurable but not regular. Let \(\mathcal{U}\) be a \(\kappa\)-complete nonprincipal ultrafilter on \([\kappa]\), and let \(\mathcal{V}\) be its dual ideal. Then \[ \kappa = \lim_{\alpha < \lambda} \beta_{\alpha} \text{ for some } \lambda, \beta_{\alpha} < \kappa. \] Here we may take \(\lambda = \operatorname{cf}(\kappa)\), which is \(< \kappa\) precisely because \(\kappa\) is not regular. We have \[ [\kappa] = \bigcup\limits_{\alpha < \lambda}^{} [\beta_{\alpha}] = \bigcup\limits_{}^{} \left\{ [\beta_{\alpha}] \mid \alpha < \lambda \right\} \] Because \(\beta_{\alpha} < \kappa\), we have that \([\beta_{\alpha}] \in \mathcal{V}\), hence the union is also in \(\mathcal{V}\) because \(\lambda < \kappa\), so we have \([\kappa] \in \mathcal{V}\), contradicting \([\kappa] \in \mathcal{U}\). The first step is the third point of Lemma A, and the second is the first point of Lemma A. Hence \(\kappa\) is regular.

Suppose \(\kappa\) is measurable and not a strong limit. Let \(\mathcal{U}\) be a \(\kappa\)-complete nonprincipal ultrafilter on \([\kappa]\). Let \(\lambda < \kappa\) be such that \(2^{\lambda} \geq \kappa\). Let \(X \subseteq [2^{\lambda}]\) be any subset of cardinality \(\kappa\). We think of the elements of \([2^{\lambda}]\) as the functions \(f : [\lambda] \rightarrow \left\{ 0, 1 \right\}\), and, as \(\abs{X} = \kappa\), we transport \(\mathcal{U}\) along a bijection \([\kappa] \rightarrow X\) so as to regard it as a \(\kappa\)-complete nonprincipal ultrafilter on \(X\).

For any \(\alpha < \lambda\), we have \[ \left\{ f \in X \mid f(\alpha) = 0 \right\} \cup \left\{ f \in X \mid f(\alpha) = 1 \right\} = X. \] So exactly one of the two sets belongs to \(\mathcal{U}\). Call this set \(S_{\alpha}\). Then \(\left\{ S_{\alpha} \mid \alpha < \lambda \right\}\) is a subset \(\mathcal{U}\) of cardinality \(\leq \lambda\). By \(\kappa\)-completeness, (since \(\lambda < \kappa\)), we have that \(\bigcap\limits_{}^{} \left\{ S_{\alpha} \mid \alpha < \lambda \right\} \in \mathcal{U}\). But \(\bigcap\limits_{\alpha}^{} S_{\alpha}\) is either empty or a singleton, hence not in \(\mathcal{U}\). Indeed, any two \(f, g \in \bigcap\limits_{\alpha}^{} S_{\alpha}\) agree at every \(\alpha < \lambda\), so \(f = g\); and \(\mathcal{U}\) is nonprincipal, so it contains neither \(\emptyset\) nor a singleton. This is a contradiction. Hence there is no such \(\lambda\), and \(\kappa\) is a strong limit cardinal.

Given a model \(\mathcal{M}\) of ZF, we extract a smaller inner model \(\mathcal{L}\) inside \(\mathcal{M}\) consisting of constructible sets. Constructibility is expressed by a formula: there is a class \(L\) of constructible sets. \(L\) has a definable well-ordering, hence \(\mathcal{L} \vDash AC\).

In general, \(\mathcal{L}\) satisfies Gödel's axiom of constructibility \(V = \mathcal{L}\). And \(V = \mathcal{L}\) implies GCH: the constructible subsets of \([\aleph_{\alpha}]\) already appear at level \(\omega_{\alpha + 1}\) of the hierarchy of constructible sets, so \(2^{\aleph_{\alpha}} = \aleph_{\alpha + 1}\) holds in \(\mathcal{L}\). Hence \(\mathcal{L} \vDash ZFC + GCH\).

Start off with a countable transitive model of ZFC \(\mathcal{M}\). This costs us nothing: by Gödel we may pass from a model of ZF to one of ZFC, and by Löwenheim–Skolem we may take it to be countable and transitive. Force an injection from \((\omega_2)^{\mathcal{M}} \xrightarrow{i} (\pot \N)^{\mathcal{M}}\) into a new model \(\mathcal{M}' := \mathcal{M}[i]\). In \(\mathcal{M}'\) we have \[ \abs{\omega_0} < \abs{\omega_1} < \abs{\omega_2} \leq \abs{(\pot \N)^{\mathcal{M}}} \leq \abs{(\pot \N)^{\mathcal{M}'}} \] The forcing is arranged so that no cardinals are collapsed, i.e. \((\omega_1)^{\mathcal{M}'} = (\omega_1)^{\mathcal{M}}\) and \((\omega_2)^{\mathcal{M}'} = (\omega_2)^{\mathcal{M}}\), which is what makes the strict inequalities above survive. So in \(\mathcal{M}'\) we have \(2^{\aleph_0} \geq \aleph_2 > \aleph_1\), that is, \(\mathcal{M}' \vDash ZFC + \neg CH\).