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\).

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

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) = j - 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\).

\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.

\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\).

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.

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}\).

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.

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.

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.

• \((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)\).

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. 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.

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.

In the notes.

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 Hargogs' ordinal.

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

Suppose \(I\) is a set of innitial 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}. \]

Proposition A shows 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_{(-)}\).

1. We prove this using transfinite induction using our propositions and lemmas.

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.

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 \(\aleph = 0\)): We already know \(\aleph_0 = \aleph_0 \cdot \aleph_0\).

• (Case \(\aleph > 0\)): For all \(\beta < \aleph\), we have \(\aleph_{\beta} \cdot \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}\). The proof is hairy and we're out of time.

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\).
• Let \(X, \leq\) be a partial order stisfying the assumptions of Zorn's Lemma. 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.

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 DC_α 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\{ y_{\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 DC_α there exists a sequence \((x_{\beta}_{\beta < \alpha})\) satisfying the DC_α 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.

\[ \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 \in I \setminus \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 isommorphism.

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] = \bigcup_{\alpha < \operatorname{cf}(\kappa)} \left( [\beta_{\alpha}] \setminus \bigcup\limits_{\alpha' < \alpha}^{} [\beta_{\alpha'}] \right) = \bigcup\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{\bigcup\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.

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

\((\implies)\) is immediate from lemma A.

For \((\impliedby)\), suppose \(\kappa = \sum\limits_{i \in I}^{} \kappa_i\), where \(\abs{I}, \kappa_i < \kappa\) . Then \[ \kappa = \abs{I} \cdot \sup_{i \in I} \kappa_i = \max (\abs{I}, \sup_{i \in I} \kappa_i). \] So \(\kappa = \sup_{i \in I} \kappa_i\), using some bijection on \(I\) with an ordinal.

So for some ordinal \(\lambda\) with \(\abs{\lambda} \leq \abs{I} < \kappa\) we have \[ \kappa = \lim_{\alphaa \rightarrow \lambda} k_{i_{\alpha}} \text{ where } \lambda < \kappa. \] Then \(\operatorname{cf}(\kappa) \leq \lambda < \kappa\) so \(\kappa\) is singular.

Suppose for contradiciton 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}. \]

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 inaccessibly cardinal.

On the other hand, if \(\kappa\) is strongly inaccessible, then \(V_{\kappa}\) is a Grothendieck universe.

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_{a \in \Ord}^{} A_{\alpha}. \]

Let us define \(F_\alpha = A_{\alpha} \setminus A_{\alpha + 1}\), i.e. the isolated points in \(A_{\alpha}\). Likewise (TODO: pluscup) \[ F = \bigcup\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 thhat } 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.

• \(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 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 step case \(\alpha + 1\), note that we have a surjection \(\Pi_{\alpha}^{\N} \xrightarrow{\cap} \Sigma_{\alpha + 1}\) so \[ \abs{\Sigma_{\alpha + 1}} \leq \Pi_{\alpha^{\N}} \leq (2^{\aleph_0})^{\aleph_0} = 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). \] and \[ A_{\lambda} := \bigcup\limits_{\alpha < \lambda}^{} A_{\alpha}, \quad B_{\lambda} :=\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}. \] 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\).

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 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\). \(X\) is then countable because there are only countably many positions.

Suppose \(G \subseteq \N^{\N}\) is closed. Define \(\sigma_\mathrm{I}(w)\) for an even-length word as \[ \sigma_\mathrm{I}(w) = \begin{cases} n \\ 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.

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. If \(n\) is even, it's II's move. Since they don't currently have a winning strategy, this is preserved by any continuation.

There is a sequence of winning plays for I.

Then this is a Cauchy sequence in \(G\). Since \(G\) is closed, its limit is also in \(G\).

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\}\). Paritally order \(P\) by \(\subseteq\). It is easily checked that the conditions of ZL are satisfied. By Zorn's lemma, \(P\) has a maximal element.

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.

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\{ u \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\). Thus \(\kappa > \aleph_0\) by the third point of Lemma A.

Suppose \(\kappa\) is measurable but not regular. Then \[ \kappa = \lim_{\alpha < \lambda} \beta_{\alpha} \text{ for some } \lambda, \beta_{\alpha} < \kappa. \] 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}\)

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\).

For any \(\alpha < \lambda\), we have \[ \left\{ f \in X \mid f(\lambda) = 0 \right\} \cup \left\{ f \in X \mid f(zl) = 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 of a singleton, hence not in \(\mathcal{U}\). This is a contradiction.