Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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}$. –  Andres Caicedo Dec 10 '12 at 17:25
    
thanks, @AndresCaicedo –  Camilo Arosemena Dec 10 '12 at 19:53
add comment

1 Answer

up vote 5 down vote accepted

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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