I'm self studying Kunen (2013 edition) right now, and got stuck on this exercise - I generally lack the tools and/or intuition for these kind of ordinal arithmetic exercises.

Exercise. Let $\alpha\geq\omega$. Then $type(\alpha\times\alpha,\vartriangleleft)=\alpha$ iff $\alpha=\omega^\mu$ for $\mu=1$ or $\mu$ infinite indecomposable ordinal.

As for the definitions:

Definition. A limit ordinal $\gamma$ is indecomposable if any (hence, all) of the following equivalent statements hold:

  1. $\forall\alpha,\beta<\gamma: \alpha+\beta<\gamma$
  2. $\forall\alpha<\gamma: \alpha+\gamma=\gamma$
  3. $\forall X\subseteq\gamma: type(X)=\gamma\lor type(\gamma\backslash X)=\gamma$
  4. $\exists\delta: \gamma=\omega^\delta$

Definition. $(\xi_1,\xi_2)\vartriangleleft(\eta_1,\eta_2)$ iff $\max(\xi_1,\xi_2)<\max(\eta_1,\eta_2)$ or $\max(\xi_1,\xi_2)=\max(\eta_1,\eta_2)$ and $(\xi_1,\xi_2)\prec(\eta_1,\eta_2)$, where $\prec$ is the lexicographical order.

I've tried the "$\Leftarrow$" direction, where the $\mu=1$ case seems straight forward, by grouping the elements into "blocks" of equal max value $n$, noticing these blocks have $2n+1$ elements and thus seeing that it's type is $\omega$. On the indecomposable case, I've tried to show inductively that $type(\omega^\delta\times\omega^\delta,\vartriangleleft)<\omega^\mu$ for all $\delta<\mu$, which therefore implies the wanted result (since $type(\alpha\times\alpha)\geq\alpha$ always hold). I can't see how I use indecomposability though, since I only use $\omega$ as base case, exploit $\mu$ being a limit in the successor case and that $\bigcup\{\omega^\zeta\mid\zeta<\gamma\}\leq\omega^\gamma$ for $\gamma$ limit.

I briefly tried the "$\Rightarrow$" direction, but I was completely lost as to how to even begin the argument.

Hints would be greatly appreciated.


For the "$\Leftarrow$" use the fact that $\mathbf{type}((\alpha+1)\times(\alpha+1),\lhd)=\mathbf{type}(\alpha\times\alpha,\lhd)+\alpha\cdot 2+1$, to prove by transfinite induction that $\mathbf{type}(\alpha\times\alpha,\lhd)\leq \alpha^3$ for all ordinals $\alpha$; then if $\gamma=\omega^\mu$ with $\mu$ indecomposable, we have $\mathbf{type}(\gamma\times\gamma,\lhd)=\sup\{\mathbf{type}(\alpha\times\alpha,\lhd):\alpha<\gamma\}$ as $\gamma$ is a limit ordinal, then by the bound given above we obtain $\mathbf{type}(\gamma\times\gamma,\lhd)\leq \gamma$; as $\alpha^3<\gamma$ for all $\alpha<\gamma$, but for any ordinal $\alpha$ we have $\mathbf{type}(\alpha\times\alpha,\lhd)\geq \alpha$.

Prove the other direction by contradiction. Using Cantor's normal form we have three cases:

  • If $\gamma=\omega^\theta$ with $\theta$ not indecomposable, there is $\mu<\gamma$ such that $\mu\cdot 2>\theta$; by the equivalent definitions you gave in your question, then prove that if $A=\{(\alpha,\xi):\alpha<\omega^\mu\wedge\omega^\mu\leq\xi<\omega^\mu\cdot 2\}$, $(A,\lhd)\simeq(\omega^{\mu\cdot 2},\in)$, and so $\mathbf{type}(\gamma\times\gamma,\lhd)\geq \mathbf{type}(\omega^\mu\cdot 2\times\omega^\mu\cdot 2,\lhd)\geq \omega^{\mu\cdot 2}>\gamma$.
  • If $\gamma=\omega^{\beta_n}\cdot l_n+\cdots+\omega^{\beta_1}\cdot l_1+l_0,$ with $l_n\geq 2$, if we put $m=l_n-1$, we get $\omega^{\beta_n}\cdot m+1<\gamma$, prove that $\mathbf{type}((\omega^{\beta_n}\cdot m+1)\times(\omega^{\beta_n}\cdot m+1),\lhd)\geq \omega^{\beta_n}\cdot 3\cdot m+1$, which implies $\mathbf{type}(\gamma\times\gamma,\lhd)> \gamma$.
  • If $\gamma=\omega^{\beta_n}\cdot l_n+\cdots+\omega^{\beta_1}\cdot l_1+l_0,$ with $l_n=1$ and $n\geq 1$, $\omega^{\beta_n}+1\leq \gamma$, so proving $\mathbf{type}((\omega^{\beta_n}+1)\times(\omega^{\beta_n}+1),\lhd)\geq\omega^{\beta_n}\cdot 3+1,$ it follows that $\mathbf{type}(\gamma\times\gamma,\lhd)> \gamma$.
  • $\begingroup$ Thanks! I have one quick question though. Say we have $\gamma=\omega^{\beta_n}\cdot l_n+\dots+\omega^{\beta_n}\cdot l_1+l_0$. Does it then always hold that $\omega^{\beta_n+1}>\gamma$ and $\omega^{\beta_n}\cdot(l_n+1)>\gamma$? And if not, then something close to? (Btw, in your first paragraph, I have presumed you meant "but for any ordinal $\alpha$ we have $type(\alpha\times\alpha,\vartriangleleft)\geq\alpha$".) $\endgroup$ – Dan Saattrup Nielsen Jul 27 '13 at 7:36
  • 1
    $\begingroup$ @Leidem: You're welcome!. Yes, indeed, we have both $\omega^{\beta_n+1}>\gamma$ and $\omega^{\beta_n}\cdot(l_n+1)>\gamma$, as $\omega^{\beta_n+1}\geq\gamma$ and $\omega^{\beta_n}\cdot(l_n+1)\geq\gamma$ and uniqueness of the Cantor normal form. $\endgroup$ – Camilo Arosemena-Serrato Jul 27 '13 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.