Set Theory

Ordinals

Table of contents

Isomorphisms and Initial Segments of Well-Ordered Sets

Notation:

Let \(A\) be a well-ordered set with \(\preccurlyeq_{A}\). We denote \[ \prec_{A}:=\{(a_{0},a_{1})\in A\times A:a_{0}\preccurlyeq_{A}a_{1}\text{ and }a_{0}\neq a_{1}\}. \]

Definition:

Let \(A,B\) be well-ordered sets with \(\preccurlyeq_{A},\preccurlyeq_{B}\), respectively. If there exists a one-to-one and onto function \(f:A\rightarrow B\) such that for every \(\{a_{0},a_{1}\}\subseteq A\), \(a_{0}\preccurlyeq_{A}a_{1}\) if and only if \(f(a_{0})\preccurlyeq_{B}f(a_{1})\), then we say that \(A\) and \(B\) are isomorphic, write \(A\simeq B\), and call \(f\) an isomorphism.

Corollary:

Isomorphism of well-ordered sets is an equivalence relation.

Claim:

Let \(A\) be a well-ordered set with \(\preccurlyeq\), let \(B\subseteq A\) be isomorphic to \(A\), and let \(f:A\rightarrow B\) be the isomorphism between them. Then for every \(a\in A\), \(a\preccurlyeq f(a)\).

Proof:

Write \(X:=\{a\in A:f(a)\prec a\}\), and assume for contradiction that \(X\neq\emptyset\). Then there exists \(b:=\min X\). We have \(f(b)\prec b\), and also \(f(f(b))\prec f(b)\), so \(f(b)\in X\), contradicting the minimality of \(b\).

Definition:

Let \(A\) be a well-ordered set with \(\preccurlyeq\), and let \(A_{0}\subset A\). We say that \(A_{0}\) is an initial segment of \(A\) if there exists \(a_{0}\in A\) such that \[ A_{0}=\{a\in A:a\prec a_{0}\}. \] We denote this initial segment by \(A[a_{0}]=A_{0}\).

Claims:

Let \(A\) be a well-ordered set with \(\preccurlyeq\). Then:

1. For every initial segment \(B\) of \(A\), \(A\) and \(B\) are not isomorphic.
2. There is only one isomorphism from \(A\) to itself.
3. For every well-ordered \(B\) isomorphic to \(A\), there is only one isomorphism between \(A\) and \(B\).

Proofs:

1. Let \(a\in A\), and assume for contradiction that there exists an isomorphism \(f:A\rightarrow A[a]\). Then \(a\preccurlyeq f(a)\in A[a]\), contradicting the definition of \(A[a]\).
2. Let \(f:A\rightarrow A\) be an isomorphism. Then \(f\) is invertible, and \(f^{-1}\) is also an isomorphism. Hence, for every \(a\in A\), \(a\preccurlyeq f(a)\) and \(a\preccurlyeq f^{-1}(a)\). Therefore \(f^{-1}(a)\preccurlyeq f^{-1}(f(a))=a\), and so \(a=f(a)\). Thus \(f\) is the identity function.
3. Let \(f,g:A\rightarrow B\) be isomorphisms. Then \(f^{-1}\circ g:A\rightarrow A\) is an isomorphism, so it is the identity function, and therefore \(f=g\).

Claims:

Let \(A\) be a well-ordered set with \(\preccurlyeq_{A}\), and let \(a_{0}\in A\). Then:

1. If \(a_{1}\in A\) and \(A[a_{0}]\simeq A[a_{1}]\), then \(a_{0}=a_{1}\).
2. Let \(B\) be a well-ordered set isomorphic to \(A\), with \(\preccurlyeq_{B}\), and denote the isomorphism between them by \(g\). Then \(g\bigl|_{A[a_{1}]}\) is an isomorphism between \(A[a_{1}]\) and \(B[g(a_{1})]\).
3. Let \(B\) be a well-ordered set isomorphic to \(A\), with \(\preccurlyeq_{B}\), denote the isomorphism between them by \(g\), and let \(b_{1}\in B\). Then \(g\bigl|_{A[g^{-1}(b_{1})]}\) is an isomorphism between \(A[g^{-1}(b_{1})]\) and \(B[b_{1}]\).

Proofs:

1. Assume for contradiction that \(a_{0}\neq a_{1}\), and without loss of generality that \(a_{0}\prec_{A}a_{1}\). Then \(A[a_{0}]\subset A[a_{1}]\), meaning \(A[a_{0}]\) is an initial segment of \(A[a_{1}]\), so they are not isomorphic, a contradiction.
2. One-to-one-ness and preservation of order are preserved under restriction. We show that the restriction is onto. For every \(a_{0}\in A[a_{1}]\), \(a_{0}\prec_{A}a_{1}\), so \(g(a_{0})\prec_{B}g(a_{1})\). Hence \(g(a_{0})\in B[g(a_{1})]\), and \(g(A[a_{1}])\subseteq B[g(a_{1})]\). Conversely, for every \(b_{0}\in B[g(a_{1})]\), \(b_{0}\prec_{B}g(a_{1})\), so \(g^{-1}(b_{0})\prec_{A}a_{1}\). Hence \(g^{-1}(b_{0})\in A[a_{1}]\), and \(b_{0}\in g(A[a_{1}])\). Therefore \(B[g(a_{1})]\subseteq g(A[a_{1}])\), as required.
3. By the previous claim, \(g^{-1}\bigl|_{B[b_{1}]}\) is an isomorphism between \(B[b_{1}]\) and \(A[g^{-1}(b_{1})]\). Hence, by invertibility, \(g\bigl|_{A[g^{-1}(b_{1})]}\) is an isomorphism between \(A[g^{-1}(b_{1})]\) and \(B[b_{1}]\).

Claim:

Let \(A,B\) be well-ordered sets with \(\preccurlyeq_{A},\preccurlyeq_{B}\), respectively, and denote the strict order relations by \(\prec_{A},\prec_{B}\). Then exactly one of the following claims holds:

1. \(A\) and \(B\) are isomorphic.
2. \(A\) is isomorphic to an initial segment of \(B\).
3. \(B\) is isomorphic to an initial segment of \(A\).

Proof:

Write \[ f:=\left\{(a,b)\in A\times B:A[a]\simeq B[b]\right\} \] and \[ A_{0}:=\{a\in A:\text{ there exists }b\in B\text{ such that }(a,b)\in f\}. \] Notice that \((\min A,\min B)\in f\neq\emptyset\), and therefore \(\emptyset\neq A_{0}\subseteq A\). Let \(a_{1}\in A_{0}\), and let \(\{b_{1},b_{2}\}\subseteq B\) be such that \((a_{1},b_{2})\in f\) and \((a_{1},b_{1})\in f\). Then \(B[b_{2}]\simeq A[a_{1}]\simeq B[b_{1}]\), so \(b_{2}=b_{1}\). Thus \(f:A_{0}\rightarrow B\) is a function, and by symmetry it is also one-to-one.

Let \(g\) be the isomorphism \(A[a_{1}]\simeq B[b_{1}]\). For every \(a_{0}\prec_{A}a_{1}\), \(g\bigl|_{A[a_{0}]}\) is an isomorphism between \(A[a_{0}]\) and \(B[g(a_{0})]\). Thus \(A[a_{0}]\simeq B[g(a_{0})]\), so \(a_{0}\in A_{0}\), and \(A_{0}\) is either all of \(A\) or an initial segment of \(A\). Now write \(b_{0}:=f(a_{0})\). Since \(f\) is one-to-one, \(b_{0}\neq b_{1}\). Assume for contradiction that \(b_{1}\prec_{B}b_{0}\). Then \(A[a_{1}]\simeq B[b_{1}]\subset B[b_{0}]\). For every \(x\in A[a_{1}]\), \(g(x)\in B[b_{1}]\), and in particular \(g(x)\in B[b_{0}]\). Hence \(x\in A[a_{0}]\), so \(A[a_{1}]\subseteq A[a_{0}]\), contradicting \(a_{0}\prec_{A}a_{1}\). Therefore \(f(a_{0})\prec_{B}f(a_{1})\), and \(f\) preserves order. Thus \(f\) is an isomorphism between \(A_{0}\subseteq A\) and \(f(A_{0})\subseteq B\).

For every \(b_{0}'\prec_{B}b_{1}\), \(g\bigl|_{A[g^{-1}(b_{0}')]}\) is an isomorphism between \(A[g^{-1}(b_{0}')]\) and \(B[b_{0}']\). Thus \(A[g^{-1}(b_{0}')]\simeq B[b_{0}']\), and \(b_{0}'\in f(A_{0})\). Hence \(f(A_{0})\) is either all of \(B\) or an initial segment of \(B\).

Assume for contradiction that \(A_{0}\) is an initial segment of \(A\) and \(f(A_{0})\) is an initial segment of \(B\). Then there exist \((a',b')\in A\times B\) such that \(A_{0}=A[a']\) and \(f(A_{0})=B[b']\). Hence \(A[a']\simeq B[b']\), and therefore \(f(a')=b'\), a contradiction. If \(A=A_{0}\) and \(B=f(A_{0})\), then \(A\) and \(B\) are isomorphic. If \(A=A_{0}\) but \(f(A_{0})\) is an initial segment of \(B\), then \(A\) is isomorphic to an initial segment of \(B\). If \(A_{0}\) is an initial segment of \(A\) while \(B=f(A_{0})\), then \(B\) is isomorphic to an initial segment of \(A\).

Canonical Representatives of Well-Ordered Sets

Definition:

Let \(\alpha\) be a set. If \(\alpha\) is transitive and is well-ordered by \(\in_{\alpha}\), then \(\alpha\) is called an ordinal. We denote the class of all ordinals by \(\mathcal{O}\).

Corollaries:

1. For every \(n\in\mathbb{N}\), \(n\) is an ordinal.
2. \(\mathbb{N}\) is an ordinal.
3. If \(\alpha\in\mathcal{O}\) and \(\beta\in\mathcal{O}\), then \(\alpha\cap\beta\in\mathcal{O}\).

Notation:

\(\omega:=\mathbb{N}\).

Claims:

Let \(\alpha\) be an ordinal. Then:

1. \(S(\alpha)\) is an ordinal.
2. For every \(\beta\in\alpha\), \(\beta\) is an ordinal.
3. If \(\beta\) is an ordinal such that \(\beta\subset\alpha\), then \(\beta\in\alpha\).

Proofs:

1. Let \(\beta\in S(\alpha)=\alpha\cup\{\alpha\}\). We split into cases. If \(\beta\in\alpha\), then \(\beta\subset\alpha\), and in particular \(\beta\subset S(\alpha)\). Otherwise \(\beta=\alpha\), and therefore \(\beta\subset S(\alpha)\). Hence \(S(\alpha)\) is transitive. Since \(\alpha\in S(\alpha)\), it is easy to see that \(S(\alpha)\) is well-ordered by \(\in_{S(\alpha)}\).
2. Let \(\beta\in\alpha\). Since \(\beta\subset\alpha\), it follows that \(\beta\) is well-ordered by \(\in_{\alpha}\), and therefore it is well-ordered by \(\in_{\beta}\). If \(\beta=\emptyset\), then \(\beta=0\in\mathbb{N}\), so \(\beta\) is an ordinal. Otherwise, let \(\gamma\in\beta\). Since \(\beta\subset\alpha\), it follows that \(\gamma\in\alpha\), and therefore \(\gamma\subset\alpha\). If \(\gamma=\emptyset\), then \(\gamma\subset\beta\). Otherwise, let \(\delta\in\gamma\). Then \(\delta\in\alpha\). We have \(\{\delta,\gamma,\beta\}\subseteq\alpha\) and \(\delta\in\gamma\in\beta\), so \(\delta\in\beta\). Hence \(\gamma\subset\beta\), and \(\beta\) is an ordinal.
3. Write \(\gamma:=\min(\alpha\setminus\beta)\). Assume for contradiction that there exists \(\delta\in\gamma\setminus\beta\). Then \(\delta\in\gamma\in\alpha\), so \(\delta\in\alpha\setminus\beta\), contradicting the minimality of \(\gamma\). Hence \(\gamma\subseteq\beta\). Let \(\delta\in\beta\). If \(\gamma\in\delta\in\beta\), or \(\gamma=\delta\), then \(\gamma\in\beta\), a contradiction. Otherwise \(\delta\in\gamma\). Therefore \(\beta\subseteq\gamma\), so \(\beta=\gamma\in\alpha\).

Corollary:

Let \(\alpha\neq\emptyset\) be an ordinal. Then \(\emptyset\in\alpha\).

Corollary (Burali-Forti Paradox):

From the axiom of foundation it follows that for every \(X\), \(X\notin X\). Therefore the class of all ordinals \(\mathcal{O}\) is not a set, and also for every \(\alpha\in\mathcal{O}\), \(\alpha\notin\alpha\).

Claims:

Let \(\alpha,\beta,\gamma\) be ordinals. Then:

1. If \(\alpha\in\beta\) and \(\beta\in\gamma\), then \(\alpha\in\gamma\).
2. \(\alpha\in\beta\), or \(\alpha=\beta\), or \(\beta\in\alpha\).

Proofs:

1. Since \(\alpha\in\beta\), \(\alpha\subset\beta\). Since \(\beta\in\gamma\), \(\beta\subset\gamma\). Thus \(\alpha\subset\beta\subset\gamma\), and therefore \(\alpha\subset\gamma\), so \(\alpha\in\gamma\).
2. We split into cases. If \(\alpha=\beta\), we are done. Otherwise \(\emptyset\in\alpha\cap\beta\neq\emptyset\). If \(\beta\subset\alpha\), then \(\beta\in\alpha\), and we are done. If \(\alpha\subset\beta\), then \(\alpha\in\beta\). The set \(\alpha\cap\beta\) is an ordinal. Assume for contradiction that \(\alpha\cap\beta\subset\alpha\) and \(\alpha\cap\beta\subset\beta\). Then \(\alpha\cap\beta\in\alpha\cap\beta\), a contradiction.

Corollary:

Let \(\alpha,\beta\) be ordinals. Then \(\alpha\subseteq\beta\) or \(\beta\subseteq\alpha\).

Notation:

Let \(\alpha,\beta\) be ordinals such that \(\beta\in\alpha\). We also write \(\beta<\alpha\).

Claim:

Let \(\alpha\) be a finite ordinal. Then \(\alpha\in\mathbb{N}\).

Proof:

Assume for contradiction that \(\alpha\notin\mathbb{N}\). Then \(\mathbb{N}\subseteq\alpha\), meaning that \(\alpha\) has an infinite subset, contradicting that it is finite.

Claim (Ordinals Are Representatives of the Well-Ordered Sets):

Let \(A\) be a well-ordered set. Then there exists a unique ordinal \(\alpha\) such that \(A\) is isomorphic to \(\alpha\).

Proof:

Write \[ A_{0}:=\{a\in A:\text{ there exists }\beta\in\mathcal{O}\text{ such that }A[a]\simeq\beta\}. \] By the axiom of replacement there exists a set \[ B:=\{\beta\in\mathcal{O}:a\in A_{0}\text{ and }A[a]\simeq\beta\}. \] Since \(B\) is a family of ordinals, it is well-ordered by \(\in_{B}\). For every \(\beta_{1}\in B\), there exists \(a_{1}\in A_{0}\) such that \(A[a_{1}]\simeq\beta_{1}\). Denote the isomorphism between them by \(g\). Then for every \(\gamma\in\beta_{1}\), \(g\bigl|_{A[g^{-1}(\gamma)]}\) is an isomorphism between \(A[g^{-1}(\gamma)]\) and \(\beta_{1}[\gamma]=\gamma\). Hence \(A[g^{-1}(\gamma)]\simeq\gamma\), so \(\gamma\in B\). Thus \(B\) is also transitive, and therefore it is an ordinal.

For every \(a_{0}\prec_{A}a_{1}\), \(g\bigl|_{A[a_{0}]}\) is an isomorphism between \(A[a_{0}]\) and \(B[g(a_{0})]=g(a_{0})\in\mathcal{O}\). Hence \(a_{0}\in A_{0}\), so \(A_{0}\) is either all of \(A\) or an initial segment of \(A\).

Assume for contradiction that \(\beta_{1}\in g(a_{0})\). Then \(A[a_{1}]\simeq\beta_{1}\subset g(a_{0})\). For every \(x\in A[a_{1}]\), \(g(x)\in\beta_{1}\), and in particular \(g(x)\in g(a_{0})\). Hence \(x\in A[a_{0}]\), so \(A[a_{1}]\subseteq A[a_{0}]\), contradicting \(a_{0}\prec_{A}a_{1}\). The function \[ f:=\{(a,\beta)\in A_{0}\times B:A[a]\simeq\beta\} \] preserves order and is an isomorphism between \(A_{0}\) and \(B\).

Assume for contradiction that \(A_{0}\) is an initial segment of \(A\), and that there exists \(a'\in A\) such that \(A_{0}=A[a']\). Then \(A[a']\simeq B\in\mathcal{O}\), so \(a'\in A_{0}\), a contradiction. Hence \(A=A_{0}\), and \(A\simeq B\). Uniqueness follows from the fact that two isomorphic ordinals must be equal.

Definition:

Let \(A\) be a well-ordered set with \(\preccurlyeq\), and let \(\alpha\in\mathcal{O}\) be the unique ordinal isomorphic to \(A\). We denote \(\operatorname{Otp}(A,\preccurlyeq)=\alpha\).

Claim:

There exists \(\alpha\in\mathcal{O}\) such that \(|\omega|<|\alpha|\).

Proof:

By the axiom of replacement there exists a set \[ Y:=\{\alpha\in\mathcal{O}:\preccurlyeq\in P(\omega\times\omega)\text{ is a well-ordering and }\operatorname{Otp}(\omega,\preccurlyeq)=\alpha\}. \] Assume for contradiction that for every \(\alpha\in\mathcal{O}\) satisfying \(\omega\le\alpha\), we have \(|\omega|=|\alpha|\). Then there exists a one-to-one and onto function \(f:\omega\rightarrow\alpha\). From the one-to-one-ness and onto-ness of \(f\), and from the well-order on \(\alpha\), we get that \[ \{(n,m)\in\omega\times\omega:f(n)\le f(m)\} \] is a well-ordering on \(\omega\), and therefore \(\alpha\in Y\). By the axiom of union, \(Y\cup\omega\) is a set, but \(Y\cup\omega=\mathcal{O}\), a contradiction.