Set theory - Chapter 2: Ordinal Numbers

1. (1)

   $\mathrm{Id}_{P}$ is an isomorphism

2. (2)

   If $f:P\rightarrow Q$ is an isomorphism then so is $f^{{-1}}:Q\rightarrow P$.

3. (3)

   If $f:P\rightarrow Q$ and $g:Q\rightarrow R$ are isomorphisms then so is $g\circ f:P\rightarrow R$.

Suppose there is $\beta<\alpha$ such that $\alpha\leq\beta+1$. For all $x\in\beta+1$, either $x<\beta<\alpha$ or $x=\beta<\alpha$. Hence $\beta+1\subseteq\alpha$ and $\beta+1\leq\alpha$. Hence $\alpha=\beta+1$ would be a successor ordinal.

Conversely, if $\alpha$ is a successor ordinal, let $\beta$ such that $\alpha=\beta+1$. Clearly, $\beta+1<\alpha$ is not satisfied.

Let $X$ be inductive. Then $X\cap\mathrm{Ord}$ is a set (since it is included in $X$) and is inductive:

1. (1)

   $\emptyset\in X$ and $\emptyset\in\mathrm{Ord}$ implies $\emptyset\in X\cap\mathrm{Ord}$

2. (2)

   If $y\in X\cap\mathrm{Ord}$ then $y+1=y\cup\{y\}$ also belongs to $X\cap\mathrm{Ord}$.

By exercise 1.3 $\mathbb{N}$ is transitive and by exercise 1.7, $(\mathbb{N},\in)$ is well-founded. Moreover by lemma 2.11 (and because $\mathbb{N}\subseteq X\cap\mathrm{Ord}\subseteq\mathrm{Ord}$) $(\mathbb{N},\in)$ is a linear ordering. Hence $\mathbb{N}$ is a transitive set well-ordered by $\in$ i.e. an ordinal number. $\emptyset\in\mathbb{N}$ so $\mathbb{N}\neq 0$. If $n<\mathbb{N}$ is a nonzero ordinal then by exercise 1.8 $\exists m\in\mathbb{N},n=m+1$ i.e. $n$ is a successor ordinal. By exercise 2.2, $\mathbb{N}$ is limit. Finally $\mathbb{N}$ is the least non-zero limit ordinal.

(Without the Axiom of Infinity)

(i) implies (ii): if there is an inductive set, then we can construct the intersection of all inductive sets. It is $T$-infinite (exercise 1.11) so it is infinite.

(ii) implies (iii): suppose there exists an infinite set $X$ and that $\mathbb{N}=\omega=\mathrm{Ord}$ i.e. all nonzero ordinals are successor. Let $Y$ be set of all finite subsets of $X$. For all $y\in Y$ there is a 1-1 mapping from $y$ onto some (unique) $F(y)\in\mathbb{N}$. By replacement, $F(Y)$ is a set. $\emptyset\in Y$ and $F(\emptyset)=0$. Hence $F(Y)$ is nonempty and $0\in F(Y)$. If $n\in F(Y)$ then there is $y\in Y$ such that $F(y)=n$. Let $e\in X\setminus y$ (such an element exists since $X$ is infinite an $y$ is finite). Clearly $y\cup\{e\}\in Y$ and $F(y\cup\{e\})=n+1$. Hence by induction, $F(Y)=\mathbb{N}=\omega$. Then $\bigcup F(Y)=\bigcup_{{n\in\mathbb{N}}}n=F(Y)$ is an ordinal. So $F(Y)\in\mathrm{Ord}=F(Y)$. A contradiction.

(iii) implies (i): If $\omega$ is a set, then $0<\omega$ since $\omega$ is nonzero and for all $x<\omega$, $x+1<\omega$ since $\omega$ is a limit ordinal. Hence $\omega$ is inductive.

The set $X=\{a_{n}:n\in\mathbb{N}\}$ is a nonempty subset of $W$. Let $x=\min X$ and $n$ such that $a_{n}=x$. Then $a_{{n+1}}<a_{n}=x$, a contradiction.

Let $\alpha_{0}\in\mathrm{Ord}$ and define $\alpha_{{n+1}}=\alpha_{n}+1$ and $\beta=\lim_{{n\rightarrow\omega}}a_{n}$. If $\gamma<\beta$, there is $\alpha_{n}$ such that $\gamma<\alpha_{n}$. Thus $\gamma+1<\alpha_{n}+1=\alpha_{{n+1}}\leq\beta$. Hence $\beta$ is limit.

Let $\left\langle\gamma_{\alpha}:\alpha\in\mathrm{Ord}\right\rangle$ be normal. Let $\alpha_{0}=\beta$, $\alpha_{{n+1}}=\gamma_{{\alpha_{n}}}$ and $\alpha=\lim_{{n\rightarrow\omega}}\alpha_{{n+1}}=\lim_{{n\rightarrow\omega}}\gamma_{{\alpha_{n}}}=\gamma_{{\lim_{{n\rightarrow\omega}}\alpha_{n}}}=\gamma_{\alpha}$ (because $\alpha\mapsto\gamma_{\alpha}$ is continuous). Since $\alpha\mapsto\gamma_{\alpha}$ is increasing, $\alpha_{{n+1}}=\gamma_{{\alpha_{n}}}\geq\alpha_{n}$ by Lemma 2.4. Hence $\beta\leq\alpha_{0}\leq\alpha_{1}\leq...\alpha_{n}\leq...\leq\alpha$.

By induction on $\gamma$.

1. ((i))
   1. (a)

      $\alpha(\beta+0)=\alpha\beta=\alpha\beta+\alpha 0$

   2. (b)

      $\alpha(\beta+(\gamma+1))=\alpha((\beta+\gamma)+1)=\alpha(\beta+\gamma)+\alpha=\alpha\beta+\alpha\gamma+\alpha=\alpha\beta+\alpha(\gamma+1)$

   3. (c)

      For all $\gamma>0$ limit, $\alpha(\beta+\gamma)=\alpha(\beta+\lim_{{\xi\rightarrow\gamma}}\xi)=\alpha\lim_{{\xi\rightarrow\gamma}}(\beta+\xi)=\lim_{{\xi\rightarrow\gamma}}\alpha(\beta+\xi)=\lim_{{\xi\rightarrow\gamma}}(\alpha\beta+\alpha\xi)=\alpha\beta+\lim_{{\xi\rightarrow\gamma}}\alpha\xi=\alpha\beta+\alpha\lim_{{\xi\rightarrow\gamma}}\xi=\alpha\beta+\alpha\gamma$

2. ((ii))
   1. (a)

      $\alpha^{{\beta+0}}=\alpha^{\beta}=\alpha^{\beta}\alpha^{0}$

   2. (b)

      $\alpha^{{\beta+\gamma+1}}=\alpha^{{\beta+\gamma}}\alpha=\alpha^{\beta}\alpha^{\gamma}\alpha=\alpha\alpha^{{\gamma+1}}$

   3. (c)

      For all $\gamma>0$ limit, $\alpha^{{(\beta+\gamma)}}=\alpha^{{(\beta+\lim_{{\xi\rightarrow\gamma}}\xi)}}=\alpha^{{\lim_{{\xi\rightarrow\gamma}}(\beta+\xi)}}=\lim_{{\xi\rightarrow\gamma}}\alpha^{{\beta+\xi}}=\lim_{{\xi\rightarrow\gamma}}\alpha^{{\beta}}+\alpha^{{\xi}}=\alpha^{\beta}+\lim_{{\xi\rightarrow\gamma}}\alpha^{{\xi}}=\alpha^{\beta}+\alpha^{{\lim_{{\xi\rightarrow\gamma}}\xi}}=\alpha^{\beta}+\alpha^{\gamma}$

3. ((iii))
   1. (a)

      ${(\alpha^{\beta})}^{0}=1=\alpha^{{\beta 0}}$

   2. (b)

      ${(\alpha^{\beta})}^{{\gamma+1}}={(\alpha^{\beta})}^{{\gamma}}\alpha^{\beta}=\alpha^{{\beta\gamma+\beta}}=\alpha^{{\beta(\gamma+1)}}$

   3. (c)

      For all $\gamma>0$ limit, ${(\alpha^{\beta})}^{{\gamma}}={(\alpha^{\beta})}^{{\lim_{{\xi\rightarrow\gamma}}\xi}}=\lim_{{\xi\rightarrow\gamma}}{(\alpha^{\beta})}^{{\xi}}=\lim_{{\xi\rightarrow\gamma}}\alpha^{{\beta\xi}}=\alpha^{{\lim_{{\xi\rightarrow\gamma}}\beta\xi}}=\alpha^{{\beta\lim_{{\xi\rightarrow\gamma}}\xi}}=\alpha^{{\beta\gamma}}$

1. ((i))

   $(\omega+1)2=\omega+1+\omega+1=\omega+\omega+1=\omega 2+1<\omega 2+2=\omega 2+1.2$

2. ((ii))

   ${(\omega 2)}^{2}=(\omega 2)(\omega 2)=(\omega 2)(\omega+\omega)=(\omega 2)\omega+(\omega 2)\omega=(\omega 2\omega)2=(\lim_{{n\rightarrow\omega}}(\omega 2n))2=\omega^{2}2<\omega^{2}4=\omega^{2}2^{2}$

Let $\alpha<\beta$. We shall show by induction on $\gamma$ than $\alpha+\gamma\leq\beta+\gamma$, $\alpha\gamma\leq\alpha\gamma$ and $\alpha^{\gamma}\leq\beta^{\gamma}$.

1. ((i))
   1. (a)

      $\alpha+0=\alpha\leq\beta=\beta+0$

   2. (b)

      $\alpha+\gamma\leq\beta+\gamma<(\beta+\gamma)+1$ so $\alpha+(\gamma+1)=(\alpha+\gamma)+1\leq(\beta+\gamma)+1=\beta+(\gamma+1)$

   3. (c)

      Let $\gamma>0$ be limit. For all $\xi<\gamma$ we have $\alpha+\xi<\beta+\gamma$. Thus $\alpha+\gamma=\lim_{{\xi\rightarrow\gamma}}(\alpha+\xi)=\beta+\gamma$

2. ((ii))
   1. (a)

      $\alpha 0=0\leq 0=\beta 0$

   2. (b)

      $\alpha\gamma\leq\beta\gamma$ and $\alpha\leq\beta$ so $\alpha\gamma+\alpha\leq\alpha\gamma+\beta\leq\beta\gamma+\beta$ (use 2.10-i for the last inequality). Hence $\alpha(\gamma+1)\leq\beta(\gamma+1)$.

   3. (c)

      Same as 2.10-i

3. ((iii))
   1. (a)

      $\alpha^{0}=1\leq 1=\beta^{0}$

   2. (b)

      $\alpha^{{\gamma+1}}=\alpha^{\gamma}\alpha\leq\alpha^{\gamma}\beta\leq\beta^{\gamma}\beta=\beta^{{\gamma+1}}$ (use 2.10-ii for the last inequality).

   3. (c)

      Same as 2.10-i

1. ((i))

   $0+\omega=\omega=1+\omega$ and $0<1$

2. ((ii))

   $1\omega=\omega=2\omega$ and $1<2$

3. ((iii))

   $2^{\omega}=\omega=3^{\omega}$ and $2<3$

Define $\alpha_{0}=\omega$ and $\alpha_{{n+1}}=\omega^{{\alpha_{n}}}$ for all $n<\omega$. If $\epsilon_{0}=\lim_{{n\rightarrow\omega}}\alpha_{n}$, then by continuity of $\xi\mapsto\omega^{\xi}$, $\omega^{{\epsilon_{0}}}=\epsilon_{0}$. We shall show that $\epsilon_{0}$ is the least ordinal that satisfies this property. Suppose $\epsilon<\epsilon_{0}$ satisfies $\omega^{\epsilon}=\epsilon$. Clearly, $\epsilon\geq\omega$. Hence the least $n$ such that $\alpha_{n}\geq\epsilon$ satisfies $n>0$. If we let $m=n-1$ then $\alpha_{m}\leq\epsilon$ and $\alpha_{n}=\omega^{{\alpha_{m}}}\leq\omega^{\epsilon}=\epsilon$. A contradiction.

Let $\gamma>0$ be a limit ordinal and consider the following properties:

1. ((i))

   $\gamma$ is indecomposable i.e there is no $\alpha,\beta<\gamma$ such that $\gamma=\alpha+\beta$.

2. ((ii))

   For all $\alpha<\gamma$, $\alpha+\gamma=\gamma$

3. ((iii))

   $\gamma=\omega^{\alpha}$ for some $\alpha$

(ii) implies (i). For all $\alpha<\gamma$ there exists (an unique) $\delta$ such that $\alpha+\delta=\gamma$. Since $\gamma$ is indecomposable, $\delta\geq\gamma$. $\gamma=\alpha+\delta\geq\alpha+\gamma$. $0\leq\alpha$ so by (2.10) $\gamma\leq\alpha+\gamma$. Hence $\alpha+\gamma=\gamma$.

(i) implies (iii). Let $\gamma$ be indecomposable and $\gamma=\omega^{{\beta_{1}}}k_{1}+...+\omega^{{\beta_{n}}}k_{n}$ be its Cantor’s normal form ($\gamma\geq\beta_{1}>\beta_{2}...>\beta_{n}$ and $0<k_{i}<\omega$). If $n\geq 2$ or $k_{1}\geq 2$ then $\gamma=\omega^{{\beta_{1}}}+(\omega^{{\beta_{1}}}(k_{1}-1)+...+\omega^{{\beta_{n}}}k_{n})=\alpha+\beta$ is a decomposition of $\gamma$. Clearly $\alpha=\omega^{{\beta_{1}}}<\gamma$. Moreover $\alpha+\beta=\gamma\leq\alpha+\gamma$ so $\beta\leq\gamma$. The inequality is strict for otherwise the Cantor’s normal form of $\gamma$ would not be unique. Hence $n=k_{1}=1$ and $\gamma=\omega^{{\beta_{1}}}$.

(iii) implies (ii). First we shall prove by induction on $\epsilon>0$ that for all $k<\omega$, $k+\omega^{\epsilon}=\omega^{\epsilon}$. It is clear for $\epsilon=1$. If it is the case for $\epsilon$ then $k+\omega^{{\epsilon+1}}=\lim_{{n\rightarrow\omega}}k+\omega^{\epsilon}n=\lim_{{n\rightarrow\omega}}\omega^{\epsilon}n=\omega^{{\epsilon+1}}$. Finally for a limit ordinal $\epsilon$ such that the property is verified for all the $\xi<\epsilon$, $k+\omega^{\epsilon}=\lim_{{\xi\rightarrow\epsilon}}k+\omega^{\xi}=\lim_{{\xi\rightarrow\epsilon}}\omega^{\xi}=\omega^{\epsilon}$. Now let $\beta<\gamma$ and consider its Cantor’s normal form $\beta=\omega^{{\beta_{1}}}k_{1}+...+\omega^{{\beta_{n}}}k_{n}$ ($\beta\leq\beta_{1}>...>\beta_{n}$ and $0<k_{i}<\omega$). We have $\omega^{\alpha}=\gamma>\beta$ and for all $\delta\leq\beta_{1}$, $\omega^{\delta}\leq\omega^{{\beta_{1}}}<\beta$. Hence $\alpha>\beta_{1}>...>\beta_{n}$. $\beta+\gamma=\beta+\omega^{\alpha}=\omega^{{\beta_{1}}}k_{1}+...+\omega^{{\beta_{{n-1}}}}k_{{n-1}}+\omega^{{\beta_{n}}}(k_{n}+\omega^{\epsilon})$ where $\epsilon>0$ satisfies $\epsilon+\beta_{n}=\alpha$. But we showed that $k_{n}+\omega^{\epsilon}=\omega^{\epsilon}$ so $\beta+\gamma=\omega^{{\beta_{1}}}k_{1}+...+\omega^{{\beta_{{n-1}}}}k_{{n-1}}+\omega^{\alpha}$. If we repeat this several times, we get $\beta+\gamma=\omega^{\alpha}=\gamma$.

The set $X=\{a_{n}:n\in\mathbb{N}\}$ is a nonempty subset of $W$. Let $x$ be a minimal element of $X$ (for the well-founded relation $E$) and $n$ such that $a_{n}=x$. Then $a_{{n+1}}Ea_{n}=x$, a contradiction.

This is Theorem 6.11.