We are working in ZF.

Problem (part 1). Suppose we have well-ordered set $(M, <)$. How to show that there exists a bijection $f$ between this set and some ordinal $x$ that preserves order?

I can use the following theorem:

Theorem. Let $F$ be a functional and $(A, <)$ be a well-redered set. Then $\exists!f\ Dom(f) = A$ and $f(x) = F(f|_{\{y \in A \mid y < x\}})$ for all $x \in A$.

If we will take $F := S(x) = x \cup \{x\}$ then we will automatically gain $f$ and for sure it preserves order, but how to rigorously show this fact?

Problem (part 2). How to show that this ordinal $x$ and bijection are unique?

As for uniqueness of the bijection it follows from the theorem, but how to deal with set $x$?


Your $F$ does not work. Note that $F$ should map functions defined on subsets of $A$ to elemens of the desired range (i.e., ordinals), but you define $F$ on ... ordinary elements, so to speak.

Instead, let $F(g):=\operatorname{img}(g)$. Then for example $f(\min A)=F(f|_\emptyset)=\operatorname{img}(f|\emptyset)=\emptyset$. Show by induction that $f(x)$ is the smallest ordinal exceeding all $f(y)$, $y<x$.

For uniqeness, you can get rid of general well-ordered sets. Show that an order-preserving bijection between two ordinals is necessarily the identity.

  • $\begingroup$ Yeah, you are right! So, am I correct that we can not apply this theorem directly? Probably, I have to repeat the proof of this theorem with slight changes for our semi-functional (since it is not defined on all sets) $F(g) = Im(g)$ and showing that order is preserved at each induction step. Am I right? $\endgroup$ – Jihad Apr 2 '15 at 20:58

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.