25 Apr 2026

Kardinalna aritmetika Lecture notes

Master's course taught by Alex Simpson. Warning: The notes are not optimized for HTML (yet). Without warranty.

Introduction

Continuum Hypothesis

Every infinite subset of \(\R\) is either in bijection with \(\N\) or in bijection with \(\R\).

This is independent from ZFC.

We also have a more explicit stronger version.

ACH: The \(\aleph\) continuum hypothesis

\[ 2^{\aleph_0} = \aleph_1 \] as an equation in cardinal arithmetic. Note that this version implies the regular continuum hypothesis.

Interrelationship with general math
Touted as a foundation for mathematics
Leads to new interesting areas of mathematics
Provides the tools for studying independence questions

We give the axioms in a way that mirrors the way mathematicians actually use them.

Our axioms will tell us which classes can be sets:

Assume a universe \(\mathcal{U}\) of all mathematical entities that we may use as elements of sets.
A collection of elements of the universe is called a class.
If \(P(x)\) is a property of elements of \(\mathcal{U}\), then \(\{x \mid P(x)\}\) satisfies \[ y \in \{x \mid P(x)\} \iff P(y). \]
A set is a class that is itself an element of \(\mathcal{U}\).

Russell's Paradox

Not every class is a set.

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.

Extensionality

If \(\Class{X}, \Class{Y}\) are classes and \(\forall z.\, z \in \Class{X} \iff z \in \Class{Y}\), then \(\Class{X} = \Class{Y}\).

Empty Set

\(\emptyset := \{x \mid \bot\}\) is a set.

Pairing

For any \(x, y\), \(\{x, y\} := \{z \mid z = x \lor z = y\}\) is a set. In particular \(\{x\} := \{x,x\}\) is a set.

Union

For a class \(\Class{X}\) of sets, \[ \bigcup \Class{X} := \{z \mid \exists Y \in \Class{X}.\, z \in Y\}. \] If \(X\) is a set of sets, then \(\bigcup X\) is a set.

Powerset

For a class \(\Class{X}\), we define its powerclass as \[ \mathcal{P}\Class{X} := \{Y \mid Y \text{ is a subset of } \Class{X}\}. \] If \(X\) is a set, then \(\mathcal{P}X\) is a set. We call it a powerset.

Separation

If \(X\) is a set and \(P(x)\) is a property of elements of \(\mathcal{U}\), then \[ \{x \in X \mid P(x)\} \] is a set.

Replacement

If \(X\) is a set and \(F : X \rightarrow \mathcal{U}\) is a class function, then \(\operatorname{image}(F)\) is a set.

A class function from \(\Class{X}\) to \(\Class{Y}\) is a property \(F(x,y)\) of elements \(x,y\) of \(\mathcal{U}\) satisfying:

For all \(x \in \Class{X}\) there exists a unique \(y \in \Class{Y}\) such that \(F(x,y)\).
If \(F(x,y)\), then \(x \in \Class{X}\) and \(y \in \Class{Y}\).

Then \[ \operatorname{image}(F) := \{y \in \Class{Y} \mid \exists x \in \Class{X}.\, F(x,y)\}. \]

Product of Classes

A product of classes \(\Class{X}\) and \(\Class{Y}\) is a class \(\Class{X} \times \Class{Y}\) together with class functions \(\pi_1 : \Class{X} \times \Class{Y} \rightarrow \Class{X}\) and \(\pi_2 : \Class{X} \times \Class{Y} \rightarrow \Class{Y}\) satisfying \[ \forall x \in \Class{X}.\, \forall y \in \Class{Y}.\, \exists! z \in \Class{X} \times \Class{Y}.\, \pi_1(z) = x \land \pi_2(z) = y. \]

Uniqueness of Products

Any two products of \(\Class{X}\) and \(\Class{Y}\) are isomorphic.

Existence of Products

For every \(\Class{X}\) and \(\Class{Y}\), a product \(\Class{X} \times \Class{Y}\) with \(\pi_1, \pi_2\) exists.

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

If \(X\) and \(Y\) are sets, then so is \(X \times Y\).

Suppose \(F : \Class{X} \rightarrow \Class{Y}\) is a class function. Its graph is \[ \Gamma(F) := \{(x, y) \in \Class{X} \times \Class{Y} \mid y = F(x)\} \subseteq \Class{X} \times \Class{Y}. \] If \(X\) is a set and \(F : X \rightarrow Y\) is a class function, then \(\Gamma(F)\) is a set by Replacement.

The exponential class is defined as \[ \Class{Y}^{X} := \left\{ \Gamma(F) \mid F : X \rightarrow \Class{Y} \text{ is a function} \right\}. \]

If \(Y\) is a set then \(Y^X\) is a set.

Natural Number Structure

A natural number structure is a triple \((\Class{N}, 0, S)\) where \(\Class{N}\) is a class, \(0 \in \Class{N}\), and \(S : \Class{N} \rightarrow \Class{N}\) satisfying:

\(S\) is injective: \(\forall x, y \in \Class{N}.\, S(x) = S(y) \implies x = y\).
Acyclicity: \(\forall x \in \Class{N}.\, S(x) \neq 0\).
Induction: if \(\Class{X}\) satisfies \(0 \in \Class{X}\) and \(\forall x \in \Class{N}.\, x \in \Class{X} \implies S(x) \in \Class{X}\), then \(\Class{N} \subseteq \Class{X}\).

A natural number structure exists.

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

Recursion Theorem

Suppose \(\mathcal{A}\) is a class, \(a \in \mathcal{A}\), and \(F : \mathcal{A} \rightarrow \mathcal{A}\). Then there exists a unique class function \(R : \Class{N} \rightarrow \mathcal{A}\) such that

\(R(0) = a\),
\(R(S(x)) = F(R(x))\).

Parametrised Recursion Theorem

Suppose \(\mathcal{A}\) is a class, \(\Class{Z}\) is a class, \(a : \Class{Z} \rightarrow \mathcal{A}\), and \(F : \Class{Z} \times \mathcal{A} \rightarrow \mathcal{A}\). Then there exists a unique class function \(R : \Class{Z} \times \Class{N} \rightarrow \mathcal{A}\) such that

\(R(z, 0) = a(z)\),
\(R(z, S(x)) = F(z, R(z, x))\).

Apply the PRT with \(\mathcal{A} = \Class{N}\), \(\Class{Z} = \Class{N}\), \(B(z) = z\), and \(F(z, x) = S(x)\). The unique resulting \[ R : \Class{N} \times \Class{N} \rightarrow \Class{N} \] satisfies

\begin{align*} R(z, 0) &= z, \\ R(z, S(x)) &= S(R(z, x)). \end{align*}

This \(R\) is addition on \(\Class{N}\).

Von Neumann Natural Numbers

For a set \(n\) define \(n^{+} := n \cup \{n\}\). A set \(X\) is a vN-number if:

For every subset \(Y \subseteq X\) satisfying \[ \emptyset \in X \implies \emptyset \in Y \quad \text{and} \quad \forall z \in Y.\, z^{ + } \in X \implies z^{ + } \in Y, \] it holds that \(Y = X\).
\(X = \emptyset\) or \(\exists z \in X\) such that \(X = z^{+}\).

The class of all vN-numbers is \[ \mathrm{vN} := \{x \mid x \text{ is a set and a vN-number}\}. \]

Axiom of Infinity

The Von Neumann natural numbers structure is a set. Equivalently: \[ \exists X.\, \emptyset \in X \land \forall y \in X.\, y \text{ is a set} \implies y^{+} \in X. \]

The axioms of set theory (ZFC-style, synthetic formulation):

Extensionality
Empty Set
Pairing
Powerset
Separation
Replacement
Axiom of Infinity

Comparison of cardinalities

Classes are collections of elements of the universe \(\Class{\mathcal{U}}\). Sets are classes that are themselves elements of \(\Class{\mathcal{U}}\). Sets are axiomasised by the axioms from lecture 1: extensionality, emptyset, pairing, union, powerset, separation, replacement, and infinity.

Let \((\N, \dots)\) be a chosen natural numbers structure. Then \(\Z, \Q\) and \(\R\) can be derived using standard mathematical constructions, e.g. Dedekind cuts.

For the time being we will work without the axiom of choice.

One intuition for sets is that they are "small" classes. There are two observations consistent with this:

Suppose \(A\) is a set and \(\Class{B}\) a class and we have a surjective class function \(A \twoheadrightarrow \Class{B}\) then \(\Class{B}\) is a set (by replacement).
Suppose \(\Class{A}\) is a class and \(B\) a set and we have an injective class function \(\Class{A} \rightarrowtail B\), then \(\Class{A}\) is a set (using separation and replacement).

Two sets \(A, B\) have the same cardinality (are equipotent), if there exists a bijective function \(f : A \rightarrow B\) between them. We write this as \[ \abs{A} = \abs{B}. \]

\noindent Note we don't yet have an independent meaning for \(\abs{A}\).

Since \(\abs{ ~ \cdot ~ } = \abs{ ~ \cdot ~}\) is given by an isomorphism, it is in particular an equivalence relation:

\begin{align*} \abs{A} &= \abs{A} \\ \abs{A} = \abs{B} &\implies \abs{B} = \abs{A} \\ \abs{A} = \abs{B} \land \abs{B} = \abs{C} &\implies \abs{A} = \abs{C} \end{align*}

A set \(A\) has cardinality less than or equal to a set \(B\) if there exists an injective function \(i : A\rightarrowtail B\) from \(A\) to \(B\). We write \[ \abs{A} \leq \abs{B} \]

\noindent

The relation is obviously reflexive and transitive due to monomorphism composition. Antisymmetry follows from the following theorem.

Cantor-Schröder-Bernstein (CSB)

Assume \(\abs{A} \leq \abs{B}\) and \(\abs{B} \leq \abs{A}\). Then \(\abs{A} = \abs{B}\).

\noindent It was reportedly first proved by Dedekind.

CSB Lemma

If \(B_0 \subseteq A_0\) and \(\abs{A_0} \leq \abs{B_0}\), then \(\abs{B_0} = \abs{A_0}\).

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

\begin{align*} A_{n+1} &:= f(A_n) \\ B_{n+1} &:= f(B_n) \end{align*}

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

\begin{align*} f(C_n) &= f(A_n \setminus B_n) \\ &= f(A_n) \setminus f(B_n) \text{ because } f \text{ is injective} \\ &= A_{n+1} \setminus B_{n+1} \\ &= C_{n+1} \end{align*}

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

A set \(A\) has cardinality strictly less than a set \(B\) if \[ \abs{A} < \abs{B} :\iff \abs{A} \leq \abs{B} \land \abs{A} \neq \abs{B}. \]

\leavevmode

Strict ordering between cardinalities is irreflexive and transitive
\(\abs{A} \leq \abs{B} < \abs{C} \leq \abs{D} \implies \abs{A} < \abs{D}\).
It is not a linear relation, even with choice.

A set \(A\) has cardinality very strictly less than a set \(B\) if we have \(\abs{A} \ll \abs{B} :\iff \abs{A} \leq \abs{B}\) and there is no surjection from \(A\) to \(B\). If \(\abs{A} \ll \abs{B}\), then \(\abs{A} < \abs{B}\), and we have the sandwiching property \[ \abs{A} \leq \abs{B} \ll \abs{C} \leq \abs{D} \implies \abs{A} \ll \abs{D}. \]

\noindent

We have

\begin{align*} \abs{X} \leq \abs{Y} \text{ and } \abs{Y} \ll \abs{Z} &\implies X \ll \abs{Z} \\ \abs{X} \ll \abs{Y} \text{ and } \abs{Y} \leq \abs{Z} &\implies X \ll \abs{Z} \\ \end{align*}

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

The standard finite sets are, for \(n \in \N\), \[ [n] = \{m \in \N \mid m < n\}. \] Herein we define a function \([ ~ \cdot ~ ] : \N \rightarrow \pot \N\) using the recursion theorem.

\leavevmode

\(\forall m, n \in \N .\, \abs{[m]} \leq \abs{[n]} \iff m \leq n\).
\(\forall n \in \N .\, \abs{[n]} \ll \abs{\N}\).

In particular, \(\N\) is not finite.

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

A set \(A\) is finite if there exists \(n \in \N\) such that \(\abs{A} = \abs{[n]}\). In this case we define its cardinality \(\abs{A} = n\).

\noindent Note that this is well defined, since there is a unique such \(n\) by the previous proposition.

\leavevmode

If we have \(A\) finite and \(A \twoheadrightarrow B\), then \(B\) is finite
If \(B\) is finite and \(A \rightarrowtail B\), then \(A\) is finite

Think about how we could define finiteness without referring to the structure of \(\N\).

\leavevmode

A set is infinite if it is not finite.
A set \(X\) is Dedekind infinite if there exists some proper subset \(X' \subsetneq X\) such that \(\abs{X} = \abs{X'}\).

Consider the following.

\(X\) is infinite.
\(X\) is Dedekind infinite.
There exists a proper injection \(i : X \rightarrowtail X\).
\(\abs{\N} \leq \abs{X}\).

Then we have \[ (2) \iff (3) \iff (4) \implies (1). \] Furthermore, \(1 \implies 4\) holds under the axiom of dependent choice. It can also be proved using the weaker axiom of countable choice, but the proof is less intuitive. We will meet CC later in the course.

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

Axiom of Dependent Choice

If a binary relation \(R \subseteq X \times X\) is total, that is \(\forall x \in X .\, \exists y \in X . xRy\), then for any \(x_0 \in X\), there exists an infinite sequence \((x_n)_{n \in \N}\) such that \[ \forall n \in \N .\, x_n R x_{n+1}. \]

We define the cardinality of \(\N\) as \(\aleph_0 = \abs{\N}\).

\noindent

By the last theorem, \(X\) is Dedekind infinite if and only if \(\aleph_0 \leq X\).

\leavevmode

A set \(X\) is countable if \(\abs{X} \leq \aleph_0\).
If \(X\) is countable and infinite, then we call it countably infinite.
If \(X\) is not countable, we say it is uncountable.

Examples of countable sets are \(\N, \Z, \Q, \N \times \N\).

\leavevmode

If \(X\) is countable then \(X\) is finite or \(\abs{X} = \aleph_0\).
Countable sets are closed under finite product, disjoint finite union, countable union, countable product, \(\dots\)
Also if \(A\) is countable and \(A \twoheadrightarrow B\), then \(B\) is countable.
Likewise if \(B\) is countable and \(A \rightarrowtail B\), then \(A\) is countable.

\noindent

Examples of countably infinite sets are \(\N, \N \times \N, \Z, \Q\). Uncountable sets are \(\R, \pot(\N), 2^{\N}\), where \(2 = \left\{ 0, 1 \right\}\). Instead of manually computing isomorphisms, we can use CSB to prove cardinal equalities.

For instance, showing \(\abs{\N} = \abs{\Q}\) entails showing:

\(\abs{\N} \leq \abs{\Q}\), which is immediate because the inclusion \(n \mapsto n\) is injective.
For \(\abs{\Q} \leq \abs{\N}\), the function \(q \mapsto 2^{\sgn(q) + 1} \cdot 3^m \cdot 5^n\), where we set \(m = n =0\) if \(q = 0\) and \(\frac{m}{n}\) is the reduced fraction for \(\abs{q}\) otherwise. This function is again injective.

Let us also show \(\abs{\R} = \abs{\pot(\N)}\)

For \(\abs{\R} \leq \abs{\pot(\Q)}\), the function \(r \mapsto \left\{ q \in \Q \mid q < r \right\}\) is injective.
\(\abs{\pot(\Q)} \leq \abs{\pot(\N)}\) holds since we have \(\abs{\Q} \leq \abs{\N}\).
For \(\abs{\pot(\N)} \leq \abs{\R}\), the function \[ s \mapsto \sum\limits_{n = 0}^{\infty} \frac{1_S(n)}{3^n} \text{ where } 1_S(n) = \begin{cases} 1 & \text{if } n \in S \\ 0 & \text{if } n \not\in S \end{cases} \] is injective.

Cantor's Theorem

For every set \(X\), we have \(\abs{X} \ll \abs{\pot X}\).

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

Since \(\R\) is in bijection with \(\pot \N\), we have \(\abs{\R} = \abs{\pot \N}\). By Cantor's theorem, \(\abs{\N} \ll \abs{\pot \N}\), so \(\R\) is uncountable.

Basic Cardinal Arithmetic

The powerclass operation \(\Class{X} \mapsto \pot \Class{X}\) induces an operation on class functions. That is, if \(f : \Class{X} \rightarrow \Class{Y}\) is a function, then we have a function \[ \pot f : \pot \Class{X} \rightarrow \pot \Class{Y} \] defined by \((\pot f)(A) = \{f(a) \mid a \in A\} = f(A)\). Note that \(\pot \) preserves identities and composition.

The operation \(f \mapsto \pot f\) is functorial, i.e.

For any \(\Class{X}\), we have \(\pot(\operatorname{id}_{\Class{X}}) = \operatorname{id}_{\pot \mathcal{X}}\), and
for any \(G : \Class{X} \rightarrow \Class{Y}\) and \(G : \Class{Y} \rightarrow \Class{Z}\), we have \[ \pot(G \circ F) = (\pot G) \circ (\pot F) : \pot \Class{X} \rightarrow \pot \Class{Z} \]

The operation \(X \mapsto \pot X\) on sets \(X\) preserves cardinal inequalities:

\begin{align*} \abs{X} = \abs{Y} &\implies \abs{\pot X} = \abs{\pot Y}, \\ \abs{X} \leq \abs{Y} &\implies \abs{\pot X} \leq \abs{\pot Y}. \end{align*}

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.

In lecture \(\)

We also consider the functoriality of the products, exponentials, and coproducts. They're also functorial, and preserve isomorphisms and monomorphisms.

If \(\abs{X} = \abs{X'}\) and \(\abs{Y} = \abs{Y'}\), then

\begin{align*} \abs{X \times Y} &= \abs{X' \times Y'}, \\ \abs{X + Y} &= \abs{X' + Y'}, \\ \abs{Y^X} &= \abs{(Y')^{(X')}}. \end{align*}

Note in the first two cases we can also take \(\leq\). In the last case, \[ \abs{Y^X} = \abs{(Y')^{(X')}} \] holds, except when \(X = Y = Y' = \emptyset \neq X'\). The reason we have a corner case corresponds to the fact that functors preserve sections, not general monomorphisms.

Cardinal Arithmetic Operations

We've already defined \(n\) as the cardinality \(\abs{[n]}\) and \(\aleph_0 = \abs{\N}\). We also define

\begin{align*} \abs{X} + \abs{Y} &:= \abs{X + Y}, \\ \abs{X} \cdot \abs{Y} &:= \abs{X \times Y}, \\ \abs{Y}^{\abs{X}} &:= \abs{Y^X}. \end{align*}

Cardinal Monoid Laws

The following hold for all sets \(X, Y, Z\).

Addition is a commutative monoid with unit 0:
\begin{align*} \abs{X} + 0 &= \abs{X} = 0 + \abs{X}, \\ \abs{X} + \abs{Y} &= \abs{Y} + \abs{X}, \\ \abs{X} + (\abs{Y} + \abs{Z}) &= (\abs{X} + \abs{Y}) + \abs{Z}. \end{align*}
Multiplication is a commutative monoid with unit 1:
\begin{align*} \abs{X} \cdot 1 &= \abs{X} = 1 \cdot \abs{X}, \\ \abs{X} \cdot \abs{Y} &= \abs{Y} \cdot \abs{X}, \\ \abs{X} \cdot (\abs{Y} \cdot \abs{Z}) &= (\abs{X} \cdot \abs{Y}) \cdot \abs{Z}. \end{align*}
Distributivity and annihilation:
\begin{align*} \abs{X} \cdot 0 &= 0, \\ \abs{X} \cdot (\abs{Y} + \abs{Z}) &= \abs{X} \cdot \abs{Y} + \abs{X} \cdot \abs{Z}. \end{align*}
Exponentiation laws:
\begin{align*} \abs{X}^0 &= 1, \\ \abs{X}^1 &= \abs{X}, \\ \abs{X}^{\abs{Y} + \abs{Z}} &= \abs{X}^{\abs{Y}} \cdot \abs{X}^{\abs{Z}}, \\ \abs{X}^{\abs{Y} \cdot \abs{Z}} &= (\abs{X}^{\abs{Y}})^{\abs{Z}}, \\ 1^{\abs{X}} &= 1, \\ (\abs{X} \cdot \abs{Y})^{\abs{Z}} &= \abs{X}^{\abs{Z}} \cdot \abs{Y}^{\abs{Z}}. \end{align*}

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

In ordinary arithmetic, we have

\begin{align*} x + z &= y + z \implies x = y, \\ x \cdot z &= y \cdot z \implies x = y \text{ (if \(z \neq 0\))}. \end{align*}

But in cardinal arithmetic, cancellation fails. In particular: \[ \aleph_0 + 0 = \aleph_0 + \aleph_0, \] but \(0 \neq \aleph_0\). Likewise, \[ 1 \cdot \aleph_0 = \aleph_0 = \aleph_0 \cdot \aleph_0, \] but \(1 \neq \aleph_0\).

Idempotent Cardinal

We say that \(\abs{X}\) is idempotent (or its own square) if \(\abs{X} = \abs{X} \cdot \abs{X}\).

For instance, \(\aleph_0\) is idempotent.

If \(\abs{X} \geq 2\) and \(\abs{X}\) is idempotent, then

\(\aleph_0 \leq \abs{X}\), i.e., \(X\) is Dedekind infinite, and
\(\abs{X} = \abs{X} + \abs{X}\).

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

If \(\abs{X} \geq 2\) and \(\abs{X}\) is idempotent, then \(2^{\abs{X}}\) is also idempotent.

We have

\begin{align*} 2^{\abs{X}} \cdot 2^{\abs{X}} &= 2^{\abs{X} + \abs{X}} \\ &= 2^{\abs{X}} \text{ (by the previous lemma)} \end{align*}

If \(X\) is infinite and \(Y \subseteq X\) satisfies \(\abs{Y} \ll \abs{X}\), then we might expect \[ \abs{X \setminus Y} = \abs{X}. \] This holds assuming the axiom of choice. The proof of this is nonetheless quite involved.

If \(\abs{X}\) is idempotent and \(Y \subseteq X\) is such that \(\abs{Y} \ll \abs{X}\), then \(\abs{X \setminus Y} = \abs{X}\).

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

Cantor's Theorem (Cardinal form)

For any set \(X\), we have \[ \abs{X} \ll 2^{\abs{X}}. \]

Continuum Hypothesis (Cardinal form)

If \(\aleph_0 \leq \abs{X} \leq 2^{\aleph_0}\), then either \(\abs{X} = \aleph_0\) or \(\abs{X} = 2^{\aleph_0}\).

Generalized Continuum Hypothesis (GCH)

If we have \[ \aleph_0 \leq \abs{Z} \leq \abs{X} \leq 2^{\abs{Z}}, \] then either \(\abs{X} = \abs{Z}\) or \(\abs{X} = 2^{\abs{Z}}\).

Gödel showed that GCH is consistent with the axioms of set theory.

Ordinals

We can come to the notion of an ordinal through two main ways.

Ordinals measure order type: Ordinals represent the order type of a well-ordered set.
Ordinals as extended numbers: We can think of ordinals as an extended number system for counting.

This counting proceeds through the natural numbers, then through \(\omega\), then continues as:

\begin{align*} 0, 1, 2, 3, 4, 5, \dots, \\ \omega, \omega + 1, \omega + 2, \omega + 3, \dots, \\ \omega \cdot 2, \omega \cdot 2 + 1, \dots, \omega \cdot 3, \omega \cdot 3 + 1, \dots, \\ \omega^2, \omega^2 + 1, \dots, \omega^2 + \omega, \dots, \omega^3, \dots \end{align*}

Eventually we reach ordinals like \[ \omega^{\omega^{\omega^{\dots}}} \] and even a pattern of \(\omega\) many exponentiations. We call this ordinal \(\varepsilon_0\). This is the smallest ordinal \(\alpha\) satisfying \[ \alpha = \omega^{\alpha}, \] the smallest fixed point of exponentiation by \(\omega\). Then we continue to \(\varepsilon_1\) and so on.

But this collection is still countable. We can then ascend to \(\omega_1\), the smallest uncountable ordinal. Repeating the pattern, we obtain \(\omega_2\), \(\omega_{\omega}\), \(\omega_{\omega_1}\), and so forth.

We construct this structure by adjoining to the natural numbers the rule that for any collection of ordinals, we can always form the next smallest ordinal that follows all of them.

We would like to formalise this intuition of generalized counting. Note that we have \(0\) and a successor operation, like with the naturals. We need to add an operation that will take us "beyond" the current structure. It turns out the right one is the supremum which maps any set of ordinals to the least upper bound.

Ordinal structure

An ordinal structure is given by a class \(\Ord\) of ordinals, a partial order \(\leq\) on \(\Ord\) and

an element \(0 \in \Ord\), i.e. zero,
a class function \(s : \Ord \rightarrow \Ord\), i.e. the successor, and
a class function \(\sup : \Ord \rightarrow \Ord\), i.e. the supremum.

The following must hold.

\(\forall \alpha \in \Ord\), we have \(0 \leq \alpha\), i.e. \(0\) is a minimal element.
\(s\) must be a successor operation, i.e. \[ \alpha < s(\alpha) \text{ and } \alpha \leq \beta \implies (\beta = \alpha \lor s(\alpha) \leq \beta). \]
\(\sup\) is a supremum operation, namely for any set \(X \subseteq \Ord\), its supremum is the least upper bound, i.e. \[ X \leq \sup X \text{ and if }X \leq \alpha, \text{ then } \sup X \leq \alpha. \]
Lastly, the principle of transfinite induction (TI) must hold, i.e. if \(\Class{X} \subseteq \Ord\) is such that
1. (base case): \(0 \in \Class{X}\),
2. (step case): \(\alpha \in \Class{X} \implies s(\alpha) \in \Class{X}\),
3. (supremum case): For every subset \(A \subseteq \Class{X}\), we have \(\sup A \in \Class{X}\),

then \(\Class{X} = \Ord\).

For ease of readability, we often write \(\alpha + 1\) instead of \(s(\alpha)\).

\(\leq\)is a linear order on \(\Ord\).

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

(Base case): When \(\alpha = 0\), we have \(0 \leq \beta\) by axiom.
(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\).
(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\).

For the split into the two cases, we used the Law of Excluded Middle.

Recall the standard finite set was given as \([n] = \left\{ x \in \N \mid x < n \right\}\).

The standard ordinal class is given as \[ [\alpha] := \left\{ \beta \in \Ord \mid \beta < \alpha \right\}. \]

This is sometimes written as \(\downarrow \alpha\).

For every ordinal \(\alpha\), the class \([\alpha]\) is a set.

We proceed by transfinite induction.

(Base case): For \(\alpha = 0\), we have \([0] = \emptyset\) which is a set.
(Step case): If \([\alpha]\)is a set, then \[ [s(\alpha)] = [\alpha] \cup \left\{ \alpha \right\}, \] which is clearly a set.
(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.

\(\Ord\) is a proper class.

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.

The ordinals separate into two kinds.

\(\alpha \in \Ord\) is a successor ordinal if there exists \(\alpha' \in \Ord\) such that we have \[ \alpha = \alpha' + 1 \]
\(\alpha \in \Ord\) is a limit ordinal if there exists a subset \(A \subseteq [\alpha]\) with \(\alpha = \sup A\). This is equivalently stated as \(\alpha = \sup [\alpha]\).

This split is clean.

Every ordinal is either a successor ordinal or a limit ordinal (but not both).

By transfinite induction, left as exercise.

We have two reformulations of transfinite induction.

If \(\Class{X} \in \Ord\) satisfies

\(0 \in \Class{X}\),
\(\alpha \in \Class{X} \implies s(\alpha) \in \Class{X}\),
\([\lambda] \subseteq \Class{X} \implies \lambda \in \Class{X} \), where \(\lambda > 0\) is a limit ordinal,

then \(\Class{X} = \Ord\).

If \(\Class{X} \subseteq \Ord\) satisfies \[ [\alpha] \subseteq \Class{X} \implies \alpha \in \Class{X}, \] then \(\Class{X} = \Ord\).

This can be stated alternatively. If \(\Class{Y}\) satisfies progressivity: \[ \forall y \in \Ord .\, (\forall x < y .\, x \in \Class{Y}) \rightarrow y \in \Class{Y}, \] then \(\Class{Y} = \Ord\).

Transfinite recursion theorem (TRT)

Let \(\Class{A}\) be a class with \(a \in \Class{A}\) and \(F : \Class{A} \rightarrow \Class{A}\), and \(L : \mathcal{P}\Class{A} \rightarrow \Class{A}\). There is a unique class function \[ T : \Ord \rightarrow \Class{A} \] satisfying

\begin{align*} T(0) &= a,\\ T(\alpha+1) &= F\big(T(\alpha)\big),\\ T(\lambda) &= L\big(\{T(\alpha)\mid \alpha<\lambda\}\big) \quad\text{for }\lambda>0\text{ a limit ordinal.} \end{align*}

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

\begin{align*} t(0) &= a \text{ if } 0 < \gamma \\ t(s(\alpha)) &= F(t(\alpha)) \text{ if } s(\alpha) < \gamma \\ t(\lambda) &= L(\left\{ t(\alpha) \mid \alpha < \lambda \right\}) \text{ if } \lambda < \gamma. \end{align*}

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.

The TRT allows us to prove a lot of useful things.

Any two ordinal structures are isomorphic.

Exercise.

Suppose \(\Class{A}\) and \(\Class{Z}\) are classes with class functions

\begin{align*} B : \Class{Z} &\rightarrow \Class{A} \\ F : \Class{Z} \times \Class{A} &\rightarrow \Class{A} \\ L : \Class{Z} \times \mathcal{P}\Class{A} &\rightarrow \Class{A} \end{align*}

Then there is a unique class function \(T : \Class{Z} \times \Ord \rightarrow \Class{A}\) satisfying

\begin{align*} T(z,0) &= B(z) \\ T(z,\alpha+1) &= F(z, T(z,\alpha)) \\ T(z,\lambda) &= L\bigl(z, \{T(z,\alpha)\mid \alpha<\lambda\}\bigr)\quad\text{for }\lambda>0\text{ a limit ordinal} \end{align*}

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

Using the parametrised transfinite recursion theorem, we define \(T : \Ord \times \Ord \rightarrow \Ord\) using

\begin{align*} B(\alpha) &= \alpha \\ F(\alpha, \beta) &= \beta + 1 \\ L(\alpha, A) &= \sup A \end{align*}

Then \(T : \Ord \times \Ord \rightarrow \Ord\) is the unique class function such that

\begin{align*} T(\alpha, 0) &= \alpha \\ T(\alpha, \beta + 1) &= F(\alpha, T(\alpha, \beta)) = T(\alpha, \beta) + 1 \\ T(\alpha, \lambda) &= L(\alpha, \left\{ T(\alpha, \beta) \mid \beta < \lambda \right\}) = \sup \left\{ T(\alpha, \beta) \mid \beta < \lambda \right\} \end{align*}

Thus we have defined ordinal addition as the unique class function \((+) : \Ord \times \Ord \rightarrow \Ord\) satisfying

\begin{align*} \alpha + 0 &= \alpha \\ \alpha + (\beta + 1) &= (\alpha + \beta) + 1, \text{ i.e.} \\ \alpha + s(\beta) &= s(\alpha + \beta)\\ \alpha + \lambda &= \sup_{\beta < \lambda} \alpha + \beta \end{align*}

This justifies the use of the notation \(\alpha + 1 = s(\alpha)\).

We have \[ 1 + \omega = \omega \neq \omega + 1 \] which means that ordinal addition is not commutative.

We likewise define ordinal multiplication as the unique class function \((\cdot) : \Ord \times \Ord \rightarrow \Ord\) satisfying

\begin{align*} \alpha \cdot 0 &= 0 \\ \alpha \cdot (\beta + 1) &= \alpha \cdot \beta + \alpha \\ \alpha \cdot \lambda &= \sup_{\beta < \lambda} \alpha \cdot \beta \qquad \lambda > 0 \text{ a limit ordinal} \end{align*}

Ordinal multiplication is not commutative. For example, \[ 2 \cdot \omega = \omega \neq \omega + \omega = \omega \cdot 2. \]

We define ordinal exponentiation as the unique class function \((\cdot)^{(\cdot)} : \Ord \times \Ord \rightarrow \Ord\) satisfying

\begin{align*} \alpha^0 &= 1 \\ \alpha^{\beta+1} &= \alpha^\beta \cdot \alpha \\ \alpha^\lambda &= \sup_{\beta < \lambda} \alpha^\beta \qquad \lambda > 0 \text{ is a limit ordinal} \end{align*}

We have \(\omega^2 = \omega \cdot \omega \neq \omega\) and \(\omega = 2^\omega \neq \omega^\omega\). Contrast with cardinal arithmetic: \(\aleph_0^2 = \aleph_0 \cdot \aleph_0 = \aleph_0\), but \(\aleph_0 \neq 2^{\aleph_0} = \aleph_0^{\aleph_0}\).

von Neumann ordinals

An ordinal structure exists.

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

\begin{align*} 0 &= \emptyset\\ &\vdots \\ n + 1 &= n \cup \left\{ n \right\} \\ &\vdots \\ \omega &= \left\{ 0, 1, 2, \dots \right\}\\ \omega + 1 &= \omega \cup \left\{ \omega \right\} \end{align*}

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.

Well-Ordered Sets

In the previous lecture we saw ordinals as a numbering system for cardinals.
Ordinals also show up as a tool for proving more general theorems.
In this lecture we will come to know the ordinals as tools for classifying well-ordered sets.

The least ordinal principle

If \(\Class{X} \subseteq \Ord\) is nonempty, then \(\Class{X}\) has a minimum element.

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.

For a class relation \(\Class{R} \subseteq \Class{X} \times \Class{X}\), we say:

\(\Class{Y}\) is \(\Class{R}\)-progressive if \[ \forall x \in \Class{X} .\, (\forall y \in \Class{X} .\, y\Class{R} x \rightarrow y \in \Class{Y}) \rightarrow x \in \Class{Y}. \]
\(y \in \Class{Y}\) is \(\Class{R}\)-minimal if \[ \neg \exists z \in \Class{Y} .\, z\Class{R} y. \]
A sequence \((x_n)_{n \in \N}\) in \(\Class{X}\) is \(\Class{R}\)-decreasing if \[ \forall n \in \N.\, x_{n+1} \Class{R} x_n. \]

Suppose \(\Class{R} \subseteq \Class{X} \times \Class{X}\) is a relation. Consider the following statements.

For every subclass \(\Class{Y} \subseteq \Class{X}\), if \(\Class{Y}\) is \(\Class{R}\)-progressive, then \(\Class{Y} = \Class{X}\).
Every nonempty subclass \(\Class{Y} \subseteq \Class{X}\) has an \(\Class{R}\)-minimal element.
There is no strict \(\Class{R}\)-decreasing infinite sequence in \(\Class{X}\).

Then \(1. \iff 2.\) and \(2. \implies 3.\). Also, \(3. \implies 2.\) holds under the axiom of dependent choice.

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

A relation \(\Class{R} \subseteq \Class{X} \times \Class{X}\) is well-founded if 1. (equivalently) from the previous proposition holds.

Any well-founded relation is irreflexive and acyclic.

A well-ordered class is a class \(\Class{X}\) together with a total order relation \(\leq\) such that the corresponding strict order \(<\) is well-founded.

Of particular interest are well-ordered sets (well-orders).

The following are equivalent for any partially ordered set \((X, \leq)\).

\((X, \leq)\) is a well-order.
Every nonemtpy subset of \(X\) has a minimum element.

\((\N, \leq)\)
Likewise, \(([n], \leq)\) (and every finite linear order)
Likewiser, for any ordinal \(\alpha\), the set \([\alpha]\) is a well-order under \(\leq\).

And actually, this last characterization is in some sense complete. In particular, we have the following theorem.

Classification theorem for well-orders

Every well-order is order-isomorphic to \([\alpha]\) for a unique ordinal \(\alpha\).

We write \(\operatorname{Ord}(X, \leq)\) for the unique \(\alpha\) such that \(X \cong [\alpha]\) for a well-order \((X, \leq)\). We call this the order type of \(X\).

Let us look at some corollaries before the proof.

The following are equivalent for well-orders \(A, B\).

\(A \cong B\)
\(\operatorname{Ord}(A) = \operatorname{Ord}(B)\)

An initial segment of a totally ordered class \((\Class{X}, \leq)\) is any \(\Class{Y} \subseteq \Class{X}\) that is down-closed, that is, \[ \forall y \in \Class{Y} , x \in \Class{X}.\, x < y \implies x \in \Class{Y}. \]

Comparison theorem for well-orders

The following are equivalent for well-orders \(A, B\).

There is an (order) embedding from \(A\) to \(B\).
\(A\) is isomorphic to an initial segment of \(B\).
\(\operatorname{Ord}(A) \leq \operatorname{Ord}(B)\).

For well-orders \(A\) and \(B\):

If \(A\) and \(B\) embed into each other, then \(A \cong B\) as an order isomorphism.
Either \(A\) embeds in \(B\) or \(B\) embeds in \(A\).

Let \((X, \leq_X)\) and \((Y, \leq_Y)\) be two well orders. We define a well-order on \(X + Y\) as "placing one after the other". as

\begin{align*} \iota_0(x) \leq_{X + Y} \iota_0(x') &\iff x \leq_X x' \\ \iota_1(y) \leq_{X + Y} \iota_1(y') &\iff y \leq_Y y' \\ \iota_0(x) \leq_{X + Y} \iota_1(y) &\iff \top \\ \iota_1(y) \leq_{X + Y} \iota_0(x) &\iff \bot \end{align*}

\[ \operatorname{X + Y, \leq_{X + Y}} = \operatorname{Ord}(X, \leq_X) + \operatorname{Ord}(Y, \leq_Y). \]

FINISH Product of well-orders

Let \((X, \leq_X)\) and \((Y, \leq_Y)\) be two well orders. We define a well-order on \(X \times Y\) as the reverse lexicographic ordering.

\[ \operatorname{X * Y, \leq_{X \times Y}} = \operatorname{Ord}(X, \leq_X) \cdot \operatorname{Ord}(Y, \leq_Y). \]

For the exponential, we want to define a well-order on a function space. In particular, we will have to restrict the functions we consider.

Let \((X, \leq_X)\) and \((Y, \leq_Y)\) be two well orders. Then \[ \operatorname{Ord}(\operatorname{finsupp}[X, Y], \leq_{Y^X}) = \operatorname{Ord}(Y)^{\operatorname{Ord(X)}}. \] Here we have \[ \operatorname{finsupp}[X, Y] = \left\{ f : X \rightarrow Y \mid \text{ the set } \left\{ x \in X \mid f(x) \neq \text{ the least of } Y \right\} \text{ is finite}\right\} \] Then \[ f <_{Y^X} g \iff f \neq g \text{ and } f(x_0) < g(x_0) \] where \(x_0 = \max \left\{ x \in X \mid f(x) \neq g(x) \right\}\).

In the special case \(Y = (\N, \leq)\) we have \[ \operatorname{finsupp}(X, \N) = \left\{ f : X \rightarrow \N \mid \left\{ x \mid f(x) \neq 0 \right\} \text{ is finite} \right\}. \]

We can look at this as finite multisets. This says that one multiset is below another by looking at the highest element which is assigned a different multiplicity - the left hand set needs to have a smaller multiplicity. We call this ordering \(<_{\N^X}\) the (Deschowitz-manna) multiset ordering. This leads us to multiset induction.

Lemma A

If \(f : A \rightarrow A\) is an embedding for \(A\) a well-order, \(f\) is inflationary, namely \[ \forall x \in A.\, x \leq f(x). \]

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

Lemma B

If \(I\) is a proper initial segment of a well-order \(A\), then \(I = [a]\) for some \(a \in A\).
If a set \(I\) is a proper initial segment of \(\Ord\), then \(I = [\alpha]\) for some ordinal \(\alpha\).

Rigidity theorem

No well order is isomorphic to any proper initial segment of itself.
Every well order has exactly one automorphism (the identity). We say it is rigid.
If \(A, B\) are isomorphic well-orders, then they have a unique isomorphism between them.

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

Transfinite recursion (uniform version)

Given \(\Class{A}\) a class and \(L : \pot \Class{A} \rightarrow \Class{A}\), there is a unique \(T : \Ord \rightarrow \Class{A}\) satisfying \[ T(\alpha) = L \left\{ T(\beta) \mid \beta < \alpha \right\}. \]

Proof of Classification theorem

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.

Cardinals

We define the cardinality of an ordinal as \[ \abs{\alpha} := \abs{[\alpha]}. \]

\begin{align*} \abs{\omega} &= \aleph_0 \\ \abs{\omega^{\omega}} &= \aleph_0 \\ &\vdots \\ \abs{\epsilon_0} &= \aleph_0 \end{align*}

Do there exist uncountable ordinals?

Hartogs' lemma

For any set \(A\) there exists a smallest ordinal \(\underline{h}(A)\) for which \[ \abs{\underline{h}(A)} \not \leq \abs{A}. \]

Implicitly we're defining a class function \(\underline{h} : \Class{\text{Set}} \rightarrow \Ord\).

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}. \] We call this function the Hartogs' function.

\(\underline{h}(\N)\) does not embed in \(\N\) and is thus not countable. So it must be the smallest uncountable ordinal. We define \[ \omega_1 := \underline{h}(\N) \]

With the Axiom of Choice, we have \(\underline{h}(A) > \abs{A}\), while not assuming it we only get the weaker \[ \abs{\underline{h}(A)} \not\leq \abs{A} \]

For any ordinal \(\alpha\), we have that \[ \underline{h}(\alpha) := \text{ the smallest ordinal } \beta \text{ with } \abs{\beta} > \abs{\alpha}. \]

In the notes.

Initial ordinals

An initial ordinal is an ordinal \(\alpha\) that satisfies, for every \(\beta < \alpha\), we have \[ \abs{\beta} < \abs{\alpha}. \]

We think of it as the smallest ordinal of its own cardinality.

Proposition B

For every set \(A\), \(\underline{h}(A)\) is an initial ordinal.

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.

(Proposition C): Every natural number \(n < \omega\) is an initial ordinal.
\(\omega\) is an initial ordinal.

Proposition D

Every infinite initial ordinal is a limit ordinal.

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

Lemma F

If \(I\) is a set of initial ordinals, then \(\sup I\) is an initial ordinal.

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

We shall count through (transfinitely) through the infinite initial ordinals \(\omega_{\alpha}\) for \(\alpha\) an ordinal. We start with

\begin{align*} \omega_0 &:= \omega \\ \omega_1 &:= \underline{h}([\omega_0]) \text{ the smallest uncountable ordinal}\\ \omega_2 &:= \underline{h}([\omega_1]) \\ \vdots & \\ \omega_{\omega} &= \sup_{\alpha < \omega} \omega_{\alpha} \text{ which is limit by lemma F} \\ \vdots & \end{align*}

We are in essence carrying out a definition by transfinite recursion.

We define \[ \omega_{(-)} : \Ord \rightarrow \Ord \] by transfinite recursion by

\begin{align*} \omega_0 &:= \omega \\ \omega_{\alpha + 1} &:= \underline{h}([\omega_{\alpha}]) \\ \omega_{\lambda} &:= \sup_{\alpha < \lambda} \omega_{\alpha} \end{align*}

\(\omega_{\alpha}\) is always an infinite initial ordinal
Every infinite initial ordinal arises as \(\omega_{\alpha}\) for a unique \(\alpha\).

We define the alephs as cardinalities of ordinals \[ \aleph_{\alpha} := \abs{\omega_{\alpha}}. \]

We have the notion of a smallest uncountable ordinal. We might wonder whether it holds that \(\abs{\omega_1} = \abs{\R}\), stated again, \(\abs{\R} = \aleph_1\), i.e. the continuum hypothesis.

Proposition E

If \(\alpha < \beta\), then \(\abs{\omega_{\alpha}} < \abs{\omega_{\beta}}\), hence \(\omega_\alpha < \omega_{\beta}\).

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

Proof of the property theorem

We prove this using transfinite induction using our propositions and lemmas.
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.

A set \(X\) is well-orderable if there exists some well-order with carrier set \(X\).

If \(Y \rightarrow X\) is an injection with \(X\) well-orderable, then \(Y\)is well-orderable.
If \(X \rightarrow Y\) is a surjection with \(X\) well-orderable, then \(Y\) is well-orderable

Suppose \(X\) is well-orderable and infinite. Then \(X\) is in bijection with \([\alpha]\) because \(\alpha\) can be taken to be the order type of some well-ordering of \(X\). Then \[ \abs{X} = \abs{[\alpha]} = \aleph_{\beta} \] for some \(\beta \in \Ord\).

Also, if \(\abs{Y} = \aleph_{\beta}\), then \(Y\) is well-orderable.

We have

\begin{align*} \aleph_{\alpha} + \aleph_{\beta} &= \aleph_{\max(\alpha, \beta)} \\ \aleph_{\alpha} \cdot \aleph_{\beta} &= \aleph_{\max(\alpha, \beta)} \end{align*}

This is easily proved by the following theorem.

Every aleph is its own square. \[ \aleph_{\alpha} = \aleph_{\alpha} \cdot \aleph_{\alpha}, \] i.e. \[ [\omega_{\alpha}] \cong [\omega_{\alpha}] \times [\omega_{\alpha}]. \]

We will prove this by defining an ordering on \(\Ord \times \Ord\) as \[ (0, 0) < (0, 1) < (1, 0) < (1, 1) < (0, 2) < (1, 2) < (2, 0) < (2, 1) < (2, 2) \] which we think of as organised in a square.

Generalising to the whole \(\Ord \times \Ord\), we define

\begin{align*} (\alpha_1, \alpha_2) \prec (\beta_1, \beta_2) \iff &\max(\alpha_1, \alpha_2) \prec \max(\beta_1, \beta_2) \\ \text{or } & \max(\alpha_1, \alpha_2) = \max(\beta_1, \beta_2) \text{ and } \alpha_1 < \beta_1 \\ \text{or } & \max(\alpha_1, \alpha_2) = \max(\beta_1, \beta_2) \text{ and } \alpha_1 = \beta_1 \text{ and } \alpha_2 < \beta_2 \end{align*}

\(\prec\) is a strict partial order on \(\Ord \times \Ord\)
Every nonempty class \(\Class{X} \subseteq \Ord \times \Ord\) has a \(\prec\)-minimum element.

For every \(\alpha\), we have that \([\alpha] \times [\alpha]\) is an initial segment of \(\Ord \times \Ord\) ordered by \(\prec\).

I can probably rewrite this using a reference. Should look these up for org.

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.

Axiom of Choice

Alephs are the cardinals of well-orderable sets. We've also seen well-orderable sets are closed under \(\times\) and \(+\), likewise for subsets and images. We have not yet shown well-orderable sets are closed under exponentiation, powerset, or infinite products. None of these preserve well-orderability without further assumptions.

In particular, we will discuss the Axiom of Choice today, which will imply that all sets are well-orderable.

A choice function on a set \(S\) of sets is a function \(f : S \setminus \{\emptyset\} \rightarrow \Class{U}\) satisfying \[ \forall x \in S .\, X \neq \emptyset \implies f(x) \in x. \]

The following are equivalent for a set \(X\).

\(X\) is well-orderable.
\(\pot X\) has a choice function.

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

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

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

Which sets of sets can we prove to have choice functions?

Any finite set of sets has a choice function.
\(\pot(X)\), when \(X\) is well-orderable.
In particular, \(\pot[\alpha]\) have choice functions.

We cannot prove, say, that \(\pot(\R)\) has a choice function.

Axiom of Choice (AC)

Every set of sets has a choice function.

We will not assume it as an axiom, but first investigate its properties.

The following are equivalent.

The axiom of choice
(The well-ordering principle): Every set is well-orderable
(Zorn's Lemma): If every chain in a partially ordered set has an upper bound, then the partially ordered set has a maximal element.

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

Each of the following is equivalent to the axiom of choice.

Every surjective function has a section, i.e. if \(X \xrightarrow{g} Y\) is surjective, then \(\exists Y \xrightarrow{f} X\) such that \(g \circ f : Y \rightarrow Y = \operatorname{id}_Y\).
Every equivalence relation has a set of representatives, i.e. if \(\sim \subseteq X \times X\) is an equivalence relation, then \(\exists B \subseteq X\) such that for every equivalence class \(A\), we have \(A \cap B\) is a singleton.
Every cartesian product of nonempty sets is nonempty, i.e. given \(A_{(-)} : I \rightarrow \Class{\mathrm{Set}}\), \(\forall i \in I .\, A_i \neq \emptyset\), then \(\prod\limits_{i \in I} A_i \neq \emptyset\).

\noindent

Recall the axiom of dependent choice.

Given

\noindent We used this to show that every infinite set is Dedekind infinite. We can improve the result slightly.

Every countable set of sets has a choice function

\noindent This version suffices for the statement of infinity sizes.

Assuming the axiom of countable choice, a countable union of countable sets is countable.

Under the axiom of dependent choice, If a set has no descending chains, it is well-founded.

\[ (\mathrm{AC}) \implies (\mathrm{DC}) \implies (\mathrm{CC}) \]

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.

An \(\alpha\)-sequence in \(X\) is a function \([\alpha] \rightarrow X\).

DC_\alpha

Suppose \(R \subseteq \bigcup\limits_{\beta < \alpha X^{[\beta]}} \times X\) is total. Then there exists \((x_{\beta}_{\beta < \alpha})\) satisfying \[ \forall \beta < \alpha .\, (x_{\gamma}_{\gamma < \beta}) R x_{\beta}. \]

\noindent It is somewhat difficult to find examples. There exist some in the field of stochastic analysis.

\[ (\mathrm{DC}) \iff (\mathrm{DC}_{\alpha}) \]

The axiom of choice is equivalent to \(\alpha\)-dependent choice for all ordinals: \[ (\mathrm{AC}) \iff \forall \alpha .\, (\mathrm{DC}_{\alpha}). \]

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

\begin{align*} x_{(-)} : [\alpha] &\rightarrow X \text{ by transfinite recursion} \\ x_{\beta} &= g \left\{ y \in X \mid (x_{\gamma})_{\gamma < \beta} R y \right\} \end{align*}

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.

\[ \alpha \leq \beta \implies (\mathrm{DC}_{\beta}) \implies (\mathrm{DC}_{\alpha}). \]

\[ (\mathrm{DC}_{\omega_{\alpha}}) \implies \forall \beta < \omega_{\alpha + 1}.\, (\mathrm{DC}_{\beta}) \]

\alpha-Bounded Zorn's lemma

Suppose \(P\) is a partial order satisfying

every well-ordered chain has order type \(< \alpha\),
every ordered chain has an upper bound.

Then \(P\) has a maximal element.

(Wolk 1983)

For a limit ordinal \(\lambda\), we have \[ (\mathrm{DC}_{\lambda}) \iff (\mathrm{ZL}_{\lambda}) \]

Cardinal arithmetic with choice

For this lecture, we will assume the axiom of choice. We will still flag its usage. The axiom makes some things more straightforward and flattens a lot of concepts.

Every infinite cardinality is an aleph. If \(X\) is infinite, then \(\abs{X} = \aleph_{\alpha}\) for a unique ordinal \(\alpha\).
Every infinite cardinality is its own square. This already implies choice!
Cardinalities are linearly ordered. Since infinte cardinalities are alephs, they inherit the order from the ordinals. This is also equivalent to choice.
Under the axiom of choice, the relations \(<\) become equivalent to \(\ll\).
For all infinite sets \(X, Y\), we have \[ \abs{X} + \abs{Y} = \max(\abs{X}, \abs{Y}) = \abs{X} \times \abs{Y}. \]

Suppose \(X_{(-)} : I \rightarrow \Class{\text{Set}}\) to be a family of sets. We defined \[ \sum\limits_{i\in I} X_i := \left\{ (i, x) \mid i \in I, x \in X_i \right\} \] and \[ \prod\limits_{i \in I} X_i := \left\{ f : I \rightarrow \bigcup\limits_{i \in I} X_i \mid \forall i \in I .\, f(i) \in X_i \right\} \] as the family of choice functions. We sometimes write a choice function as \((X_i)_{i \in I}\) and call it a family of elements.

These operations are functorial. If \((f_i : X_i \rightarrow Y_i)_{i\in I}\) then we can derive the functions

\begin{align*} \sum\limits_{i\in I} X_i &\rightarrow \sum\limits_{i \in I} Y_i & \sum\limits_{i\in I} X_i &\rightarrow \prod\limits_{i \in I} Y_i \\ \sum\limits_{i\in I} f_i := (i, x) &\mapsto (i, f_i(x)) & \prod\limits_{i\in I} f_i := g &\mapsto (i \mapsto f_i(g(i))) \end{align*}

which obviously preserve identity and composition, i.e. are factorial.

Suppose \((X_i)_{i \in I}\) and \((Y_i)_{i\in I}\) enjoy the property that \[ \forall i \in I.\, \abs{X_i} \leq \abs{Y_i}, \] then \[ \abs{\sum\limits_{i\in I} X_i} \leq \abs{\sum\limits_{i\in I} Y_i} \text{ and } \abs{\prod\limits_{i\in I} X_i} \leq \abs{\prod\limits_{i\in I} Y_i} \]

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.

\noindent Note the proof uses the axiom of choice when we take a specific family \(f_i : X_i \rightarrow Y_i\).

Suppose \((X_i)_{i \in I}\) and \((Y_i)_{i\in I}\) enjoy the property that \[ \forall i \in I.\, \abs{X_i} = \abs{Y_i}, \] then \[ \abs{\sum\limits_{i\in I} X_i} = \abs{\sum\limits_{i\in I} Y_i} \text{ and } \abs{\prod\limits_{i\in I} X_i} = \abs{\prod\limits_{i\in I} Y_i} \]

CSB.

It also makes sense to talk about operations on families of cardinals. If \((\kappa_i)_{i \in I}\) is a family of cardinals, i.e. initial ordinals, then we say

\begin{align*} \sum\limits_{i \in I} \kappa_i &:= \abs{\sum\limits_{i \in I} [\kappa_i]} \\ \prod\limits_{i \in I} \kappa_i &:= \abs{\prod\limits_{i \in I} [\kappa_i]} \end{align*}

Note that \([\kappa_i]\) is the set of ordinals less than \(\kappa_i\).

Suppose \(\lambda\) and \(\kappa\) are cardinalities. We can consider the sum \[ \sum\limits_{\alpha < \lambda} \kappa = \lambda \cdot \kappa. \] i.e. self-sum \(\kappa\) \(\lambda\)-many times. It's true in general that \[ \sum\limits_{i \in I}^{} X = I \times X \] (because we have no dependency in the second component). Let us consider the general case.

FINISH Give name

Suppose \(\lambda\) is an infinite cardinal and \((\kappa_{\alpha})_{\alpha < \lambda}\) are nonzero cardinals. Then \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \lambda \cdot \left( \sup_{\alpha < \lambda} \kappa_{\alpha} \right). \]

We need to prove \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \lambda \cdot \kappa. \] 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.

If \(\lambda \leq \sup_{\alpha < \lambda} \kappa_{\alpha}\) then \[ \sum\limits_{\alpha < \lambda}^{} \kappa_{\alpha} = \sup_{\alpha < \lambda} \kappa_{\alpha}. \]

König's theorem

If \((\kappa_i)_{i \in I}\) and \((\lambda_i)_{i \in I}\) are families of cardinals with \(\kappa_i \ll \lambda_i\) for every \(i \in I\). Then \[ \sum\limits_{i \in I}^{} \kappa_i \ll \prod\limits_{i \in I}^{} \lambda_i. \]

\noindent

We can use this to rederive Cantor's theorem.

For any cardinality \(\kappa\), we have \(\kappa < 2^{\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

\begin{align*} \sum\limits_{i \in I}^{} [\kappa_i] &\rightarrow \prod\limits_{i \in I}^{} [\lambda_i] \\ (i, \alpha) &\mapsto \left(j \mapsto \begin{cases} \alpha & \text{ if } j = i \\ \kappa_j & \text{ if } j \neq i \end{cases} \right) \end{align*}

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.

\noindent

Cardinal exponentiation is a special case of products. In particular, \[ \kappa^{\lambda} = \prod\limits_{\alpha < \lambda}^{}. \] Cardinal exponentiation enjoys expected laws. \[ \left( \prod\limits_{i \in I}^{} \kappa_i \right)^{\lambda} = \prod\limits_{i \in I}^{} \kappa_i^{\lambda} \text{ and } \kappa^{\sum\limits_{i \in I}^{} \lambda_i} = \prod\limits_{i \in I}^{} \left( \kappa^{\lambda_i} \right) \]

The question now is to find a \(\gamma\) so that \(\aleph_{\alpha}^{\aleph_{\beta}} = \aleph_{\gamma}\). This question arguably has no good answer. One potential answer is given by the generalised continuum hypothesis (GCH): For any infinite \(\aleph_{\alpha}\) we have \[ 2^{\aleph_{\alpha}} = \aleph_{\alpha + 1}. \] If we have this, everything can be answered. Sadly both it and its negation are independent from our axioms.

We can prove two things.

(A) \(2^{\aleph_{\alpha}} \geq \aleph_{\alpha + 1}\)
(B) \(\alpha \leq \beta \implies 2^{\aleph_{\alpha}} \leq 2^{\aleph_{\beta}}\)

For the next statement we will need a few more definitions.

For every \(\alpha\), we have \[ \operatorname{cf}(2^{\aleph_{\alpha}}) > \aleph_{\alpha}. \]

For a limit ordinal \(\gamma\), an increasing sequence of ordinals of length \(\gamma\) is \((\alpha_\beta)_{\beta < \gamma}\) satisfying \[ \beta < \beta' \implies \alpha_{\beta} < \alpha_{\beta'}. \] The limit of such a sequence is \[ \lim_{\beta \rightarrow \gamma} \alpha_{\beta} := \sup_{\beta < \gamma} \alpha_{\beta}. \]

If \(\alpha\) is a limit ordinal, then its cofinality \(\operatorname{cf}(\alpha)\) is the smallest ordinal \(\gamma\) such that \(\alpha\) is the limit of an increasing sequence of ordinals of length \(\gamma\).

\(\operatorname{cf}(\omega) = \omega\), since we can see \(\omega\) as a limit of the naturals.
\(\operatorname{cf}(\omega^2) = \omega\) since \(\omega^2 = \lim \omega, \omega \cdot 2, \omega \cdot 3, \cdots\)
\(\operatorname{cf}(\omega_1) = \omega_1\) since \(\omega_1 = \lim_{\alpha \rightarrow \omega} \alpha\)
Similarly, \(\operatorname{cf}(\omega_2) = \omega_2\) and so on.
\(\operatorname{cf}(\omega_{\omega}) = \omega\) since \[ \omega_{\omega} = \lim \omega, \omega_1, \omega_2, \dots \] i.e. we approximate it with an \(\omega\)-chain of ordinals.

\noindent

Theorem: initiality of cofinality noindent

We always have that \(\operatorname{cf}(\alpha)\) is always an infinite initial ordinal, i.e. an \(\aleph\).

\noindent Thus we often write \(\operatorname{cf}(\omega) = \omega = \aleph_0\) and the like.

\(\operatorname{cf}(\aleph_0) = \operatorname{cf}(\omega) = \omega = \aleph_0\)
\(\operatorname{cf}(\aleph_1) = \operatorname{cf}(\omega_1) = \omega_1 = \aleph_1\)
\(\operatorname{cf}(\aleph_2) = \operatorname{cf}(\omega_2) = \omega_2 = \aleph_2\)
\(\operatorname{cf}(\aleph_{\omega}) = \operatorname{cf}(\omega_{\omega}) = \omega = \aleph_0\)

By the cofinality theorem, we get

\begin{align*} 2^{\aleph_0} &\neq \aleph_0 \\ &= \aleph_1 \text{ is possible} \\ &= \aleph_2 \text{ is possible} \\ &\vdots\\ &\neq \aleph_{\omega} \text{ is ruled out by the theorem} \\ &= \aleph_{\omega + 1} \text{ is possible} \\ &\vdots \end{align*}

Before we prove the above theorem C, we will have a few technical lemmata.

Every infinite cardinal \(\kappa\) can be expressed as \[ \kappa = \sum\limits_{\alpha < \operatorname{cf}(\kappa)}^{} \kappa_{\alpha} \] where we have \(\kappa_{\alpha} < \kappa\) for every \(\alpha < \operatorname{cf}(\kappa)\).

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.

FINISH Applications of choice

Regular and inaccessible cardinals

\(\operatorname{cf}(\alpha) \leq \alp
If \(\alpha\) is not a cardinal (i.e. it is not an initial ordinal), then \(\operatorname{cf}(\alpha) < \alpha\).
We have \(\operatorname{cf}(\operatorname{cf}(\alpha))\)

For any limit ordinal \(\alpha\), \(\operatorname{

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

An infinite cardinal \(\kappa\) is regular if \(\operatorname{cf}(\kappa) = \kappa\). It is singular if \(\operatorname{cf}(\kappa) < \kappa\).

An infinite cardinal \(\aleph_{\alpha}\) is a successor cardinal if \(\alpha\) is a successor ordinal. It is a limit cardinal if \(\alpha\) is a limit ordinal.

Every infinite successor cardinal is regular.

\noindent Before proceeding to the proof we will have two lemmas. The first one we have already seen.

A cardinal \(\kappa\) is singular if and only if we have \[ \kappa = \sum\limits_{i \in I}^{} \kappa_i \] where \(\abs{I} < \kappa\) and every \(\kappa_i < \kappa\).

\((\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}. \]

An infinite cardinal is weakly inaccessible if it is an uncountable, regular limit cardinal.

\noindent We have various large cardinal axioms,

There exists a weakly inaccessible cardinal.

\noindent Note that we can prove neither WIC nor \(\neg\)WIC from the axioms.

Suppose \(\aleph_{\lambda}\) is a weakly inaccessible cardinal. This means \(\lambda\) is a limit cardinal. We show that \(\lambda = \aleph_{\lambda}\). We have \[ \aleph_{\lambda} = \lim_{\alpha \rightarrow \lambda} \aleph_{\alpha} \] as \(\lambda\) is a limit ordinal. We have \(\lambda \geq \operatorname{\aleph_{\lambda}} = \aleph_{\lambda}\). Note that we always have \(\alpha \leq \omega_{\alpha} = \aleph_{\alpha}\), so indeed \(\aleph_{\lambda} = \lambda\).

We had that \(\kappa\) is a limit cardinal if and only if for any \(\aleph_{\alpha} < \kappa \), we also have \(\aleph_{\alpha+ 1} < \kappa\). We can expand the definition slightly.

\(\kappa\) is a strong limit cardinal if for any \(\kappa' < \kappa\), we also have \(2^{\kappa'} < 2^{\kappa}\).

\noindent For instance, \(\aleph_{\omega}\) is a limit cardinal, but we cannot prove it is a strong limit cardinal.

We have the so called beth cardinals: \[ \underbrace{\aleph_0}_{\beth_0}, \underbrace{2^{\aleph_0}}_{\beth_1}, \underbrace{2^{2^{\aleph_0}}}_{\beth_2}, \cdots \text{limit} &= \beth_{\omega} \]

\noindent Every strong limit cardinal is a limit cardinal. If the generalised continuum hypothesis holds, then every limit cardinal is a strong limit.

A cardinal is strongly inaccessible if it is an uncountable, regular, strong limit cardinal.

There exists a strongly inaccessible cardinal.

\noindent

A Grothendieck universe is a set \(\mathcal{U}\) satisfying

(Transitivity): Whenever \(X \in \mathcal{U}\) is a set and \(x \in X\), it holds that \(x\in \mathcal{U}\).
(Unordered pair): If \(x, y \in \mathcal{U}\), then \(\left\{ x, y \right\} \in \mathcal{U}\)
(Powerset): If \(x, y \in \mathcal{U}\), then \(\pot X \in \mathcal{U}\)
(Unions): If \(I \in \mathcal{U}\) is a set and \((X_i)_{i \in I}\) is a family where every \(X_i \in \mathcal{U}\) is a set, we have \[ \bigcup\limits_{i \in I}^{} X_i \in \mathcal{U}. \]

Some examples of Grothendieck unvierses are

\(\emptyset\)
The set of all hereditarily finite sets

\noindent In some sense these are all the examples, as elucidated by the following theorem.

The following are equivalent.

There exists a Grothendieck universe containing an infinite set.
SIC, i.e. the existence of a strongly inaccessible cardinal.

(Overview)

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.

\noindent Let us elucidate the \(V_{\kappa}\) from the cumulative hierarchy.

We define the cumulative hierarchy by transfinite recursion. We consider the map \(V_{(-)} : \Ord \rightarrow \Class{Set}\). Then

\begin{align*} V_0 &:= \emptyset \\ V_{\alpha + 1} &:= \pot V_{\alpha} \\ V_{\lambda} := \bigcup\limits_{\alpha < \lambda}^{} V_{\alpha} \text{ for } \lambda \text{ a limit ordinal.} \end{align*}

\noindent The full cumulative hierarchy \[ \Class{V} := \bigcup\limits_{\alpha}^{} V_{\alpha} \] is a proper class. In particular, this is the class of all sets that are

hereditary,
well-founded.

Note however, that for every \(\alpha\), it is obvious that \(V_{\alpha}\) is a set.

If we have \(\alpha \leq \beta\), it follows that \(V_{\alpha} \subseteq V_{\beta}\).
For a finite \(n\), \(V_n\) has the cardinality \(2^{2^{\udots }^{2^0}}\) for \(n\) 2s.
\(V_{\omega}\) is the set of hereditarily finite sets.
We have \(\operatorname{vN}(\omega) \in V_{\omega + 1}\) and also \(\operatorname{vN}(\alpha) \in V_{\alpha + 1}\)

if \(X \in V_{\alpha}\), then we have \(\pot X \in V_{\alpha + 1}\).