Set theory - Chapter 2: Ordinal Numbers

2.1

  1. (1)

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

  2. (2)

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

  3. (3)

    If f:PQf:P\rightarrow Q and g:QRg:Q\rightarrow R are isomorphisms then so is gf:PRg\circ f:P\rightarrow R.

2.2

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

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

2.3

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

  1. (1)

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

  2. (2)

    If yXOrdy\in X\cap\mathrm{Ord} then y+1=y{y}y+1=y\cup\{y\} also belongs to XOrdX\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 XOrdOrd\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 0\mathbb{N}\neq 0. If n<n<\mathbb{N} is a nonzero ordinal then by exercise 1.8 m,n=m+1\exists m\in\mathbb{N},n=m+1 i.e. nn is a successor ordinal. By exercise 2.2, \mathbb{N} is limit. Finally \mathbb{N} is the least non-zero limit ordinal.

2.4

(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 TT-infinite (exercise 1.11) so it is infinite.

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

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

2.5

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

2.6

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

2.7

Let γα:αOrd\left\langle\gamma_{\alpha}:\alpha\in\mathrm{Ord}\right\rangle be normal. Let α0=β\alpha_{0}=\beta, αn+1=γαn\alpha_{{n+1}}=\gamma_{{\alpha_{n}}} and α=limnωαn+1=limnωγαn=γlimnωαn=γα\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, αn+1=γαnαn\alpha_{{n+1}}=\gamma_{{\alpha_{n}}}\geq\alpha_{n} by Lemma 2.4. Hence βα0α1αnα\beta\leq\alpha_{0}\leq\alpha_{1}\leq...\alpha_{n}\leq...\leq\alpha.

2.8

By induction on γ\gamma.

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

      α(β+0)=αβ=αβ+α0\alpha(\beta+0)=\alpha\beta=\alpha\beta+\alpha 0

    2. (b)

      α(β+(γ+1))=α((β+γ)+1)=α(β+γ)+α=αβ+αγ+α=αβ+α(γ+1)\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 γ>0\gamma>0 limit, α(β+γ)=α(β+limξγξ)=αlimξγ(β+ξ)=limξγα(β+ξ)=limξγ(αβ+αξ)=αβ+limξγαξ=αβ+αlimξγξ=αβ+αγ\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)

      αβ+0=αβ=αβα0\alpha^{{\beta+0}}=\alpha^{\beta}=\alpha^{\beta}\alpha^{0}

    2. (b)

      αβ+γ+1=αβ+γα=αβαγα=ααγ+1\alpha^{{\beta+\gamma+1}}=\alpha^{{\beta+\gamma}}\alpha=\alpha^{\beta}\alpha^{% \gamma}\alpha=\alpha\alpha^{{\gamma+1}}

    3. (c)

      For all γ>0\gamma>0 limit, α(β+γ)=α(β+limξγξ)=αlimξγ(β+ξ)=limξγαβ+ξ=limξγαβ+αξ=αβ+limξγαξ=αβ+αlimξγξ=αβ+αγ\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)

      (αβ)0=1=αβ0{(\alpha^{\beta})}^{0}=1=\alpha^{{\beta 0}}

    2. (b)

      (αβ)γ+1=(αβ)γαβ=αβγ+β=αβ(γ+1){(\alpha^{\beta})}^{{\gamma+1}}={(\alpha^{\beta})}^{{\gamma}}\alpha^{\beta}=% \alpha^{{\beta\gamma+\beta}}=\alpha^{{\beta(\gamma+1)}}

    3. (c)

      For all γ>0\gamma>0 limit, (αβ)γ=(αβ)limξγξ=limξγ(αβ)ξ=limξγαβξ=αlimξγβξ=αβlimξγξ=αβγ{(\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}}

2.9

  1. ((i))

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

  2. ((ii))

    (ω2)2=(ω2)(ω2)=(ω2)(ω+ω)=(ω2)ω+(ω2)ω=(ω2ω)2=(limnω(ω2n))2=ω22<ω24=ω222{(\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 2% n))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\leq\beta+\gamma, αγαγ\alpha\gamma\leq\alpha\gamma and αγβγ\alpha^{\gamma}\leq\beta^{\gamma}.

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

      α+0=αβ=β+0\alpha+0=\alpha\leq\beta=\beta+0

    2. (b)

      α+γβ+γ<(β+γ)+1\alpha+\gamma\leq\beta+\gamma<(\beta+\gamma)+1 so α+(γ+1)=(α+γ)+1(β+γ)+1=β+(γ+1)\alpha+(\gamma+1)=(\alpha+\gamma)+1\leq(\beta+\gamma)+1=\beta+(\gamma+1)

    3. (c)

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

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

      α0=00=β0\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 α(γ+1)β(γ+1)\alpha(\gamma+1)\leq\beta(\gamma+1).

    3. (c)

      Same as 2.10-i

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

      α0=11=β0\alpha^{0}=1\leq 1=\beta^{0}

    2. (b)

      αγ+1=αγααγββγβ=βγ+1\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

2.11

  1. ((i))

    0+ω=ω=1+ω0+\omega=\omega=1+\omega and 0<10<1

  2. ((ii))

    1ω=ω=2ω1\omega=\omega=2\omega and 1<21<2

  3. ((iii))

    2ω=ω=3ω2^{\omega}=\omega=3^{\omega} and 2<32<3

2.12

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

2.13

Let γ>0\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α0\leq\alpha so by (2.10) γα+γ\gamma\leq\alpha+\gamma. Hence α+γ=γ\alpha+\gamma=\gamma.

(i) implies (iii). Let γ\gamma be indecomposable and γ=ωβ1k1++ωβnkn\gamma=\omega^{{\beta_{1}}}k_{1}+...+\omega^{{\beta_{n}}}k_{n} be its Cantor’s normal form (γβ1>β2>βn\gamma\geq\beta_{1}>\beta_{2}...>\beta_{n} and 0<ki<ω0<k_{i}<\omega). If n2n\geq 2 or k12k_{1}\geq 2 then γ=ωβ1+(ωβ1(k1-1)++ωβnkn)=α+β\gamma=\omega^{{\beta_{1}}}+(\omega^{{\beta_{1}}}(k_{1}-1)+...+\omega^{{\beta_% {n}}}k_{n})=\alpha+\beta is a decomposition of γ\gamma. Clearly α=ωβ1<γ\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=k1=1n=k_{1}=1 and γ=ωβ1\gamma=\omega^{{\beta_{1}}}.

(iii) implies (ii). First we shall prove by induction on ϵ>0\epsilon>0 that for all k<ωk<\omega, k+ωϵ=ωϵk+\omega^{\epsilon}=\omega^{\epsilon}. It is clear for ϵ=1\epsilon=1. If it is the case for ϵ\epsilon then k+ωϵ+1=limnωk+ωϵn=limnωωϵn=ωϵ+1k+\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+ωϵ=limξϵk+ωξ=limξϵωξ=ωϵ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 β=ωβ1k1++ωβnkn\beta=\omega^{{\beta_{1}}}k_{1}+...+\omega^{{\beta_{n}}}k_{n} (ββ1>>βn\beta\leq\beta_{1}>...>\beta_{n} and 0<ki<ω0<k_{i}<\omega). We have ωα=γ>β\omega^{\alpha}=\gamma>\beta and for all δβ1\delta\leq\beta_{1}, ωδωβ1<β\omega^{\delta}\leq\omega^{{\beta_{1}}}<\beta. Hence α>β1>>βn\alpha>\beta_{1}>...>\beta_{n}. β+γ=β+ωα=ωβ1k1++ωβn-1kn-1+ωβn(kn+ωϵ)\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 ϵ>0\epsilon>0 satisfies ϵ+βn=α\epsilon+\beta_{n}=\alpha. But we showed that kn+ωϵ=ωϵk_{n}+\omega^{\epsilon}=\omega^{\epsilon} so β+γ=ωβ1k1++ωβn-1kn-1+ωα\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={an:n}X=\{a_{n}:n\in\mathbb{N}\} is a nonempty subset of WW. Let xx be a minimal element of XX (for the well-founded relation EE) and nn such that an=xa_{n}=x. Then an+1Ean=xa_{{n+1}}Ea_{n}=x, a contradiction.

2.15

This is Theorem 6.11.

This page is W3C-compliant - Author: Frédéric WANG
Valid XHTML 1.1 Valid MathML 2.0 Valid SVG Valid CSS