# If $\alpha$ is an indecomposable ordinal, why $\Gamma(\alpha\times{\alpha})=\alpha$?

Greets

This is from exercise 3.4 of Thomas Jech's "Set Theory", stated:

"Show that $\Gamma(\alpha\times{\alpha})\leq{\omega^{\alpha}}$. Thus $\Gamma(\alpha\times{\alpha})=\alpha$ for all indecomposable ordinals $\alpha$".

$\Gamma$ is the Gödel pairing function on ordinals. An ordinal $\alpha$ is indecomposable if there are no $\beta<\alpha$ and $\gamma<\alpha$ such that $\beta+\gamma=\alpha$.

The first part is trivial, since it holds for $\alpha=0$, and the function $\omega^{\alpha}$ is normal in the variable $\alpha$.

I'm having trouble to show the second part, the only connection I see is the fact that $\gamma$ is indecomposable if and only if $\gamma=\omega^{\alpha}$ for some $\alpha$, which is easily proven from Cantor's normal form theorem.

Any help will be appreciated.

-
What is $\Gamma$? What does indecomposable mean? – Chris Eagle Dec 10 '12 at 16:56
I just corrected it. Thanks – Camilo Arosemena Dec 10 '12 at 17:07
The "thus" part is false. The ordinals closed under Gödel pairing are precisely the multiplicatively indecomposable $\alpha$, that is, $1$, and those of the form $\omega^{\omega^\beta}$. – Andrés E. Caicedo Dec 10 '12 at 17:25
thanks, @AndresCaicedo – Camilo Arosemena Dec 10 '12 at 19:53

This is also an exercise in Kunen 2011 (p. 67) which I am studying at the moment. Here is how I proved it. Kunen's version of the exercise is as follows:

Exercise I.11.7. For $\alpha \geq \omega$, show that $\mbox{type}(\alpha \times \alpha, \lhd) = \alpha$ iff $\alpha = \omega^{\mu}$, where $\mu$ is either $1$ or an infinite decomposable ordinal.

Here $\lhd$ is the canonical well ordering on ONxON. Note that Kunen introduces decomposable ordinals in a previous exercise:

Exercise I.9.53. Let $\gamma$ be a limit ordinal. Show that the following are equivalent:

1. $\forall \alpha,\beta < \gamma \:\: [\alpha + \beta < \gamma]$.

2. $\forall \alpha < \gamma \:\: [\alpha + \gamma = \gamma]$.

3. $\forall X \subseteq \gamma \:\: [\mbox{type}(X)=\gamma \vee \mbox{type}(\gamma\setminus X)=\gamma]$.

4. $\exists \delta \:\: [\gamma = \omega^\delta]$. $\blacksquare$

Such $\gamma$ are called (additively) indecomposable.

Before proving Exercise I.11.7, I proved the following proposition, the proof of which I will not reproduce here.

Proposition. For any ordinal $\alpha> 2$, the following conditions are equivalent:

1. $\beta\cdot\alpha = \alpha$ for all non-zero $\beta<\alpha$.

2. $\xi\cdot\eta < \alpha$ for all $\xi, \eta < \alpha$.

3. $\alpha$ is of the form $\omega^{\omega^{\delta}}$ for some ordinal $\delta$. $\blacksquare$

An ordinal $\alpha$ satisfying the above conditions is called multiplicatively indecomposable. We can use this terminology to restate the exercise as follows:

Exercise I.11.7. For $\alpha \geq \omega$, show that $\mbox{type}(\alpha \times \alpha, \lhd) = \alpha$ iff $\alpha$ is multiplicatively indecomposable.

# Warm-up

Before proving the exercise, I tried to get better acquainted with the function $$\Gamma (\alpha , \beta) \: = \: \mbox{type}\{(\xi,\eta) : (\xi,\eta) \lhd (\alpha , \beta) \}.$$ Observe that $$\Gamma (0,\alpha) = \mbox{type}(\alpha \times \alpha, \lhd).$$ So the exercise I.11.7. directly involves the function $\Gamma$.

For example, for finite ordinals $n\in \omega$ we have $$\Gamma (0,n) = \mbox{type}(n \times n, \lhd) = n^2.$$

The function $\Gamma$ behaves at successor steps in the second coordinate as follows: $$\Gamma (\alpha , \beta+1) = \left\{ \begin{array}{ll} \Gamma (\alpha , \beta) + 1 & \mbox{if } \alpha > \beta \\ \Gamma (\alpha , \beta) + \beta & \mbox{if } \alpha = \beta \\ \Gamma (\alpha , \beta) + \gamma + \beta + 1 + \alpha & \mbox{if } \alpha < \beta \end{array} \right.$$ where $\gamma$ in the third case is the unique ordinal satisfying $\alpha + \gamma = \beta$.

One can prove this formula by writing down the chain of $\lhd$-successors from $(\alpha, \beta)$ to $(\alpha, \beta+1)$. The first case is obvious since if $\alpha > \beta$ then $(\alpha, \beta+1)$ is the $\lhd$-successor of $(\alpha, \beta)$. The second case follows from the chain of $\lhd$-successors $$(\beta,\beta) \: \lhd \: (0,\beta+1) \: \lhd \: (1,\beta+1) \: \lhd \: (2,\beta+1) \: \lhd \: \cdots \: \lhd \: (\beta,\beta+1).$$ In the third case, the chain is as follows: \begin{align*} (\alpha, \beta) & \: \lhd \: (\alpha+1, \beta) \: \lhd \: (\alpha+2, \beta) \: \lhd \: \cdots \: \lhd \: (\xi,\beta) \: \lhd \: \cdots \\ \mbox{} & \: \lhd \: (\beta, 0) \: \lhd \: (\beta, 1) \: \lhd \: \cdots \: \lhd \: (\beta, \beta) \\ \mbox{} & \: \lhd \: (0,\beta +1) \: \lhd \: (1,\beta +1) \: \lhd \: \cdots \: \lhd \: (\alpha, \beta+1) \end{align*} The $\xi$ in the first line takes values $\alpha < \xi <\beta$.

By considering the $\lhd$-predecessors when $\lambda$ is limit, one can get $$\Gamma (\alpha , \lambda) = \left\{ \begin{array}{ll} \sup_{\xi < \lambda} \Gamma (\alpha , \xi) & \mbox{if } \alpha \geq \lambda \\ \sup_{\xi < \lambda} \Gamma (\alpha , \xi) \: + \: \alpha & \mbox{if } \alpha < \lambda \end{array} \right.$$

We will make use of the following particular instances of the above formulas: \begin{align*} \Gamma(0, \beta +1) & = \Gamma(0,\beta) + \beta + \beta + 1 \\ & \\ \Gamma(0, \lambda ) & = \sup_{\xi < \lambda} \Gamma (0 , \xi) \:\:\:\:\: \mbox{ if } \lambda \mbox{ is limit} \end{align*}

Kunen also remarks that (p. 67) $$\Gamma (0,\alpha) = \mbox{type}(\alpha \times \alpha, \lhd) \geq \alpha .$$

If $(\alpha,\beta)+1$ is the $\lhd$-successor of $(\alpha,\beta)$ then $$(\alpha,\beta)+1 \: = \: \left\{ \begin{array}{ll} (0,\beta+1) & \mbox{ if } \alpha = \beta \\ (\alpha+1,\beta) & \mbox{ if } \alpha < \beta \\ (\alpha,\beta+1) & \mbox{ if } \alpha > \beta. \end{array} \right.$$ Let us call $(\delta,\gamma)$ limit if $$\forall (\xi,\eta)\in\text{ON}\times\text{ON} \quad \big[(\xi,\eta)\lhd (\delta,\gamma) \rightarrow (\xi,\eta)+1 \lhd (\delta,\gamma) \big].$$ Then $$(\delta, \gamma) \text{ is limit } \quad \text{ iff } \quad \gamma\text{ is limit or } [\delta < \beta \wedge \delta \text{ is limit}].$$

# Proof of the Exercise

Lemma. For all ordinals $\alpha$ we have $\Gamma(0,\alpha) < \alpha \cdot \alpha + 1$.

Proof. This lemma holds clearly for finite $\alpha$: If $n\in \omega$, then $$\Gamma (0,n) = \mbox{type}(n \times n, \lhd) = n^2 < n\cdot n +1.$$ Let us prove the lemma by induction on $\alpha$. We may assume that $\alpha \geq \omega$.

If $\alpha = \beta +1$ for some $\beta$ and $\Gamma(0,\beta)< \beta\cdot\beta + 1$ then \begin{align*} \Gamma(0,\beta + 1) & \: = \: \Gamma(0,\beta) + \beta + \beta + 1 \: \leq \: \beta\cdot \beta + 1 + \beta + \beta + 1 \: = \: \beta\cdot \beta + \beta + \beta + 1 \\ & \: = \: (\beta +1)\cdot (\beta +1) \: < \: (\beta +1)\cdot (\beta +1)+1 \end{align*}

If $\alpha$ is limit and $\Gamma(0,\xi)<\xi\cdot \xi +1$ for all $\xi <\alpha$ then $$\Gamma(0,\alpha) \: = \: \sup_{\xi < \lambda} \Gamma(0,\xi) \: \leq \: \sup_{\xi < \lambda} (\xi\cdot \xi +1) \: \leq \: \alpha\cdot \alpha \: < \: \alpha\cdot \alpha +1.$$ This completes the induction. $\blacksquare$

Lemma. If $\alpha < \omega^{\delta}$ then $\Gamma(0,\alpha) < \omega^{\omega^{\delta}}$.

Proof. Assume that $\alpha < \omega^{\delta}$. Then $\alpha < \omega^{\omega^{\delta}}$ as well. Since $\omega^{\omega^{\delta}}$ is multiplicatively indecomposable, $\alpha\cdot \alpha < \omega^{\omega^{\delta}}$. As $\omega^{\omega^{\delta}}$ is limit we have $\alpha\cdot \alpha + 1 < \omega^{\omega^{\delta}}$. Thus $\Gamma(0,\alpha) < \alpha\cdot \alpha + 1 < \omega^{\omega^{\delta}}$. $\blacksquare$

This lemma gives us one direction of the exercise:

Lemma. $\Gamma (0, \omega^{\omega^{\delta}}) = \omega^{\omega^{\delta}}.$

Proof. $\Gamma (0, \omega^{\omega^{\delta}}) \: = \: \sup_{\xi < \omega^{\omega^{\delta}}} \Gamma (0, \xi) \: \leq \: \sup_{\xi < \omega^{\omega^{\delta}}} \omega^{\omega^{\delta}} \: = \: \omega^{\omega^{\delta}}$. $\blacksquare$

The following inequality will establish the other direction of the exercise.

Lemma. $\alpha\cdot \alpha < \Gamma(0,\alpha + \alpha) + 1$.

Proof. We will show the lemma by induction on $\alpha$. Since $n\cdot n < (n+n)^2 + 1$ for $n\in\omega$, this lemma is true for finite ordinals. From now on we may assume that $\alpha \geq \omega$.

Assume that $\alpha=\beta +1$ for some $\beta$ and $\beta\cdot\beta < \Gamma(0,\beta+\beta) +1$. Then \begin{align*} \Gamma(0,(\beta+1)+(\beta+1)) & \: = \: \Gamma(0,\beta+\beta+1) \: = \: \Gamma(0,\beta+\beta) + \beta + \beta +\beta + \beta + 1 \\ & \geq \: \beta\cdot \beta + \beta + \beta+ \beta+ \beta + 1 \: \geq \: (\beta+1)\cdot (\beta+1). \end{align*} So $(\beta+1)\cdot (\beta+1) < \Gamma(0,(\beta+1)+(\beta+1)) +1$.

Now assume that $\alpha$ is limit and $\xi\cdot\xi < \Gamma(0,\xi+\xi)+1$ holds for all $\xi<\alpha$. Then $$\Gamma(0,\alpha+\alpha) \: = \: \sup_{\xi<\alpha+\alpha} \Gamma(0,\xi) \: \geq \: \sup_{\alpha<\xi<\alpha+\alpha} \Gamma(0,\xi) \: \geq \: \sup_{\alpha<\xi<\alpha+\alpha} \xi \: = \: \alpha+\alpha.$$ Hence $\alpha + \alpha < \Gamma(0,\alpha + \alpha) + 1$. This completes the induction. $\blacksquare$

Finally, we have:

Lemma. If $\Gamma(0,\alpha) = \alpha$ then $\alpha$ is multiplicatively indecomposable.

Proof. Assume that $\Gamma(0,\alpha) = \alpha$ . Clearly, $\alpha$ is a limit ordinal. It suffices to show that if $\gamma < \alpha$ then $\gamma\cdot\gamma < \alpha$. Since $$\gamma + \gamma \: < \: \Gamma(0,\gamma) + \gamma + \gamma +1 \: = \: \Gamma(0,\gamma+1) \: < \: \Gamma(0,\alpha) \: = \: \alpha$$ we have $\gamma + \gamma < \alpha$ and $$\Gamma(0,\gamma+\gamma) \: < \: \Gamma(0,\alpha) \: = \: \alpha.$$ As $\alpha$ is a limit, we have $\Gamma(0,\gamma+\gamma) + 1 < \alpha$ as well. Thus $$\gamma+\gamma \: < \: \Gamma(0,\gamma+\gamma) +1 \: < \: \alpha$$ and $\alpha$ is multiplicatively indecomposable. $\blacksquare$

-
there are some errors, which aren't significant, you're prove is understandable and is correct, thanks!!!! – Camilo Arosemena Dec 11 '12 at 13:54
@Camilo Arosemena. You're welcome. Can you please post any errors you find. – Ali Kare Dec 13 '12 at 14:43