# isomorphism from well ordered set to ordinal

Given $\langle X,<_{_X}\rangle$ well ordered set, show there exists unique ordinal $\alpha$ such that $\langle X,<_{_X}\rangle\cong \langle \alpha,\in\rangle$

Proving the uniqueness is easy, but I have a problem proving existence, instead of searching for $\alpha$ itself I think it will be easier to show that there exists $\gamma$(ordinal) such that there is isomorphism between an initial segment of $\gamma$ and $X$(as initial segment of ordinals are ordinals):

If there no such $\gamma$ we can conclude that for every ordinal $\alpha$ there is $X_\alpha\subsetneq X$ such that $\langle X_\alpha,<_{_X}\rangle\cong \langle \alpha,\in\rangle$ by theorem(The comparison theorem for well-orders).

Now I am not sure if I can stop with:

We got that the set $X$ has subset as large as arbitrary ordinal, which implies that $Ord$ is a set, contradiction

Or do I need to really construct a surjective function from $X$ to $Ord$ and then by the axioms $Ord$ is a set or something alike.

Here's an approach that, in a sense, combines both methods you were considering. The idea is to inductively embed ordinals into $(X, \le_X)$ until you can't any more, and then deduce that the ordinal you finished up with is the ordinal you seek.

First note that $(0, \in)$ embeds trivially into $(X, \le_X)$.

Suppose there is an embedding $i_{\alpha} : (\alpha, \in) \hookrightarrow (X, \le_X)$, and consider the set $X_{\alpha} = X \setminus i_{\alpha}[\alpha]$.

• If $X_{\alpha}$ is empty, then you can deduce that $i_{\alpha}$ is an isomorphism.
• If $X_{\alpha}$ is inhabited, then it has a $\le_X$-least element $x_{\alpha}$, and then there is an embedding $i_{\alpha+1} : (\alpha + 1, \in) \hookrightarrow (X, \le_X)$ which extends $i_{\alpha}$ and satisfies $i_{\alpha}(\alpha) = x_{\alpha}$.

Now suppose $\beta$ is a limit ordinal and that there are embeddings $i_{\alpha} : (\alpha, \in) \hookrightarrow (X, \le_X)$ for each $\alpha < \beta$ such that $i_{\alpha} \subseteq i_{\alpha'}$ for all $\alpha \le \alpha' < \beta$. Define $i_{\beta} = \bigcup_{\alpha < \beta} i_{\alpha}$ and note that $i_{\beta}$ is an embedding $(\beta, \in) \hookrightarrow (X, \le_X)$.

This process must eventually terminate, since $(\alpha, \in)$ does not embed into $(X, \le_X)$ whenever $|\alpha| > |X|$, and the only way it can terminate is when for some $\alpha$ we have $i_{\alpha} : (\alpha, \in) \hookrightarrow (X, \le_X)$ and $X_{\alpha} = \varnothing$.

There are a couple of gaps in the proof to be filled in, but I'm sure you can flesh out the details.

• Sorry, my english is not perfect, what do you mean "embed into"? What you did is creating with recurrence definition function $i_\alpha$ that stopped when the image is equal to $X$(when we have isomorphism), and we know it has to stop at some point since... again the embed into, sorry about the inconvenience – ℋolo Jul 10 '18 at 19:13
• What I mean by "$(\alpha, \in)$ embeds into $(X, \le_X)$" is that there is an order-embedding $i_{\alpha} : (\alpha, \in) \hookrightarrow (X, \le_X)$, i.e. an injective function $i_{\alpha} : \alpha \to X$ satisfying $\beta \le \gamma \Rightarrow i_{\alpha}(\beta) \le i_{\alpha}(\gamma)$. – Clive Newstead Jul 10 '18 at 20:10
• Re-reading my proof, it's actually important to note that each $i_{\alpha}$ is an isomorphism from $(\alpha, \in)$ to an initial segment of $(X, \le_X)$. That's what allows you to deduce that when the process terminates, the embedding you constructed is an isomorphism. – Clive Newstead Jul 10 '18 at 20:11