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

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

It is well-known that the cartesian product of two infinite sets of cardinality α\aleph_{\alpha} is also of cardinality α\aleph_{\alpha}. Equivalently, the set ωα×ωα\omega_{\alpha}\times\omega_{\alpha} can be well-ordered in order-type ωα\omega_{\alpha}. However, the standard ordering on ωα×ωα\omega_{\alpha}\times\omega_{\alpha} does not work, since it is always of order type ωα2\omega_{\alpha}^{2}. Instead, we introduce for each ordinal α\alpha the canonical well-ordering of α×α\alpha\times\alpha as follows: (ξ1,ξ2)(η1,η2){(\xi_{1},\xi_{2})}\lhd{(\eta_{1},\eta_{2})} if either max(ξ1,ξ2)<max(η1,η2){\max{(\xi_{1},\xi_{2})}}<{\max{(\eta_{1},\eta_{2})}} or max(ξ1,ξ2)=max(η1,η2){\max{(\xi_{1},\xi_{2})}}={\max{(\eta_{1},\eta_{2})}} but (ξ1,ξ2)(\xi_{1},\xi_{2}) precedes (η1,η2)(\eta_{1},\eta_{2}) lexicographically. If we note γ(α)\gamma(\alpha) the ordinal isomorphic to that well-ordering ordering, then we can prove that γ(ωα)=ωα\gamma(\omega_{\alpha})=\omega_{\alpha} as wanted (see Corollary 0.4).

Jech’s Set Theory book contains several properties of γ\gamma. For example, γ\gamma is increasing : for any ordinal α\alpha, α×α\alpha\times\alpha is a (proper) initial segment of (α+1)×(α+1){(\alpha+1)}\times{(\alpha+1)} and of λ×λ\lambda\times\lambda for any limit ordinal λ>α\lambda>\alpha. As a consequence, α,αγ(α)\forall\alpha,\alpha\leq\gamma(\alpha) which can also trivially be seen by the increasing function ξ(ξ,0)\xi\mapsto(\xi,0) from α\alpha to α×α\alpha\times\alpha. Also, α,γ(α)<γ(λ)\forall\alpha,\gamma(\alpha)<\gamma(\lambda) implies supα<λγ(α)γ(λ)\sup_{\alpha<\lambda}{\gamma(\alpha)}\leq\gamma(\lambda). This can not be a strict equality, or otherwise the element (ξ,η)λ×λ{(\xi,\eta)}\in\lambda\times\lambda corresponding to supα<λγ(α)\sup_{\alpha<\lambda}{\gamma(\alpha)} via the isomorphism between λ×λ\lambda\times\lambda and γ(λ)\gamma(\lambda) would be an element larger than all (α,α)(\alpha,\alpha) for α<λ\alpha<\lambda. Hence γ\gamma is continuous and by exercise 2.7 of the same book, γ\gamma has arbitrary large fixed points. Exercise 3.5 shows that γ(α)ωα\gamma(\alpha)\leq\omega^{\alpha} and so γ\gamma does not increase cardinality (see Corollary 0.2 for a much better upper bound). Hence starting at any infinite cardinal κ\kappa the construction of exercise 2.7 provides infinitely many fixed points of γ\gamma having cardinality κ\kappa. Hence the infinite fixed points of γ\gamma are not just cardinals and we can wonder what they are exactly…

I recently tried to solve Exercise I.11.7 of Kunen’s Set Theory book which suggests a nice characterization of infinite fixed points of γ\gamma: they are the ordinals of the form ωωα\omega^{\omega^{\alpha}}. However, I could not find a simple proof of this statement so instead I tried to determine the explicit expression of γ(α)\gamma(\alpha), from which the result becomes obvious (see Corollary 0.3). My final calculation is summarized in Theorem 0.1, which provides a relatively nice expression of γ(α)\gamma(\alpha). Recall that any α1\alpha\geq 1 can be written uniquely as α=ωβq+ρ\alpha=\omega^{\beta}q+\rho where β\beta is (following Kunen’s terminology) the “logarithm in base ω\omega of α\alpha” (that we will denote logωα\log_{\omega}{\alpha} for αω\alpha\geq\omega) and q,ρq,\rho are the quotient and remainder of the Euclidean division of α\alpha by ωβ\omega^{\beta}. Alternatively, this can be seen from Cantor’s Normal Form: β\beta and qq are the exponent and coefficient of the largest term while ρ\rho is the sum of terms of smaller exponents.

Theorem 0.1.

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.

In a future blog post ;-) ∎

From this theorem, we deduce several corollaries:

Corollary 0.2.

For any ordinal α\alpha, we have

αγ(α)ωlogω(α)(α-r)+α2rα(α+r)\alpha\leq{\gamma(\alpha)}\leq{{\omega^{\log_{\omega}(\alpha)}\cdot\left({% \alpha-r}\right)}+{\alpha\cdot{2r}}}\leq\alpha\left(\alpha+r\right)

where r=αmodωr=\alpha\mod\omega is the remainder in the Euclidean division of α\alpha by ω\omega (i.e. the constant term in the Cantor Normal Form).

Proof.

The “Limit Ordinals” case is r=0r=0 i.e. αγ(α)ωlogω(α)α\alpha\leq{\gamma(\alpha)}\leq{{\omega^{\log_{\omega}(\alpha)}\cdot\alpha}}, which is readily seen by the previous theorem. Then we deduce for the “Infinite Successor Ordinals” case: γ(α+n)=γ(α)+α2n+nωlogω(α)α+(α+n)2n{\gamma(\alpha+n)}=\gamma(\alpha)+{\alpha\cdot{2n}}+n\leq{{\omega^{\log_{% \omega}(\alpha)}\cdot\alpha}}+{\left(\alpha+n\right)\cdot{2n}} where logω(α+n)=logω(α){\log_{\omega}(\alpha+n)}={\log_{\omega}(\alpha)} and n=(α+nmodω)n=\left(\alpha+n\mod\omega\right). Since ωlogω(α)α\omega^{\log_{\omega}(\alpha)}\leq\alpha we can write ωlogω(α)(α-r)+α2rα(α-r+2r)=α(α+r){{\omega^{\log_{\omega}(\alpha)}\cdot\left({\alpha-r}\right)}+{\alpha\cdot{2r}% }}\leq{\alpha\cdot\left(\alpha-r+2r\right)}={\alpha\cdot{(\alpha+r)}}. ∎

Hence the order type of the canonical ordering \lhd of α×α\alpha\times\alpha (i.e. γ(α)α(α+ω)\gamma(\alpha)\leq\alpha{(\alpha+\omega)}) is never significantly bigger than the one of the standard lexical ordering (i.e. α2\alpha^{2}), and even never larger for limit ordinals. Moreover, for many ordinals α\alpha the canonical ordering is of order type α\alpha:

Corollary 0.3.

The fixed points of γ\gamma are 0,10,1 and ωωα\omega^{\omega^{\alpha}} for all ordinals α\alpha.

Proof.

For the “Finite Ordinals” case, we have γ(n)=n2=n\gamma(n)=n^{2}=n iff n=0n=0 or n=1n=1. For the “Infinite Successor Ordinals” case, we have α2n>α\alpha\cdot{2n}>\alpha if n1n\geq 1 so γ(α+n)>α+n\gamma(\alpha+n)>\alpha+n. Now we look at the three subcases of the “Limit Ordinals” case. For the first one, we have logω(α)1\log_{\omega}(\alpha)\geq 1 and so ωlogω(α)αωα>α\omega^{\log_{\omega}(\alpha)}\alpha\geq\omega\alpha>\alpha. For the second one, we note that logω(α)2>logω(α){\log_{\omega}(\alpha)}2>\log_{\omega}(\alpha) and so ωlogω(α)2>α\omega^{{\log_{\omega}(\alpha)}2}>\alpha (compare the Cantor Normal Form). Since n-11n-1\geq 1 by assumption, we have γ(α)>α\gamma(\alpha)>\alpha. Similarly in the third case, if we expand the parenthesis the first term is ω\omega raised to the power ωlogω(logω(α))(2m-1){\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)\right)}\cdot\left% (2m-1\right)} which is stricly greater than logω(α)=ωlogω(logω(α))m\log_{\omega}(\alpha)=\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha% \right)\right)}m if m2m\geq 2. Now if m=1m=1, we obtain γ(α)=ωlogω(α)+ωlogω(α)ρ\gamma(\alpha)={\omega^{\log_{\omega}(\alpha)}+{\omega^{\log_{\omega}(\alpha)}% \rho}} and α=ωlogω(α)+ρ\alpha={\omega^{\log_{\omega}(\alpha)}}+\rho. Hence γ(α)>α\gamma(\alpha)>\alpha if ρ>0\rho>0 and γ(α)=α\gamma(\alpha)=\alpha if ρ=0\rho=0. Finally for αω\alpha\geq\omega, γ(α)=α\gamma(\alpha)=\alpha iff α=ωωlogω(logω(α))\alpha=\omega^{\omega^{\log_{\omega}\left(\log_{\omega}\left(\alpha\right)% \right)}} iff α=ωωβ\alpha=\omega^{\omega^{\beta}} for some ordinal β\beta. ∎

Finally, now that we know that infinite fixed points of γ\gamma are of the form α=ωωβ\alpha=\omega^{\omega^{\beta}} we only need to verify that infinite cardinals κ\kappa are of this form to prove that |κ×κ|=κ{|\kappa\times\kappa|}=\kappa. This provides an alternative (less straightforward) proof of Theorem 3.5 from Jech’s Set Theory book.

Corollary 0.4.

Any infinite cardinal κ\kappa is a fixed point of γ\gamma. Hence for any infinite cardinal κ1,κ2\kappa_{1},\kappa_{2} we have

κ1+κ2=κ1κ2=max(κ1,κ2)\kappa_{1}+\kappa_{2}=\kappa_{1}\kappa_{2}={\max(\kappa_{1},\kappa_{2})}
Proof.

For any cardinal infinite cardinal μ\mu that is a fixed point of γ\gamma, the canonical well-ordering provides a bijection between μ\mu and μ×μ\mu\times\mu i.e. μ2=μ\mu^{2}=\mu. Hence if μ1μ2\mu_{1}\leq\mu_{2} are two fixed points, we have

μ2μ1+μ2μ1μ2μ22=μ2\mu_{2}\leq{\mu_{1}+\mu_{2}}\leq{\mu_{1}\mu_{2}}\leq\mu_{2}^{2}=\mu_{2}

Suppose that there is a cardinal κ\kappa which is not a fixed point of γ\gamma and consider the smallest one. Then any infinite cardinal below κ\kappa is a fixed point of γ\gamma and the previous equality is still true below κ\kappa.

Suppose κ>ωlogωκ\kappa>\omega^{\log_{\omega}{\kappa}} and write κ=ωlogωκ+ρ\kappa=\omega^{\log_{\omega}{\kappa}}+\rho where ρ<κ\rho<\kappa corresponds to the remaining terms in Cantor Normal Form. Then 0μ1=|ωlogωκ|<κ\aleph_{0}\leq\mu_{1}=\left|\omega^{\log_{\omega}{\kappa}}\right|<\kappa, μ2=|ρ|<κ\mu_{2}={|\rho|}<\kappa and μ1+μ2=κ\mu_{1}+\mu_{2}=\kappa. But the two first relations imply μ1+μ2=max(μ1,μ2)<κ\mu_{1}+\mu_{2}=\max(\mu_{1},\mu_{2})<\kappa which contradicts the third one. Hence κ=ωlogωκ\kappa=\omega^{\log_{\omega}{\kappa}}.

Now suppose logωκ>ωlogωlogωκ\log_{\omega}{\kappa}>\omega^{\log_{\omega}{\log_{\omega}{\kappa}}} and write logωκ=ωlogωκ+ρ\log_{\omega}{\kappa}=\omega^{\log_{\omega}{\kappa}}+\rho where ρ<logωκ\rho<\log_{\omega}{\kappa} corresponds to the remaining terms in Cantor Normal Form. Then we have

κ=ωlogωκ=ωωlogωlogωκωρ\kappa=\omega^{\log_{\omega}{\kappa}}=\omega^{\omega^{\log_{\omega}{\log_{% \omega}{\kappa}}}}\omega^{\rho}

where ωωlogωlogωκ<ωlogωκ=κ\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}}<\omega^{\log_{\omega}{% \kappa}}=\kappa and ωρ<ωlogωκ=κ\omega^{\rho}<\omega^{\log_{\omega}{\kappa}}=\kappa since αωα\alpha\mapsto\omega^{\alpha} is strictly increasing. Then 0μ1=|ωωlogωlogωκ|<κ\aleph_{0}\leq\mu_{1}=\left|\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa% }}}}\right|<\kappa, μ2=|ωρ|<κ\mu_{2}={|\omega^{\rho}|}<\kappa and μ1μ2=κ\mu_{1}\mu_{2}=\kappa. But again, the two first relations imply μ1μ2=max(μ1,μ2)<κ\mu_{1}\mu_{2}=\max(\mu_{1},\mu_{2})<\kappa which contradicts the third one.

Finally, κ=ωωlogωlogωκ\kappa=\omega^{\omega^{\log_{\omega}{\log_{\omega}{\kappa}}}} and so is a fixed point of γ\gamma, a contradiction. Hence all the infinite cardinals are fixed point of γ\gamma and so the property stated at the beginning is true for arbitrary infinite cardinals μ1,μ2\mu_{1},\mu_{2}. ∎