# Bijection between well-ordered set and ordinal

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$?

## 1 Answer

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.

• 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? – Jihad Apr 2 '15 at 20:58