I have a problem with the following exercise:

First a definition: $ \mathord{\in} = \{\langle x,y \rangle; x \in y \}$

Exercise: Show that the following conditions are equivalent:

a. For every $\beta,\gamma < \alpha$, $\beta + \gamma < \alpha$

b. For every $\beta < \alpha$, $\beta + \alpha = \alpha$

c. For every $A \subseteq \alpha$, $\operatorname{order-type}(\langle A,\in\rangle) = \alpha$, or, $\operatorname{order-type}(\langle A \setminus \alpha,\in \rangle) = \alpha$

d. There exists an ordinal $\delta$ such that, $\alpha = \omega^\delta$

Anyone have a hint for me? Especially for c. I tried to prove $a \implies b$ by induction, but I am not sure whether the induction should be on $\alpha$ or on $\gamma$. I also don't quite get the intuition behind this. Especially, the intuition of part c.

Thank you!! Shir

  • $\begingroup$ (c) says that if you partition $\alpha$ into two subsets sets and look at the ordering the subsets inherit from $\alpha$, at least one of them will have order type $\alpha$. Or, in other words, you cannot get $\alpha$ by mixing two well-orders that are each shorter than $\alpha$. This easily implies (a). $\endgroup$ – Henning Makholm Nov 1 '13 at 9:44
  • $\begingroup$ The jargon is "additively indecomposable" for (a) and "strongly indecomposable" for (c). It follows from this exercise that the two notions are the same for ordinals, but they are different for general order types, as shown by the example $(\omega^*+\omega)\omega$ which is additively but not strongly indecomposable. $\endgroup$ – bof Nov 1 '13 at 10:19
  • $\begingroup$ @ Henning Makholm thank you for your answer! $\endgroup$ – topsi Nov 2 '13 at 12:27

First, a minor point, you should assume $\alpha\gt0$; if $\alpha=0$, then the first three statements are true, but the last is false.

(a)$\Rightarrow$(b): Suppose $\beta\lt\alpha$. Clearly $\alpha\le\beta+\alpha$; assume for a contradiction that $\alpha\lt\beta+\alpha$. Then we have $\beta\lt\alpha\lt\beta+\alpha$, which implies that $\alpha=\beta+\gamma$ for some ordinal $\gamma\lt\alpha$. Now we have $\beta,\gamma\lt\alpha$ and $\beta+\gamma=\alpha$, contradicting (a).

(b)$\Rightarrow$(a): $\beta+\gamma\lt\beta+\alpha=\alpha$.

(c)$\Rightarrow$(b): Suppose $\beta\lt\alpha$. Write $\alpha=\beta+\gamma$. Applying (c) with $A=\beta$, either $\beta=\alpha$ or $\gamma=\alpha$. Since $\beta\lt\alpha$, we must have $\gamma=\alpha$ and $\beta+\alpha=\beta+\gamma=\alpha$.

(a)$\Rightarrow$(d): We have $\omega^{\delta}\le\alpha\lt\omega^{\delta+1}$ for some ordinal $\delta$. Assume for a contradiction that $\omega^{\delta}\lt\alpha\lt\omega^{\delta+1}$. By (a) we have $\omega^{\delta}2\lt\alpha$ and, by induction, $\omega^{\delta}n\lt\alpha$ for all $n\lt\omega$, whence $\alpha\ge\omega^{\delta}\omega=\omega^{\delta+1}$, a contradiction.

(d)$\Rightarrow$(c): Proof by induction on $\delta$. The straightforward details are left to the reader. By the way, what we are proving here is the partition relation $\omega^{\delta}\rightarrow(\omega^{\delta},\omega^{\delta})^1$ in the infamous "arrow notation" of Erdős and Rado.

  • $\begingroup$ In (a) to (d) it should be noted that it requires some proof (which the OP should be able to furnish) that there is a largest $\delta$ such that $\omega^\delta\le\alpha$. Also, you don't actually seem to use the assumption that $\alpha$ is infinite. $\endgroup$ – Henning Makholm Nov 1 '13 at 9:49
  • $\begingroup$ @HenningMakholm: Oh, right, I only use that $\alpha\ge1$. $\endgroup$ – bof Nov 1 '13 at 10:09
  • $\begingroup$ @bof: Thank you!! I have tried to write the induction down. here it is: math.stackexchange.com/questions/548942/… what do you think?? $\endgroup$ – topsi Nov 2 '13 at 12:27
  • $\begingroup$ I don't grade papers. Your proof is just a blur to my weak eyes. Under high magnification I read the opening lines. Let me abbreviate "order-type" to "tp" and $\omega^{\eta}$ to $\alpha$ so I won't have to type so much. If it's (d)$\Rightarrow$(c) that you're proving, then you want to say "either $tp(A)=\alpha$ or $tp(\alpha\setminus A)=\alpha$" NOT "either $tp(A)=\alpha$ or $\alpha\setminus tp(A)=\alpha$". (c) is not about subtracting ordinals from ordinals. It says that, if you take a set of order type $\alpha$ and partition it into two sets, at least one of them will have type $\alpha$. $\endgroup$ – bof Nov 2 '13 at 13:13

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.