# Well ordering of order types

Notice: in this problem I shouldn't use any properties of the ordinals, and order types are not defined as ordinals.

Let $A,B$ be well ordered sets. We say that $otp(A) = otp(B)$, if $A,B$ are isomorphic, $otp(A) < otp(B)$ if $A$ is isomorphic to a proper initial segment of $B$, and $otp(B) < otp(A)$, the same.

I need to prove that the collection of all order types ($otp$'s) is well ordered.

For total ordering - anti-reflexivity is due to the fact that no set is isomorphic to any of its initial segments. Transitivity is due to the fact that if $otp(A) < otp(B), otp(B)<otp(C)$, it follows that $A$ is isomorphic to an initial segment of $B$ with $f:A\to B$, and $B$ is isomorphic to an initial segment of $C$ with $g:B\to C$. It follows that $range(f)$ is isomorphic to an initial segment of $C$, and therefore $g\circ f$ is an isomorphism between $A$ and an initial segment of $C$, i.e $otp(A) < otp(C)$.

Totality is due to the fact that every pair of well ordered sets are either isomorphic or one is embedded to the other.

I encountered a problem when trying to prove that every subset has a least element. I thought maybe showing, somehow, that there is a single initial segment that can be embedded into any other set in a set of well-ordered sets.

HINT: Given a set $S$ of well-ordered sets. First, pick a well-ordered set $A$ in $S$ at random. If there are no elements of $S$ less than it, then it is a least element. Otherwise, the consider the elements of $S$ less than $A$. You want to show that the elements of $S$ have a least element; what you know is that each subset of $A$ has a least element. Can you find a way to turn elements of $S$ less than $A$ into elements of $A$?

• Could you phrase your hint in other way? I can't seem to get any insights from this. – Joshhh Jan 11 '16 at 17:08
• Every element of $S$ less than $A$ corresponds to an initial segment of $A$, and thus to the least element of $A$ that is not in this initial segment. Choose the least element of $A$ that corresponds to some element of $S$, then the corresponding element of $S$ is the minimum you are after. – Paul Sinclair Jan 11 '16 at 17:40

Suppose that $X$ is a non-empty collection of order types. Pick some $A$ such that $\operatorname{otp}(A)\in X$, then consider $X_A=\{\operatorname{otp}(B)\in X\mid\operatorname{otp}(B)<\operatorname{otp}(A)\}$.

Show that $X_A$ has a least element due to the fact that $A$ is well-ordered, and conclude that $X$ also has a least element; or that $X_A$ is empty and $\operatorname{otp}(A)$ is the least element you wanted.

Assume $A$ is a set of order-types $\alpha$ with no minimal element. For each $\alpha \in A$, choose a set $b_\alpha$ where $otp(b) = \alpha$ and let $B$ be the ordered set of all such $b$ such that $b_\alpha < b_\beta \leftrightarrow \alpha < \beta \leftrightarrow$ there is a proper initial segment of $b_\beta$ isomorphic to $b_\alpha$.

It can be easily shown that no well-ordered set can have an infinite decreasing sequence of proper initial segments, which means given any $b_\alpha$, there must be some $b_\beta < b_\alpha$ that is not isomorphic to an initial segment of $b_\alpha$, so $\beta \geq \alpha$, a contradiction.

• Doesn't $\omega$ have an infinite sequence of proper initial segments? – Joshhh Jan 11 '16 at 16:48
• Sorry I meant to say infinite decreasing sequence of proper initial segments, which $\omega$ does not have. – Dan Simon Jan 11 '16 at 17:55