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.

  • $\begingroup$ 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 $\endgroup$
    – ℋolo
    Jul 10 '18 at 19:13
  • $\begingroup$ 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)$. $\endgroup$ Jul 10 '18 at 20:10
  • $\begingroup$ 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. $\endgroup$ Jul 10 '18 at 20:11

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.