Kardinalna aritmetika (Simpson)
Warning: The notes are not optimized for HTML (yet). Without warranty.
Lecture 1 - Introduction
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.
\[ 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}\).
Not every class is a set.
Let \[ \underline{R} = \{x \mid x \text{ is a set and } x \not\in x\} \] be a class. If \(\underline{R}\) were a set, then \[ \underline{R} \in \underline{R} \iff \underline{R} \not\in \underline{R}, \] a contradiction.
If \(\underline{X}, \underline{Y}\) are classes and \(\forall z.\, z \in \underline{X} \iff z \in \underline{Y}\), then \(\underline{X} = \underline{Y}\).
\(\emptyset := \{x \mid \bot\}\) is a set.
For any \(x, y\), \(\{x, y\} := \{z \mid z = x \lor z = y\}\) is a set. In particular \(\{x\} := \{x,x\}\) is a set.
For a class \(\underline{X}\) of sets, \[ \bigcup \underline{X} := \{z \mid \exists Y \in \underline{X}.\, z \in Y\}. \] If \(X\) is a set of sets, then \(\bigcup X\) is a set.
For a class \(\underline{X}\), we define its powerclass as \[ \mathcal{P}\underline{X} := \{Y \mid Y \text{ is a subset of } \underline{X}\}. \] If \(X\) is a set, then \(\mathcal{P}X\) is a set. We call it a powerset.
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.
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 \(\underline{X}\) to \(\underline{Y}\) is a property \(F(x,y)\) of elements \(x,y\) of \(\mathcal{U}\) satisfying:
- For all \(x \in \underline{X}\) there exists a unique \(y \in \underline{Y}\) such that \(F(x,y)\).
- If \(F(x,y)\), then \(x \in \underline{X}\) and \(y \in \underline{Y}\).
Then \[ \operatorname{image}(F) := \{y \in \underline{Y} \mid \exists x \in \underline{X}.\, F(x,y)\}. \]
A product of classes \(\underline{X}\) and \(\underline{Y}\) is a class \(\underline{X} \times \underline{Y}\) together with class functions \(\pi_1 : \underline{X} \times \underline{Y} \rightarrow \underline{X}\) and \(\pi_2 : \underline{X} \times \underline{Y} \rightarrow \underline{Y}\) satisfying \[ \forall x \in \underline{X}.\, \forall y \in \underline{Y}.\, \exists! z \in \underline{X} \times \underline{Y}.\, \pi_1(z) = x \land \pi_2(z) = y. \]
Any two products of \(\underline{X}\) and \(\underline{Y}\) are isomorphic.
For every \(\underline{X}\) and \(\underline{Y}\), a product \(\underline{X} \times \underline{Y}\) with \(\pi_1, \pi_2\) exists.
Define \[ \underline{X} \times \underline{Y} := \left\{ \left\{ \{x\}, \{x, y\} \right\} \mid x \in \underline{X},\, y \in \underline{Y} \right\} \] and \[ \pi_1(z) := \text{the unique } x \in \underline{X} \text{ such that } \exists y \in \underline{Y}.\, z = \{\{x\}, \{x,y\}\}, \] and similarly for \(\pi_2\).
If \(X\) and \(Y\) are sets, then so is \(X \times Y\).
Suppose \(F : \underline{X} \rightarrow \underline{Y}\) is a class function. Its graph is \[ \Gamma(F) := \{(x, y) \in \underline{X} \times \underline{Y} \mid y = F(x)\} \subseteq \underline{X} \times \underline{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 \[ \underline{Y}^{X} := \left\{ \Gamma(F) \mid F : X \rightarrow \underline{Y} \text{ is a function} \right\}. \]
If \(Y\) is a set then \(Y^X\) is a set.
A natural number structure is a triple \((\underline{N}, 0, S)\) where \(\underline{N}\) is a class, \(0 \in \underline{N}\), and \(S : \underline{N} \rightarrow \underline{N}\) satisfying:
- \(S\) is injective: \(\forall x, y \in \underline{N}.\, S(x) = S(y) \implies x = y\).
- Acyclicity: \(\forall x \in \underline{N}.\, S(x) \neq 0\).
- Induction: if \(\underline{X}\) satisfies \(0 \in \underline{X}\) and \(\forall x \in \underline{N}.\, x \in \underline{X} \implies S(x) \in \underline{X}\), then \(\underline{N} \subseteq \underline{X}\).
A natural number structure exists.
Construct \(\underline{N}\) as the class of Von Neumann natural numbers (see below).
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 : \underline{N} \rightarrow \mathcal{A}\) such that
- \(R(0) = a\),
- \(R(S(x)) = F(R(x))\).
Suppose \(\mathcal{A}\) is a class, \(\mathcal{Z}\) is a class, \(a : \mathcal{Z} \rightarrow \mathcal{A}\), and \(F : \mathcal{Z} \times \mathcal{A} \rightarrow \mathcal{A}\). Then there exists a unique class function \(R : \mathcal{Z} \times \underline{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} = \underline{N}\), \(\mathcal{Z} = \underline{N}\), \(B(z) = z\), and \(F(z, x) = S(x)\). The unique resulting \[ R : \underline{N} \times \underline{N} \rightarrow \underline{N} \] satisfies
\begin{align*} R(z, 0) &= z, \\ R(z, S(x)) &= S(R(z, x)). \end{align*}This \(R\) is addition on \(\underline{N}\).
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}\}. \]
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
Lecture 2 - Comparison of cardinalities
Suppose \(A\) is a set and \(\underline{B}\) a class and we have \[ A \twoheadrightarrow \underline{B} \] surjective, then \(\underline{B}\) is a set (replacement).
Suppose \(\underline{A}\) is a class and \(B\) a set and we have \[ A \underline{}\rightarrowtail B, \] then \(\underline{A}\) is a set (separation + replacement).
We will see how crazily big sets will get, hence them being small really is only in comparison to classes.
Two sets \(A, B\) have the same cardinality (bijective correspondene, isomorphic, equipotent), if there exists a bijective function \[ f : A \rightarrow B. \]
Our notation will be \[ \abs{A} = \abs{B}. \] We don't yet have an independent meaning for \(\abs{A}\).
Since \(\abs{\cdot} = \abs{\cdot}\) is an isomorphism, it is in particular an equivalence relation.
A set \(A\) has cardinality less than or equal to a set \(B\) if there exists an injective function \[ i : A\rightarrowtail B. \]
We write \[ \abs{A} \leq \abs{B}. \]
- The relation is obviously reflexive and transitive due to monomorphism composition.
- We have antisymmetry due to a deeper theorem: CSB.
- We also wonder about linear ordering - we will get this, but only under choice.
Assume \(\abs{A} \leq \abs{B}\) and \(\abs{B} \leq \abs{A}\). Then \(\abs{A} = \abs{B}\).
We have injective functions \[ f : A \rightarrow B \quad g : B \rightarrow A. \] Define \(A_0 = A\) and \(B_0 = \im(g)\).
Then \[ g \circ f : A \rightarrow B_0 \] is injective so \(\abs{A_0} \leq \abs{B_0}\). By using the CSB lemma, we have \[ \abs{A} = \abs{A_0} = \abs{B_0} = \abs{B}. \]
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
\begin{align*} A_{n+1} &:= f(A_n) \\ B_{n+1} &:= f(B_n) \end{align*}Define \(C_n = A_n \setminus B_n \) and \[ C = \bigcup\limits_n C_n \] and \[ D = A_0 \setminus C \] Then \[ 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. \]
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}. \]
- Irreflexive and transitive.
- \(\abs{A} \leq \abs{B} < \abs{C} \leq \abs{D} \implies \abs{A} < \abs{D}\).
- Not linear, even with choice.
\(\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 again have the sandwiching property \[ \abs{A} \leq \abs{B} \ll \abs{C} \leq \abs{D} \implies \abs{A} \ll \abs{D}. \]
The standard finite sets are, for \(n \in \N\), \[ [n] = \{m \in \N \mid m < n\}. \]
Herein we define \[ [\cdot] : \N \rightarrow \pot \N \] using the recursion theorem.
- \[ \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.
The left implication is trivial.
Right implication, use induction.
A set \(A\) is finite if there exists \(n \in \N\) such that \(\abs{A} = \abs{[n]}\). In this case we define \(\abs{A} = n\).
Note that this is well defined, since there is a unique such \(n\).
- 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\).
A set \(A\) is infinite if it is not finite.
Consider the following.
- \(X\) is infinite.
- There exists a proper subset \(X' \subseteq X\) such that \(\abs{X} = \abs{X'}\).
- There exists a proper injection \(i : X \rightarrowtail X\).
- \(\abs{\N} \leq \abs{X}\).
We also call statement 2 Dedekind infinite.
Then we have \[ 1 \impliedby 2 \iff 3 \iff 4. \] But \(1 \implies 4\) requires the axiom of (countable) choice.
\(1 \implies 4\). Suppose \(X\) is infinite. We define an injection, that is a sequence 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.
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 \(\aleph_0 = \abs{\N}\).
- A set \(X\) is countable if \(\abs{X} \leq \aleph_0\).
- If \(X\) is countable and infinite, then we call it countably infinite.
Examples of countable sets are \(\N, \Z, \Q, \N \times \N\).
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.
A set \(X\) is uncountable if it is not countable.
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}\). 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.
Lecture 3 - Basic Cardinal Arithmetic
The covariant powerclass operation is functorial. That is, if \(f : X \rightarrow Y\) is a function, then we have a function \[ \mathcal{P}f : \mathcal{P}X \rightarrow \mathcal{P}Y \] defined by \(\mathcal{P}f(A) = \{f(a) \mid a \in A\}\). Note that \(\mathcal{P}\) preserves identities and composition.
The operation \(X \mapsto \mathcal{P}X\) on sets \(X\) preserves cardinal inequalities:
\begin{align*} \abs{X} \leq \abs{Y} &\implies \abs{\mathcal{P}X} \leq \abs{\mathcal{P}Y}, \\ \abs{X} = \abs{Y} &\implies \abs{\mathcal{P}X} = \abs{\mathcal{P}Y}. \end{align*}Functors preserve isomorphisms and split monomorphisms.
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.
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*}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\).
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 \xhookrightarrow{\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}\).
For any set \(X\), we have \[ \abs{X} \ll 2^{\abs{X}}. \]
If \(\aleph_0 \leq \abs{X} \leq 2^{\aleph_0}\), then either \(\abs{X} = \aleph_0\) or \(\abs{X} = 2^{\aleph_0}\).
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.
Lecture 4 - 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.
An ordinal structure is given by a class \(\underline{\text{Ord}}\) of ordinals, a partial order \(\leq\) on \(\text{\underline{Ord}}\) and
- an element \(0 \in \text{\underline{Ord}}\), i.e. zero,
- a class function \(s : \text{\underline{Ord}} \rightarrow \text{\underline{Ord}}\), i.e. the successor, and
- a class function \(\sup : \text{\underline{Ord}} \rightarrow \text{\underline{Ord}}\), i.e. the supremum.
The following must hold.
- \(\forall \alpha \in \text{\underline{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 \text{\underline{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 \(\underline{X} \subseteq \text{\underline{Ord}}\) is such that
- (base case): \(0 \in \underline{X}\),
- (step case): \(\alpha \in \underline{X} \implies s(\alpha) \in \underline{X}\),
- (supremum case): For every subset \(A \subseteq \underline{X}\), we have \(\supA \in \underline{X}\),
then \(\underline{X} = \text{\underline{Ord}}\).
For ease of readability, we often write \(\alpha + 1\) instead of \(s(\alpha)\).
\(\leq\)is a linear order on \(\text{\underline{Ord}}\).
Let \(\beta \in \text{\underline{Ord}}\) be arbitrary. We will prove that \[ \alpha \leq \beta \lor \beta \leq \alpha \] holds for all \(\alpha \in \text{\underline{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
\[
\supA \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 \text{\underline{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{\underline{A}}\) is a set. Then \[ [\sup A] = \bigcup\limits_{\alpha \in A} [\alpha] \] is a set, because sets are closed under set-indexed unions.
\(\text{\underline{Ord}}\) is a proper class.
Suppose \(\text{\underline{Ord}}\) is a set.
Then \(\sup(\text{\underline{Ord}})\) is a maximum element in the set of ordinals. But this cannot be, because \(s(\sup(\text{\underline{Ord}}))\) is strictly larger.
The ordinals separate into two kinds.
- \(\alpha \in \text{\underline{Ord}}\) is a successor ordinal if there exists \(\alpha' \in \text{\underline{Ord}}\) such that we have \[ \alpha = \alpha' + 1 \]
- \(\alpha \in \text{\underline{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 \(\underline{X} \in \text{\underline{Ord}}\) satisfies
- \(0 \in \underline{X}\),
- \(\alpha \in \underline{X} \implies s(\alpha) \in \underline{X}\),
- \([\lambda] \subseteq \underline{X} \implies \lambda \in \underline{X} \), where \(\lambda > 0\) is a limit ordinal,
then \(\underline{X} = \text{\underline{Ord}}\).
If \(\underline{X} \subseteq \text{\underline{Ord}}\) satisfies \[ [\alpha] \subseteq \underline{X} \implies \alpha \in \underline{X}, \] then \(\underline{X} = \text{\underline{Ord}}\).
Let \(\underline{A}\) be a class with \(a \in \underline{A}\) and \(F : \underline{A} \rightarrow \underline{A}\), and \(L : \mathcal{P}\underline{A} \rightarrow \underline{A}\). There is a unique class function \[ T : \underline{Ord} \rightarrow \underline{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 \underline{A}\), \(F : \underline{A} \rightarrow \underline{A}\) and \(L : \mathcal{P} \underline{A} \rightarrow \underline{A}\) as above. We need to prove the existence of a suitable \(T : \text{\underline{Ord}} \rightarrow \underline{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 \underline{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 \underline{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 \text{\underline{Ord}}, \exists! \gamma-\text{approximation } t_{\gamma} : [\gamma] \rightarrow \underline{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 \(\underline{A}\) and \(\underline{Z}\) are classes with class functions
\begin{align*} B : \underline{Z} &\rightarrow \underline{A} \\ F : \underline{Z} \times \underline{A} &\rightarrow \underline{A} \\ L : \underline{Z} \times \mathcal{P}\underline{A} &\rightarrow \underline{A} \end{align*}Then there is a unique class function \(T : \underline{Z} \times \text{\underline{Ord}} \rightarrow \underline{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 : \text{\underline{Ord}} \times \text{\underline{Ord}} \rightarrow \text{\underline{Ord}}\) using
\begin{align*} B(\alpha) &= \alpha \\ F(\alpha, \beta) &= \beta + 1 \\ L(\alpha, A) &= \sup A \end{align*}Then \(T : \text{\underline{Ord}} \times \text{\underline{Ord}} \rightarrow \text{\underline{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 \((+) : \text{\underline{Ord}} \times \text{\underline{Ord}} \rightarrow \text{\underline{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)\).
Ordinal addition is not commutative
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) : \text{\underline{Ord}} \times \text{\underline{Ord}} \rightarrow \text{\underline{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)} : \text{\underline{Ord}} \times \text{\underline{Ord}} \rightarrow \text{\underline{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}\).
An ordinal structure exists.
We define \(\text{\underline{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.