• Quick access
  • Homepage (fr)
  • International
  • François's Blog
  • Frédéric's Blog
  • Maths (fr)
  • Computer Science (fr)
  • Programming (fr)
  • Our games (fr)
  • Video games (fr)
• Special pages
  • Log in (fr)
  • Forum
  • Authors (fr)
  • Site Map (fr)
• Parent directories
  • International
  • Set Theory
  • Set theory - Chapter 2: Ordinal Numbers
• Current directory
  • Set theory - Chapter 1: Axioms of Set theory
  • Set theory - Chapter 2: Ordinal Numbers
  • Set theory - Chapter 3: Cardinal Numbers
  • Set theory - Chapter 6: The Axiom of Regularity
  • Set theory - Chapter 14: Forcing

Set theory - Chapter 2: Ordinal Numbers

2.1

• ${\mathrm{Id}}_P$ is an isomorphism
• If $f:P\to Q$ is an isomorphism then so is $f^{-1}:Q\to P$
• If $f:P\to Q$ and $g:Q\to R$ are isomorphisms then so is $g\circ f:P\to R$

2.2

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

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

2.3

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

• $\varnothing \in X$ and $\varnothing \in \mathrm{Ord}$ implies $\varnothing \in X\cap \mathrm{Ord}$
• If $y\in X\cap \mathrm{Ord}$then $y+1=y\cup \left\{y\right\}$ also belongs to $X\cap \mathrm{Ord}$.

By (1.3) $\mathbb{N}$ is transitive and by (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 ∈ i.e. an ordinal number. $\varnothing \in \mathbb{N}$ so $\mathbb{N}\ne 0$. If $n<\mathbb{N}$ is a non-zero ordinal then by (1.8) $\exists m\in \mathbb{N}n=m+1$ i.e. $n$ is a successor ordinal. By (2.2) $\mathbb{N}$ is limit. Finally $\mathbb{N}$ is the least non-zero ordinal.

2.4

(Without the Axiom of Infinity)

(i) ⇒ (ii) If there is an inductive set, then we can construct the intersection of all inductive sets. It is T-infinite (1.11) so it is infinite.

(ii) ⇒ (iii) Suppose there exists an infinite set $X$ and that $\mathbb{N}=\omega =\mathrm{Ord}$ i.e. all ordinals are successor. Let $Y$ be be set of all finite subset of $X$. For all $y\in Y$ there is a 1-1 mapping of y onto some (unique) $F\left(y\right)\in \mathbb{N}$ . By replacement, $F\left(Y\right)$ is a set.$\varnothing \in Y$ and $F\left(\varnothing \right)=0$. Hence $F\left(Y\right)$ is nonempty and $0\in F\left(Y\right)$. If $n\in F\left(Y\right)$then there is $y\in Y$ such that $F\left(y\right)=n$. Let $e\in X\backslash y$(such an element exists since $X$ is infinite an $y$ is finite). Clearly $y\cup \left\{e\right\}\in Y$ and $F\left(y\cup \left\{e\right\}\right)=n+1$. Hence by induction, $F\left(y\right)=\mathbb{N}=\omega$. Then $\bigcup F\left(y\right)=\bigcup _{n\in \mathbb{N}}n=F\left(y\right)$ is an ordinal and $F\left(y\right)\in F\left(y\right)$. A contradiction.

(iii) ⇒ (i) If $\omega$ is a set, then $0<\omega$ since $\omega$ is non-zero and for all $x<\omega$, $x+1<\omega$ since $\omega$ is a limit ordinal. Hence $\omega$ is inductive.

2.5

The set $X=\{a_n,n\in \mathbb{N}\}$ is a non-empty subset of $W$. Let $x=minX$ and $n$ such that $a_n=x$. Then , a contradiction.

2.6

Let $\alpha \in \mathrm{Ord}$ and define ${\alpha }_0=0$, ${\alpha }_{n+1}={\alpha }_n+1$ and $\beta =\underset{n\to \omega }{lim}{\alpha }_n$. If $\text{γ<β}$, there is ${\text{α}}_{\text{n}}$ such that $\text{γ<}{\text{α}}_{\text{n}}$. Thus $\text{γ+1<}{\text{α}}_{\text{n}}\text{+1=}{\text{α}}_{\text{n+1}}\text{≤β}$. Hence β is limit.

2.7

Let $<{\gamma }_{\alpha },\alpha \in \mathrm{Ord}>$ be normal. Let ${\alpha }_0=\beta$, ${\alpha }_{n+1}={\gamma }_{{\alpha }_n}$ and $\alpha =\underset{n\to \omega }{lim}{\alpha }_n$. Then $\alpha =\underset{n\to \omega }{lim}{\alpha }_{n+1}=\underset{n\to \omega }{lim}{\gamma }_{{\alpha }_n}={\gamma }_{\underset{n\to \omega }{lim}{\alpha }_n}={\gamma }_{\alpha }$ (because $\alpha \mapsto {\gamma }_{\alpha }$ is continuous). Since $\alpha \mapsto {\gamma }_{\alpha }$ is increasing, ${\alpha }_{n+1}={\gamma }_{{\alpha }_n}\ge {\alpha }_n$ by Lemma 2.4. Hence $\beta ={\alpha }_0\le {\alpha }_1\le ...\le {\alpha }_n\le ...\le \alpha$.

2.8

By induction on $\gamma$.

1. • $\alpha \left(\beta +0\right)=\alpha \beta =\alpha \beta +\alpha 0$
   • $\alpha \left(\beta +\left(\gamma +1\right)\right)=\alpha (\left(\beta +\gamma \right)+1)=\alpha \left(\beta +\gamma \right)+\alpha =\alpha \beta +\alpha \gamma +\alpha =\alpha \beta +\alpha \left(\gamma +1\right)$
   • For all $\gamma >0$ limit, $\alpha \left(\beta +\gamma \right)=\alpha \left(\beta +\underset{\zeta \to \gamma }{lim}\zeta \right)=\alpha \underset{\zeta \to \gamma }{lim}\left(\beta +\zeta \right)=\underset{\zeta \to \gamma }{lim}\alpha \left(\beta +\zeta \right)=\underset{\zeta \to \gamma }{lim}\alpha \beta +\mathrm{\alpha \zeta }=\alpha \beta +\underset{\zeta \to \gamma }{lim}\mathrm{\alpha \zeta }=\alpha \beta +\alpha \underset{\zeta \to \gamma }{lim}\zeta =\alpha \beta +\alpha \gamma$
2. • ${\alpha }^{\beta +0}={\alpha }^{\beta }={\alpha }^{\beta }{\alpha }^0$
   • ${\alpha }^{\beta +\left(\gamma +1\right)}={\alpha }^{\beta +\gamma }\alpha ={\alpha }^{\beta }{\alpha }^{\gamma }\alpha ={\alpha }^{\beta }{\alpha }^{\gamma +1}$
   • For all $\gamma >0$ limit, ${\alpha }^{\left(\beta +\gamma \right)}={\alpha }^{\left(\beta +\underset{\zeta \to \gamma }{lim}\zeta \right)}={\alpha }^{\underset{\zeta \to \gamma }{lim}\left(\beta +\zeta \right)}=\underset{\zeta \to \gamma }{lim}{\alpha }^{\left(\beta +\zeta \right)}=\underset{\zeta \to \gamma }{lim}{\alpha }^{\beta }+{\alpha }^{\zeta }={\alpha }^{\beta }+\underset{\zeta \to \gamma }{lim}{\alpha }^{\zeta }={\alpha }^{\beta }+{\alpha }^{\underset{\zeta \to \gamma }{lim}\zeta }={\alpha }^{\beta }+{\alpha }^{\gamma }$
3. • ${\left({\alpha }^{\beta }\right)}^0=1={\alpha }^{\beta 0}$
   • ${\left({\alpha }^{\beta }\right)}^{\gamma +1}={\left({\alpha }^{\beta }\right)}^{\gamma }{\alpha }^{\beta }={\alpha }^{\beta \gamma }{\alpha }^{\beta }={\alpha }^{\beta \gamma +\beta }={\alpha }^{\beta \left(\gamma +1\right)}$
   • For all $\gamma >0$ limit, ${\left({\alpha }^{\beta }\right)}^{\gamma }={\left({\alpha }^{\beta }\right)}^{\underset{\zeta \to \gamma }{lim}\zeta }=\underset{\zeta \to \gamma }{lim}{\left({\alpha }^{\beta }\right)}^{\zeta }=\underset{\zeta \to \gamma }{lim}{\alpha }^{\beta \zeta }={\alpha }^{\underset{\zeta \to \gamma }{lim}\beta \zeta }={\alpha }^{\beta \underset{\zeta \to \gamma }{lim}\zeta }={\alpha }^{\beta \zeta }$

2.9

1. $\left(\omega +1\right)2=\omega +1+\omega +1=\omega +\omega +1=\omega 2+1<\omega 2+2=\omega 2+1.2$
2. ${\left(\omega 2\right)}^2=\left(\omega 2\right)\left(\omega 2\right)=\left(\omega 2\right)\left(\omega +\omega \right)=\left(\omega 2\omega \right)2=\left(\underset{n\to \omega }{lim}\omega 2n\right)2={\omega }^{2}2<{\omega }^{2}4={\omega }^2{2}^2$

2.10

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

1. • $\alpha +0=\alpha \le \beta =\beta +0$
   • $\alpha +\gamma \le \beta +\gamma <\left(\beta +\gamma \right)+1$ so $\alpha +\left(\gamma +1\right)=\left(\alpha +\gamma \right)+1\le \left(\beta +\gamma \right)+1=\beta +\left(\gamma +1\right)$
   • Let $\gamma >0$ be limit. For all $\zeta <\gamma$ $(\alpha +\zeta \le \beta +\zeta <\beta +\gamma )$. Thus $\alpha +\gamma =\underset{\zeta \to \gamma }{lim}\alpha +\zeta \le \beta +\gamma$
2. • $\alpha 0=0\le 0=\beta 0$
   • $\mathrm{\alpha \gamma }\le \mathrm{\beta \gamma }$ and $\alpha \le \beta$ so $\alpha \gamma +\alpha \le \mathrm{\alpha \gamma }+\beta \le \beta \gamma +\beta$ (use 2.10-i for the last inequality). Hence $\alpha \left(\gamma +1\right)\le \beta (\gamma +1)$.
   • Same as 2.10-i
3. • ${\alpha }^0=1\le 1={\beta }^0$
   • ${\alpha }^{\gamma +1}={\alpha }^{\gamma }\alpha \le {\alpha }^{\gamma }\beta \le {\beta }^{\gamma }\beta ={\beta }^{\gamma +1}$ (use 2.10-ii for the last inequality).
   • Same as 2.10-i

2.11

1. $0+\omega =\omega =1+\omega$ and $0<1$
2. $1\omega =\omega =2\omega$ and $1<2$
3. $2^{\omega }=\omega =3^{\omega }$ and $2<3$

2.12

Define ${\alpha }_0=\omega$ and ${\alpha }_{n+1}={\omega }^{{\alpha }_n}$ for all $n<\omega$. If ${\epsilon }_0=\underset{n\to \omega }{lim}{\alpha }_n$, then by continuity of $\zeta \mapsto {\omega }^{\zeta }$ ${\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 \ge \omega$. Hence the least $n$ such that ${\alpha }_n>\epsilon$ satisfies $n>0$. If we let $m=n-1$ then ${\alpha }_m\le \epsilon$ and ${{\alpha }_n=\omega }^{{\alpha }_m}\le {\omega }^{\epsilon }=\epsilon$. A contradiction.

2.13

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

1. $\gamma$ is indecomposable i.e there is no $\alpha ,\beta <\gamma$ such that $\gamma =\alpha +\beta$
2. For all $\alpha <\gamma$ $\alpha +\gamma =\gamma$
3. $\gamma ={\omega }^{\alpha }$ for some $\alpha$

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

(i) ⇒ (iii) Let $\gamma$ be indecomposable and $\gamma ={\omega }^{{\beta }_1}{k}_1+...{\omega }^{{\beta }_n}{k}_n$ be its Cantor's normal form ($\gamma \ge {\beta }_1>...>{\beta }_n$and $0<k_i<\omega$). If $n\ge 2$ or $k_1\ge 2$ then $\gamma ={\omega }^{{\beta }_1}+\left({\omega }^{{\beta }_1}(k_1-1)+...+{\omega }^{{\beta }_n}{k}_n\right)=\alpha +\beta$ is a decomposition of $\gamma$. Clearly ${\alpha =\omega }^{{\beta }_1}<\gamma$. Moreover $\alpha +\beta =\gamma \le \alpha +\gamma$ so $\beta \le \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) ⇒ (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}=\underset{n\to \omega }{lim}1+{\omega }^{\epsilon }n=\underset{n\to \omega }{lim}{\omega }^{\epsilon }n={\omega }^{\epsilon +1}$. Finally for a limit ordinal $\epsilon$ such that the property is verified for all the $\zeta <\epsilon$,$k+{\omega }^{\epsilon }=\underset{\zeta \to \epsilon }{lim}k+{\omega }^{\zeta }=\underset{\zeta \to \epsilon }{lim}{\omega }^{\zeta }={\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 \ge {\beta }_1>...>{\beta }_n$and $0<k_i<\omega$). We have ${\omega }^{\alpha }=\gamma >\beta$ and for all $\delta \le {\beta }_1$, ${\omega }^{\delta }\le {\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$.

2.14

The set $X=\{a_n,n\in \mathbb{N}\}$ is a non-empty 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 contradiction.

2.15

See Theorem 2.15

This page is W3C-compliant - Author: Frédéric WANG