1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you phrase your hint in other way? I can't seem to get any insights from this. $\endgroup$ – Joshhh Jan 11 '16 at 17:08
  • $\begingroup$ 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. $\endgroup$ – Paul Sinclair Jan 11 '16 at 17:40
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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.