Frédéric Wang    About    Mathematics    Computer Science    Miscellaneous    Archive

The canonical well-ordering of α×α (part 2)

In a my previous blog post, I discussed the canonical well-ordering on α×α\alpha\times\alpha and stated theorem 0.5 below to calculate its order-type γ(α)\gamma(\alpha). Subsequent corollaries provided a bound for γ(α)\gamma(\alpha), its fixed points and a proof that infinite cardinals were among these fixed points (and so that cardinal addition and multiplication is trivial). In this second part, I’m going to provide the proof of this theorem.

First, we note that for all n<ωn<\omega, there is only one order-type for n×nn\times n, since the notion of cardinal and ordinal is the same for finite sets. So indeed

n<ω,γ(n)=|n×n|=n2\forall n<\omega,\gamma(n)={|n\times n|}=n^{2}

and taking the limit, we get our first infinite fixed point:

γ(ω)=supn<ωγ(n)=ω\gamma(\omega)=\sup_{n<\omega}{\gamma(n)}=\omega

For all α\alpha the ordering on (α+1)×(α+1){(\alpha+1)}\times{(\alpha+1)} is as follows: first the elements of α×α\alpha\times\alpha ordered as γ(α)\gamma(\alpha), followed by the elements (ξ,α)(\xi,\alpha) for 0ξ<α0\leq\xi<\alpha, followed by the elements (α,ξ)(\alpha,\xi) for 0ξα0\leq\xi\leq\alpha. Hence

α,γ(α+1)=γ(α)+α2+1\forall\alpha,{\gamma(\alpha+1)}={\gamma(\alpha)}+\alpha\cdot 2+1

From this, we can try to calculate the next values of γ\gamma after ω\omega:

γ(ω+1)=ω+ω2+1=ω3+1{\gamma(\omega+1)}=\omega+{\omega\cdot 2}+1={\omega\cdot 3}+1
γ(ω+2)=ω3+1+ω+1+ω+1+1=ω5+2{\gamma(\omega+2)}={\omega\cdot 3+1}+\omega+1+\omega+1+1={\omega\cdot 5}+2

The important point is 1+ω=ω1+\omega=\omega ; in general we will use several times the property α+ωβ=ωβ\alpha+\omega^{\beta}=\omega^{\beta} if α<ωβ\alpha<\omega^{\beta}. By a simple recurrence (see proposition 0.1), we can generalize the expression to arbitrary nn:

γ(ω+n)=ω(2n+1)+n{\gamma(\omega+n)}=\omega\left(2n+1\right)+n

and so taking the limit

γ(ω2)=ω2{\gamma(\omega\cdot 2)}=\omega^{2}

which is a limit ordinal not fixed by γ\gamma. We note another point that will be used later: taking the limit “eliminates” the smallest terms. More generally, we can perform the same calculation, starting from any arbitrary αω\alpha\geq\omega:

Proposition 0.1.

For any limit ordinal α\alpha and 1n<ω1\leq n<\omega we have

γ(α+n)=γ(α)+α2n+n\gamma(\alpha+n)=\gamma(\alpha)+{\alpha\cdot{2n}}+n
Proof.

For n=1n=1 this is the relation for γ(α+1)\gamma(\alpha+1) explained above. If the relation is true for nn then

γ(α+n+1)=γ(α+n)+(α+n)2+1\gamma(\alpha+n+1)=\gamma(\alpha+n)+{\left(\alpha+n\right)\cdot 2}+1
γ(α+n+1)=γ(α)+α2n+n+α+n+α+n+1\gamma(\alpha+n+1)=\gamma(\alpha)+{\alpha\cdot{2n}}+n+\alpha+n+\alpha+n+1

and since αω\alpha\geq\omega we have n+α=αn+\alpha=\alpha and so

γ(α+n+1)=γ(α)+α(2n+1)+n+1\gamma(\alpha+n+1)=\gamma(\alpha)+{\alpha\cdot{(2n+1)}}+n+1

Which shows the result at step n+1n+1. ∎

As above, we can take the limit and say γ(α+ω)=supn<ωγ(α+n)=γ(α)+αω{\gamma(\alpha+\omega)}=\sup_{n<\omega}{\gamma(\alpha+n)}=\gamma(\alpha)+% \alpha\cdot\omega which is consistent with γ(ω2)=ω+ω2=ω2{\gamma(\omega\cdot 2)}=\omega+\omega^{2}=\omega^{2}. However, if we consider the Cantor Normal Form α=ωβ1n1++ωβknk\alpha=\omega^{\beta_{1}}n_{1}+...+\omega^{\beta_{k}}n_{k}, then for all n<ωn<\omega we have can use the fact that “ωβ1\omega^{\beta_{1}} will eliminate smaller terms on its left” that is αn=ωβ1(n1n)+ωβ2n2++ωβknk\alpha\cdot n=\omega^{\beta_{1}}{(n_{1}n)}+\omega^{\beta_{2}}n_{2}+...+\omega^% {\beta_{k}}n_{k}. Then using the fact that “taking the limit eliminates the smallest terms” we get αω=supn<ωαn=ωβ1+1\alpha\cdot\omega=\sup_{n<\omega}\alpha\cdot n=\omega^{\beta_{1}+1}. So actually, we have a nicer formula where αω\alpha\cdot\omega is put in Cantor Normal Form:

αω,γ(α+ω)=γ(α)+ωlogω(α)+1\forall\alpha\geq\omega,{\gamma(\alpha+\omega)}=\gamma(\alpha)+\omega^{\log_{% \omega}(\alpha)+1}

This can be generalized by the following proposition:

Proposition 0.2.

For any αω\alpha\geq\omega and β1\beta\geq 1 such that logω(α)+1β\log_{\omega}(\alpha)+1\geq\beta we have

γ(α+ωβ)=γ(α)+ωlogω(α)+β{\gamma(\alpha+\omega^{\beta})}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+\beta}
Proof.

We prove by induction on β\beta that for all such α\alpha the expression is true. We just verified β=1\beta=1 and the limit case is obvious by continuity of γ\gamma and of the sum/exponentiation in the second variable. For the successor step, if logω(α)+1β+1\log_{\omega}(\alpha)+1\geq\beta+1 then a fortiori 1n<ω,logω(α+ωβn)+1β+1β\forall 1\leq n<\omega,\log_{\omega}(\alpha+\omega^{\beta}\cdot n)+1\geq\beta+% 1\geq\beta. We can then use the induction hypothesis to prove by induction on 1n<ω1\leq n<\omega that γ(α+ωβn)=γ(α)+ωlogω(α)+βn{\gamma(\alpha+{\omega^{\beta}\cdot n})}=\gamma(\alpha)+\omega^{\log_{\omega}(% \alpha)+\beta}\cdot n. For n=1n=1, this is just the induction hypothesis of β\beta (for the same α\alpha!). For the successor step, we need to use the induction hypothesis of β\beta (for α+ωβn\alpha+\omega^{\beta}\cdot n) which is γ(α+ωβ(n+1))=γ(α+ωβn)+ωlogω(α)+β{\gamma(\alpha+{\omega^{\beta}\cdot{(n+1)}})}={\gamma(\alpha+{\omega^{\beta}% \cdot n})}+\omega^{\log_{\omega}(\alpha)+\beta}. Finally, γ(α+ωβ+1)=sup1n<ωγ(α+ωβn)=γ(α)+ωlogω(α)+β+1{\gamma(\alpha+{\omega^{\beta+1}})}={\sup_{1\leq n<\omega}{\gamma(\alpha+{% \omega^{\beta}\cdot n})}}=\gamma(\alpha)+\omega^{\log_{\omega}(\alpha)+\beta+1}, as wanted. ∎

For all α1\alpha\geq 1, logω(ωα)+1=α+1\log_{\omega}(\omega^{\alpha})+1=\alpha+1 so the previous paragraph also gives γ(ωα+1)=γ(ωα+ωα+1)=γ(ωα)+ωα2+1{\gamma(\omega^{\alpha+1})}=\gamma\left(\omega^{\alpha}+\omega^{\alpha+1}% \right)={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2+1}. Then, we find

γ(ω2)=ω+ω3=ω3\gamma(\omega^{2})=\omega+\omega^{3}=\omega^{3}
γ(ω3)=ω3+ω5=ω5\gamma(\omega^{3})=\omega^{3}+\omega^{5}=\omega^{5}

And more generally by induction on n<ωn<\omega, we can show that

γ(ωn+1)=ω2n+1\gamma(\omega^{n+1})=\omega^{2n+1}

Then we deduce another fixed point

γ(ωω)=sup1n<ωγ(ωn)=ωω\gamma(\omega^{\omega})={\sup_{1\leq n<\omega}\gamma\left({\omega^{n}}\right)}% =\omega^{\omega}

The following proposition tries to generalize the expression of γ(ωα+1){\gamma(\omega^{\alpha+1})}.

Proposition 0.3.

For any α,β1\alpha,\beta\geq 1 such that logω(α)>logω(β)\log_{\omega}(\alpha)>\log_{\omega}(\beta) we have

γ(ωα+β)=γ(ωα)+ωα2+β{\gamma(\omega^{\alpha+\beta})}={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2% +\beta}
Proof.

This is done by induction on β<α\beta<\alpha for a fixed α\alpha. We already verified the case β=1\beta=1 in the previous paragraph and the limit case is obvious by continuity of γ\gamma and of the sum/exponentiation in the second variable. For the successor step, we have γ(ωα+β+1)=γ(ωα+β)+ω(α+β)2+1{\gamma(\omega^{\alpha+\beta+1})}={\gamma(\omega^{\alpha+\beta})}+\omega^{{(% \alpha+\beta)}\cdot 2+1} and by induction hypothesis, γ(ωα+β)=γ(ωα)+ωα2+β{\gamma(\omega^{\alpha+\beta})}={\gamma(\omega^{\alpha})}+\omega^{\alpha\cdot 2% +\beta}. Since logω(α)>logω(β+1)=logω(β)\log_{\omega}(\alpha)>\log_{\omega}(\beta+1)=\log_{\omega}(\beta) we have (α+β)2+1=α+β+α+β+1=α2+β+1>α2+β{(\alpha+\beta)}\cdot 2+1=\alpha+\beta+\alpha+\beta+1=\alpha\cdot 2+\beta+1>% \alpha\cdot 2+\beta and so ωα2+β+ωα2+β+1=ωα2+β+1\omega^{\alpha\cdot 2+\beta}+\omega^{\alpha\cdot 2+\beta+1}=\omega^{\alpha% \cdot 2+\beta+1}. Finally, γ(ωα+β+1)=γ(ωα+β)+ωα2+β+1{\gamma(\omega^{\alpha+\beta+1})}={\gamma(\omega^{\alpha+\beta})}+\omega^{% \alpha\cdot 2+\beta+1} as wanted. ∎

For any 1n<ω1\leq n<\omega and α1\alpha\geq 1, if 1β<ωα1\leq\beta<\omega^{\alpha} then logω(β)<α=logω(ωαn)\log_{\omega}(\beta)<\alpha=\log_{\omega}(\omega^{\alpha}\cdot n). Hence proposition 0.3 gives γ(ωωαn+β)=γ(ωωαn)+ωωα2n+β{\gamma(\omega^{{\omega^{\alpha}\cdot n}+\beta})}={\gamma(\omega^{{\omega^{% \alpha}\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{2n}}+\beta} Then by continuity of γ\gamma and of the sum/exponentiation in the second variable, we can consider the limit βωα\beta\rightarrow\omega^{\alpha} to get γ(ωωα(n+1))=γ(ωωαn)+ωωα(2n+1){\gamma(\omega^{{\omega^{\alpha}\cdot(n+1)}})}={\gamma(\omega^{{\omega^{\alpha% }\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{(2n+1)}}}. So continuing our calculation we have

γ(ωω2)=ωω+ωω3=ωω3{\gamma(\omega^{\omega\cdot 2})}=\omega^{\omega}+\omega^{\omega\cdot 3}=\omega% ^{\omega\cdot 3}
γ(ωω3)=ωω3+ωω5=ωω5{\gamma(\omega^{\omega\cdot 3})}=\omega^{\omega\cdot 3}+\omega^{\omega\cdot 5}% =\omega^{\omega\cdot 5}

and taking the limit we find another fixed point

γ(ωω2)=ωω2{\gamma(\omega^{\omega^{2}})}=\omega^{\omega^{2}}

then again

γ(ωω22)=ωω2+ωω23=ωω23{\gamma(\omega^{\omega^{2}\cdot 2})}=\omega^{\omega^{2}}+\omega^{\omega^{2}% \cdot 3}=\omega^{\omega^{2}\cdot 3}
γ(ωω23)=ωω23+ωω25=ωω25{\gamma(\omega^{\omega^{2}\cdot 3})}=\omega^{\omega^{2}\cdot 3}+\omega^{\omega% ^{2}\cdot 5}=\omega^{\omega^{2}\cdot 5}

and taking the limit we find another fixed point

γ(ωω3)=ωω3{\gamma(\omega^{\omega^{3}})}=\omega^{\omega^{3}}

More generally, we have the following proposition:

Proposition 0.4.

For any ordinal α\alpha and 1n<ω1\leq n<\omega we have

γ(ωωαn)=ωωα(2n-1){\gamma(\omega^{{\omega^{\alpha}\cdot n}})}=\omega^{{\omega^{\alpha}\cdot{(2n-% 1)}}}
Proof.

From the relation γ(ωωα(n+1))=γ(ωωαn)+ωωα(2n+1){\gamma(\omega^{{\omega^{\alpha}\cdot(n+1)}})}={\gamma(\omega^{{\omega^{\alpha% }\cdot n}})}+\omega^{{\omega^{\alpha}\cdot{(2n+1)}}}, we deduce by induction on nn that

n2,γ(ωωαn)=γ(ωωα)+ωωα(2n-1)\forall n\geq 2,{\gamma(\omega^{{\omega^{\alpha}\cdot n}})}={\gamma(\omega^{{% \omega^{\alpha}}})}+\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}

Taking the limit nωn\rightarrow\omega,we obtain

γ(ωωα+1)=γ(ωωα)+ωωα+1{\gamma(\omega^{{\omega^{\alpha+1}}})}={\gamma(\omega^{{\omega^{\alpha}}})}+% \omega^{{\omega^{\alpha+1}}}

We can then show by induction that all the ωωα\omega^{\omega^{\alpha}} are actually fixed points, using the previous relation at successor step, the continuity of γ\gamma at limit step and the fact that γ(ω)=ω\gamma(\omega)=\omega. This means

γ(ωωα)=ωωα=ωωα(2×1-1){\gamma(\omega^{{\omega^{\alpha}}})}=\omega^{{\omega^{\alpha}}}=\omega^{{% \omega^{\alpha}\cdot{(2\times 1-1)}}}

Then for n2n\geq 2, we get

γ(ωωαn)=γ(ωωα)+ωωα(2n-1)=ωωα+ωωα(2n-1)=ωωα(2n-1){\gamma(\omega^{{\omega^{\alpha}\cdot n}})}={\gamma(\omega^{{\omega^{\alpha}}}% )}+\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}={\omega^{{\omega^{\alpha}}}}+\omega% ^{{\omega^{\alpha}\cdot{(2n-1)}}}=\omega^{{\omega^{\alpha}\cdot{(2n-1)}}}

Equipped with these four propositions, we have a way to recursively calculate γ\gamma. We are ready to prove the main theorem:

Theorem 0.5.

For all ordinal α\alpha, we denote γ(α)\gamma(\alpha) the order-type of the canonical ordering of α×α\alpha\times\alpha. Then γ\gamma can be calculated as follows:

  1. 1.

    Finite Ordinals: For any n<ωn<\omega we have

    γ(n)=n2\gamma(n)=n^{2}
  2. 2.

    Limit Ordinals: For any limit ordinal α\alpha,

    1. (a)

      If ωlogω(logω(α))\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)} does not divide logω(α)\log_{\omega}(\alpha) then

      γ(α)=ωlogω(α)α\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\alpha
    2. (b)

      Otherwise, we write α=ωlogω(α)n+ρ\alpha={\omega^{\log_{\omega}(\alpha)}n}+\rho for some n1n\geq 1. If n2n\geq 2 then

      γ(α)=ωlogω(α)(ωlogω(α)(n-1)+ρ)\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left({\omega^{\log_{\omega}% (\alpha)}\cdot{(n-1)}}+\rho\right)

      (like the first case but we “decrement nn in the second factor”)

    3. (c)

      Otherwise, α=ωlogω(α)+ρ\alpha={\omega^{\log_{\omega}(\alpha)}}+\rho and we write logω(α)=ωlogω(logω(α))m\log_{\omega}(\alpha)=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha% \right)\right)}m for some m1m\geq 1. We have

      γ(α)=ωlogω(α)(ωωlogω(logω(α))(m-1)+ρ)\gamma(\alpha)=\omega^{\log_{\omega}(\alpha)}\cdot\left(\omega^{\omega^{\log_{% \omega}\left(\log_{\omega}\left(\alpha\right)\right)}\cdot\left(m-1\right)}+% \rho\right)

      (like the first case but we “decrement mm in the second factor”)

  3. 3.

    Infinite Successor Ordinals: For any limit ordinal α\alpha and 1n<ω1\leq n<\omega we have

    γ(α+n)=γ(α)+α2n+n\gamma(\alpha+n)=\gamma(\alpha)+{\alpha\cdot{2n}}+n

    where γ(α)\gamma(\alpha) is determined as in the previous point.

Proof.

The “Finite Ordinals” has been discussed at the beginning and the “Infinite Successor Ordinals” is proposition 0.1. Now let’s consider the Cantor Normal Form ωβ1n++ωβknk\omega^{\beta_{1}}n+...+\omega^{\beta_{k}}n_{k} of a limit ordinal αω\alpha\geq\omega (so βk1\beta_{k}\geq 1 and β1=logω(α)\beta_{1}=\log_{\omega}(\alpha)). First, from proposition 0.2 we can make successively extract the nkn_{k} terms ωβk\omega^{\beta_{k}} (by left-multiplying them by ωβ1\omega^{\beta_{1}}), then the nk-1n_{k-1} terms ωβk-1\omega^{\beta_{k-1}}, … then the n2n_{2} terms ωβ2\omega^{\beta_{2}} and finally n-1n-1 terms ωβ1\omega^{\beta_{1}}. We obtain:

γ(α)=γ(ωβ1)+ωβ1(ωβ1(n-1)+ωβ2n2++ωβknk){\gamma(\alpha)}={\gamma(\omega^{\beta_{1}})}+{\omega^{\beta_{1}}\left(\omega^% {\beta_{1}}{(n-1)}+\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}\right)}

We now write β1=ωδm+σ\beta_{1}=\omega^{\delta}m+\sigma where δ=logωβ1\delta=\log_{\omega}{\beta_{1}} and m,σm,\sigma are the quotient and remainder of the Euclidean division of β1\beta_{1} by ωδ\omega^{\delta}. We can then use proposition 0.3 to extract σ\sigma:

σ=0γ(ωβ1)=γ(ωωδm)\sigma=0\implies{\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{\delta}m})}
σ0γ(ωβ1)=γ(ωωδm)+ωωδ(2m)+σ\sigma\neq 0\implies{\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{% \delta}m})}+\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}

Finally, using proposition 0.4 we obtain

γ(ωωδm)=ωωδ(2m-1){\gamma(\omega^{\omega^{\delta}m})}=\omega^{{\omega^{\delta}\cdot{(2m-1)}}}

σ0\sigma\neq 0 means that ωδ=ωlogω(logω(α))\omega^{\delta}=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)% \right)} does not divide β1=logω(α)\beta_{1}={\log_{\omega}(\alpha)}. In that case, ωωδ(2m)+σ>ωωδ(2m-1)\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}>\omega^{{\omega^{\delta}\cdot{(2m-1% )}}} and so γ(ωβ1)=ωωδ(2m)+σ{\gamma(\omega^{\beta_{1}})}=\omega^{\omega^{\delta}\cdot{(2m)}+\sigma}. We note that β12=ωδm+σ+ωδm+σ=ωδ(2m)+σ\beta_{1}\cdot 2=\omega^{\delta}m+\sigma+\omega^{\delta}m+\sigma=\omega^{% \delta}{(2m)}+\sigma since the remainder σ\sigma is less than ωδ\omega^{\delta}. So actually γ(ωβ1)=ωβ1ωβ1{\gamma(\omega^{\beta_{1}})}=\omega^{\beta_{1}}\omega^{\beta_{1}}. Coming back to the expression of γ(α)\gamma(\alpha), this term can be grouped with ωβ1(n-1)\omega^{\beta_{1}}{(n-1)} to recover the Cantor Normal Form of α\alpha and we finally get γ(α)=ωβ1α\gamma(\alpha)=\omega^{\beta_{1}}\alpha.

Otherwise, σ=0\sigma=0, β1=ωδm\beta_{1}=\omega^{\delta}m and

γ(ωβ1)=γ(ωωδm)=ωωδ(2m-1)=ωβ1ωωδ(m-1){\gamma(\omega^{\beta_{1}})}={\gamma(\omega^{\omega^{\delta}m})}=\omega^{{% \omega^{\delta}\cdot{(2m-1)}}}={\omega^{\beta_{1}}{\omega^{\omega^{\delta}% \cdot{(m-1)}}}}

But then β1=ωδm>ωδ(m-1)\beta_{1}=\omega^{\delta}m>{\omega^{\delta}{(m-1)}} and so ωβ1ωβ1>ωβ1ωωδ(m-1)\omega^{\beta_{1}}\omega^{\beta_{1}}>\omega^{\beta_{1}}\omega^{{\omega^{\delta% }\cdot{(m-1)}}}. Hence if n2n\geq 2, the term γ(ωβ1){\gamma(\omega^{\beta_{1}})} is eliminated in the expression of γ(α)\gamma(\alpha) and it remains

γ(α)=ωβ1(ωβ1(n-1)+ρ){\gamma(\alpha)}={\omega^{\beta_{1}}\left(\omega^{\beta_{1}}{(n-1)}+\rho\right)}

where ρ=ωβ2n2++ωβknk\rho=\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}. If instead n=1n=1, then the term ωβ1(n-1)\omega^{\beta_{1}}{(n-1)} is zero and it remains

γ(α)=ωβ1(ωωδ(m-1)+ωβ2n2++ωβknk){\gamma(\alpha)}={\omega^{\beta_{1}}\left(\omega^{{\omega^{\delta}\cdot{(m-1)}% }}+\omega^{\beta_{2}}n_{2}+\dots+\omega^{\beta_{k}}n_{k}\right)}