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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I did the following exercise, can you tell me if I have it right, thank you (Just/Weese p 176):

Show that $|\xi + 1|$ is either finite or equal to $|\xi|$. (here $\xi$ is an ordinal)

By contradiction assume $\xi + 1$ is infinite and $|\xi + 1|>|\xi|$.

For an infinite ordinal $S$ we can construct a bijection $f: S + 1 \to S $ as follows: Let $S + 1 = S \cup \{\ast\}$. Then define $\ast \mapsto s_0$ where $s_0 = \min S$ and $s \mapsto \min (S \setminus f[I(s)])$ where $I(s) = \{s' \in S \mid s' < s\} \cup \{\ast\}$ is the initial segment of $s$ together with the additional element.

share|cite|improve this question
I'm confused by your definition of the initial segment. But if you're doing what I think you're doing, you have a slight problem since you send $s_0$ to itself. – Miha Habič Dec 12 '12 at 16:15
@MihaHabič Thank you, that was a rather unfortunate typo: I wrote "\min" instead of "\mid". – Rudy the Reindeer Dec 12 '12 at 16:17
@MihaHabič And you are also right about the definition. I will fix it. – Rudy the Reindeer Dec 12 '12 at 16:19
Also, you should write $f[I(s)]$ or $f''I(s)$ in your definition. The distinction between the direct and pointwise image of a set becomes unbelievably important later on, and by being careful now you save yourself a lot of confusion. – Miha Habič Dec 12 '12 at 16:29
The pointwise image of a set $A$ is $f[A]=\{f(a);a\in A\}$ and the direct image is just $f(A)$. The difference arises when you deal with sets whose elements are also its subsets. For example, suppose I have a function $f$ defined on the set $\{\emptyset\}$. Then $f(\emptyset)$ might be anything, but $f[\emptyset]=\emptyset$. – Miha Habič Dec 12 '12 at 16:35
up vote 5 down vote accepted

It seems a bit convoluted. More simply you could say that if $\xi \ge \omega$ then you can define a bijection $f:\xi+1 \to \xi$ as follows:

  • $f(\xi) = 0$
  • If $\alpha \in \xi$ and $\alpha < \omega$ then $f(\alpha)=\alpha+1$
  • If $\alpha \in \xi$ and $\alpha \ge \omega$ then $f(\alpha) = \alpha$

This is very similar to what you did. Essentially, it puts the top element to $0$ and increments all the naturals, and leaves everything else fixed.

On the point of style: you could have cut off your entire first sentence and started the proof with "For an infinite ordinal $S$ ...". It's an example of the classic $$\text{[Suppose not X]}-\text{[Proof of X]}-\text{[Therefore not not X]}$$ when just $\text{[Proof of X]}$ would have sufficed.

share|cite|improve this answer
Thank you! I was trying to map the top element to zero and shift up all the rest. – Rudy the Reindeer Dec 12 '12 at 16:28

Your Answer


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.