# Constructing a bijection between $\xi$ and $\xi + 1$

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.

-
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

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.

-
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