Every well-ordering is isomorphic to the set of all lesser ordinals under ordinal comparison

Question

Wikipedia states that

Every well-ordered set (S,<) is order isomorphic to the set of ordinals less than one specific ordinal number [the order type of (S,<)] under their natural ordering.

I've been trying to find proofs on the Internet of this theorem at an appropriate level of rigor, but am entirely at a loss.

The best motivation I've found for defining von Neumann ordinals as the set of all lesser ordinals is that every well-ordering is order isomorphic to the set of all lesser ordinals under the ordinal comparison operation. Since I'm trying to use this theorem as a way to motivate defining ordinals, all I'd like to use in the proof is a supposition that ordinals are canonical representatives of order types, and not worry about how they're concretely defined.

I'm supposing that I've already proven that ordinal comparison is a well-ordering. How might I go about this proof? (Can I even do it without the von Neumann definition?) Thanks!

Clarification: My goal is not to show that every well-ordering is isomorphic to an ordinal. It is to show that every well-ordering is already isomorphic to a set of canonical representations of all lesser order types under ordinal comparison, so we might as well define ordinals as sets of all lesser ordinals, which is the von Neumann construction.

Answer 1

This probably doesn't answer OP question, (as I don't know what he really wants), but I copied it from some rough notes of mine.

We must use the axiom of replacement. Consider the formula

$$\varphi(x, \beta) \equiv \beta \ \mbox{is an ordinal} \wedge L_x \cong (\beta,<).$$

$\varphi$ is a function since if $(\beta,<) \cong (\gamma,<)$, where $\beta$ and $\gamma$ are ordinals then $\beta=\gamma$. Then by the axiom of replacement there is a set $X$ such that $$X= \{ \beta \ | \ (\exists x \in L) \ \varphi(x, \beta) \}.$$ The set $X$ is a set of ordinals, furthermore $X$ is transitive, thus $X$ is an ordinal let $X=\alpha$. Also the domain of $\varphi$ is an initial segment of $L$. I claim that $\operatorname{dom} \varphi = L$ since otherwise $\operatorname{dom} \varphi = L_x$ for some $x \in L$, and so $\alpha \cong L_x$ and thus $\alpha$ itself is in the domain of $\varphi$. The set $ f \subseteq \{ (x, \beta) \in \alpha \times L \ | \ L_x \cong (\beta,<) \}$ is an isomorphism.

Answer 2

You mention that you want an argument that doesn't invoke the specific nature of ordinals. This is in fact something we can do - specifically, we can show that the stated result holds whenever we have a reasonable notion of "representatives" of well-orderings. This is the argument below:

---

Suppose I have a class of representatives for all well-orderings - that is, I have a way to assign to each well-ordering $W$ a well-ordering $REP(W)$ such that the following are equivalent:

• $W_0$ and $W_1$ are order-isomorphic.

• $REP(W_0)=REP(W_1)$. That's literally "$=$," not just "$\cong$."

(So the $REP(W)$s really do represent isomorphism types of well-orderings.) Call these $REP(W)$s representative well-orders.

Now there are two important things to note here:

• There is a natural relation $\trianglelefteq$ on the class of representative well-orders: $A\trianglelefteq B$ iff there is an order-preserving injection of $A$ into $B$. This is clearly transitive and reflexive, and it can be shown that it is in fact a (class) well-ordering on the class of representative well-orders. NOTE: this is the only place where transfinite induction is used here.

In the particular case of the von Neumann ordinals, "$\alpha\trianglelefteq\beta$" is equivalent to "$\alpha\in\beta$," so the von Neumann approach has the advantage of making "$\trianglelefteq$" particularly nice to define.

• Given a well-ordering $W$, not only is there the associated representative $REP(W)$, but there is also a function $F_W$ from $W$ to the class of representative well-orders: given $w\in W$, let $$F_W(w)=REP(W\upharpoonright w)$$ (where $W\upharpoonright w$ is the sub-well-order of $W$ consisting of elements $<_Ww$), and remember that by definition of $REP$ the orderings $F_W(w)$ and $W\upharpoonright w$ are order-isomorphic.

The map $F_W$ has a few nice properties; the following is key:

If $u\le_Wv$ then $F_W(u)\trianglelefteq F_W(v)$.

To prove this, note that we have a few functions here:

• There is the inclusion map $j$ from $W\upharpoonright u$ to $W\upharpoonright v$ - this is order-preserving.

• There are order-isomorphisms $i_u: W\upharpoonright u\rightarrow F_W(u)$ and $i_v: W\upharpoonright v\rightarrow F_W(v)$ giving representatives for the initial segments of $W$ associated to $u$ and $v$, respectively.

---

Alright, so what? Let's remember our goal:

For every well-ordering $W$, $W$ is isomorphic to the set $\{REP(W\upharpoonright w): w\in W\}$ ordered by $\trianglelefteq$.

The obvious candidate isomorphism is the map sending $w$ to $REP(W\upharpoonright w)$; we just need to show that this is an isomorphism.

We want, then, an order-preserving injection $C$ (for comparison) from $F_W(u)$ to $F_W(v)$, and we can get this as follows: $$C(x)=i_v(j(i_u^{-1}(x))).$$ That is:

• We take some $x$ in $F_W(u)$.

• Where do we send it? Well, first we convert it to an element of $W\upharpoonright u$, by pulling back along $i_u$. Remember that $i_u$ is a bijection, so this is something we can do.

• OK, now we have an element of $W\upharpoonright u$ and we want to put it into $F_W(v)$. There's an obvious way to do this: first, throw it over to $W\upharpoonright v$ using the inclusion map $j$, and then bump that into $F_W(v)$ via the isomorphism $i_v$. So that's what we do.

It's easy to check that $C$ is in fact an order-preserving injection, the key being that each of the maps along the way - $i_u^{-1}$, $j$, and $i_v$ - was order-preserving and injective.

Answer 3

Let $(S,<)$ be any well-ordered set, and let $Ord$ denote your class of canonical representatives (I'm not assuming the Von Neumann definition, but the hypotheses I'm using will become clear along the proof).

Then let $F(x, \alpha)$ be an abbreviation for $x \in S\land \alpha \in Ord \land S[x]\simeq \alpha$, where $\simeq$ means "order-isomorphic" and $S[x] = \{y\in S : y<x\}$.

Then, if $F(x,\alpha), F(x, \beta)$, we get $\alpha \simeq \beta$, and so if we assume that elements of $Ord$ are pairwise non-isomorphic (which is the point of "canonical representatives"), we have $\alpha = \beta$, so $F$ is a functional relation. (Note that I'm also assuming that elements of $Ord$ are sets, not full-isomorphism classes for instance)

By the axiom schema of replacement, the following is a set $B=\{\alpha : \exists x, F(x,\alpha) \}$, and $f= \{(x, \alpha) : F(x, \alpha)\}$ is a function from a subset of $S$ to $B$.

If we assume that $Ord$ contains representatives for each isomorphism type (which again is kind of wanted for "canonical representatives"), then this function is actually defined on $S$; and by classical properties of well-orderings, it is injective: it is an isomorphism onto its image.

Now if we let $\gamma \in Ord$ be the representative isomorphic to $S$, it is clear that $B \subset \{\alpha: \alpha \in Ord \land \alpha < \gamma \}$, where $<$ is the "can be embedded" relation on $Ord$. Let $\delta$ be the least element in $Ord$ (you've assumed that the comparison relation was a well-ordering) such that $B \subset \{\alpha: \alpha \in Ord \land \alpha < \delta \}$.

Now let $\beta \in Ord, \beta < \delta$. By minimality, there is $\lambda \in B$ such that $\beta \leq \lambda$. Consider $x$ such that $\lambda \simeq S[x]$. Then any embedding $\beta \to \lambda$ provides an embedding $\beta \to S[x]$, so an embedding $\beta \to S$ with proper image, so there is an embedding $\beta \to S$ where the image of $\beta$ is a proper initial segment of $S$ (classical property of well-orderings), and so $\beta \simeq S[y]$ for some $y\in S$: $\beta \in B$, and so $B= \{\alpha: \alpha \in Ord \land \alpha < \delta \}$ which is what you wanted to prove, since $B$ and $S$ are isomorphic.

Answer 4

We start by a simple observation which is true for any totally ordered set, not only for well-ordered sets.

Let $(X,\le)$ be a linearly ordered set. We will use the notation $X_a=\{x\in X; x<a\}$ pre $a\in X$. Notice that these sets are initial segments of $X$.

Observation. Let $(X,\le)$ be a linearly ordered set and let $X'=\{X_a; a\in X\}$. Then the function $f\colon X\to{X'}$ defined as $$f(a)=X_a$$ is an isomorphism between the ordered sets $(X,\le)$ and $(X',\subseteq)$.

Proof. We can see immediately that $f$ is surjective. If $a<b$ then $a\in X_b$ and $a\notin X_a$, so $f(a)=X_a\ne X_b=f(b)$. The case $b<a$ is symmetric. So it is also injective.

The map $f$ is monotone: If $a \le b$ then $f(a)=\{x\in X; x<a\} \subseteq \{x\in X; x<b\}=f(b)$. (It suffices to notice that $x<a$ and $a\le b$ implies $x<b$ by transitivity.)

To see that also $f^{-1}$ is monotone, we notice that $X_a\subseteq X_b$ implies $a\le b$. (If we had $a>b$, then $b\in X_a\setminus X_b$, which contradicts $X_a\subseteq X_b$.) $\hspace{1cm}\square$

Side remark. Notice that we have used linearity of $\le$ in the above proof. The version of the above observation with $\{x\in X; x\le a\}$ instead of $X_a$ is true also for partially ordered sets and it implies that every partially ordered set is isomorphic to some system of sets ordered by inclusion (in fact, to a subset of $(\mathcal P(X),\subseteq)$.) See, for example, Theorem 1.11 in S. Roman: Lattices and Ordered Sets or this question.

How does this relate to ordinals? We can view ordinals as representatives or order types of well-ordered sets. (At least if we approach them in the naive rather than axiomatic way.) We can define inequality between ordinals via initial embeddings of the corresponding well-ordered sets. (I.e., ordinal type of $(A,\le)$ is less or equal to ordinal type of $(B,\preceq)$ iff $A$ is isomorphic to an initial segment of $B$. This seems to be the natural way how to compare ordinals/well-ordered sets.)

So the above lemma shows that a well-ordered set $X$ is isomorphic to the set of proper initial segments of $X$. Ordinal types of these initial segments are precisely the ordinals lesser than the ordinal type of $X$.