Ordinal comparison trichotomy

Question

How does one prove rigorously that ordinal comparison is trichotomous; that is, exactly one of the following is true:

1. $(A, <_A) \cong (B, <_B)$
2. $\exists a \in A : (A, <_A)/a \cong (B, <_B)$
3. $\exists b \in B : (A, <_A) \cong (B, <_B)/b$

where the notation $(X, <_X)/u$ means the initial segment of the well-ordering $(X,<_X)$ bounded by $u$.

I have no real idea why this makes sense; I found this proof:

Let Z be the set of all z in X such that I(z) is order-isomorphic to an initial segment of Y. If z is in Z and w< z then it is easy to see that w is in Z. Hence, either Z is all of X or it is the initial segment I(u), where u is the least element of X that does not belong to Z. Next, I claim that if z is in Z, then there is exactly one isomorphism from I(z) to an initial segment of Y. For if not, let w be minimal such that there are two distinct order-isomorphisms f and g from I(w) to initial segments of Y. Let v be minimal such that f(v) does not equal g(v). Then f and g must agree on the initial segment I(v), and f(v) and g(v) are then forced to be the least element of Y that does not belong to f(I(v)). This observation allows us to define an order-isomorphism from Z into Y - each z in Z maps to the least element of Y not included in f(I(z)). Then either f(Z)=Y, in which case we are done, or f(Z) is a proper subset of Y, in which case Z must be the whole of X or we'd be able to extend f.

But it's not succinct at all. I also have a textbook proof that states

Let $f = \{ (v,w) : v \in \alpha \wedge w \in \beta \wedge (\alpha, <)/v \cong (\beta,<)/w \}$ and note that $f$ is an isomorphism from some initial segment of A onto some initial segment of $B$, and that these initial segments cannot both be proper.

which seems insufficiently rigorous for my purposes.

(EDIT: I removed half of this question, since it was buried at the end and unclear, and will ask it again.)

Answer 1

Regarding well-orders:

Let $<_A$ be a well-order on $A$ . A proper initial segment of $A$ is $\{a\in A:a<_Aa_0\}=pred_{<_A}(a_0)$ for some $a_0\in A$.( "pred" is for "predecessors".)

Let $(A,<_A)$ and $(B,<_B)$ be well-orders. We have:

(1). The only order-isomorphic bijection $f:A\to A$ is $id_A.$

(2)(a). There is no order-isomorphism from $A$ onto a proper initial segment of $A.$

(2)(b). Corollary to (2)(a). If $a_1<_A a_2$ then there is no order-isomorphism from $pred_{<_A}(a_1)$ onto $pred_{<_A}(a_2). $

(3). There is at most one order-isomorphism from $A$ onto $B.$

(4). Trichotomy: Exactly one of these holds: (i). $A$ is order-isomorphic to $B.$ (ii). $A$ is order-isomorphic to a proper initial segment of $B.$ (iii). $B$ is order-isomorphic to a proper initial segment of $A.$

(1) and (2) can be proved by contradiction. For (1) if $f\ne id_A,$ consider $a_0=\min_{<_A}\{a\in A:f(a)\ne a\}.$

For (2)(a) if $f:A\to pred_{<_A}(a)$ is an order-isomorphism then $f(a)\ne a.$ Consider $a_0=\min_{<_A}\{a'\in A:f(a')\ne a'\}$. Show that $a_0<_Af(a_0),$ so $a_0\in pred_{<_A}(a).$ Consider $a_1=f^{-1}(a_0).$

For (3), if $f:A\to B$ and $g:A\to B$ are order-isomorphisms then $(g^{-1}f):A\to A$ is an order-isomorphic bijection, so by (1), $g^{-1}f=id_A.$

For (4), let $a\in A_1\subset A$ iff $pred_{<_A}(a)$ is order-isomorphic to $pred_{<_B}(f(a))$ for some $f(a)\in B.$ Then $f(a)$ is unique for $a\in A_1$ by (2)(b). The uniqueness of $f(a)$ allows us to use the Replacement Axiom to define the function $f:A_1\to B.$ We can now easily show that $f$ is order-preserving. And easily show that (i) if $A_1=A$ then $f$ maps $A$ onto $B$ or onto a proper initial segment of $B$ ( but not both, by (2)(a)),and (ii) if $A_1\ne A$ then $A_1$ is a proper initial segment of $A,$ and $f$ maps $A_1$ onto $B.$

Regarding ordinals:

Suppose a well-order $(A,<_A)$ is not isomorphic to any ordinal, or to any proper initial segment of any ordinal (which is also an ordinal). Then by (4) every ordinal is isomorphic to $pred_{<A}(a)$ for some $a\in A.$ The uniqueness of $f(a)$ in the preceding paragraph enables us to use the Replacement Axiom to deduce the existence of the set $On$ of all ordinals. But then the def'n of "ordinal" implies that $On$ is an ordinal, so $On\in On.$ The issue here is not the axiom of Foundation (a.k.a.Regularity) but that a well-order is, by def'n, irreflexive: A well-order < cannot have any $x$ with $x< x.$ But we would have $x<x\in On$ if $x=On\in On.$

Footnotes: Re :(4). If $a'<_A a\in A_1$ and $\phi:pred_{<_A}(a)\to pred_{<_B}(f(a))$ is an order-isomorphism then $f$ maps $pred_{<_A}(a')$ order-isomorphically onto $pred_{<_B}(\phi(a'),$ so $a'\in A_1$ and $f(a')=\phi(a')<_Bf(a).$

And you might wish to also define $b\in B_1\subset B$ iff there is an order-isomorphism from $pred_{<_B}(b)$ to $pred_{<_A}(g(b))$ for some $g(b)\in A.$

Re: $On.$ Let $A'$ be the set of all $a\in A$ such that $pred_{<_A}(a)$ is isomorphic to an ordinal $f(a).$ Note that $A'$ exists by the Comprehension Axiom. The uniqueness of $f(a)$ for each $a\in A'$ allows the use of Replacement to obtain $\{f(a):a\in A'\}$.

Answer 2

We will show that if $\mathfrak{v}$ and $\mathfrak{w}$ are ordinal numbers of sets $V$ and $W$ then exactly one of the possibilities $\mathfrak{v} < \mathfrak{w}$, $\mathfrak{w} < \mathfrak{v}$ or $\mathfrak{v} = \mathfrak{w}$ is true.

We first observe that an intersection of initial segments of a well-ordered set is itself an initial segment. Therefore, an intersection of all initial segments which is just the singleton containing the least element is also an initial segment.

Since $V$ and $W$ are well-ordered they have least elements, say $\alpha$ and $\beta$ and therefore, $\{\alpha\}$ and $\{\beta\}$ are the (smallest) initial segments of the corresponding sets.

Let $\mathcal{F}$ be the set of all order-preserving isomorphisms between $V$ or an initial segment of $V$ and $W$ or an initial segment of $W$. $\mathcal{F}$ is a subset of $V \times W$. A mapping $\{\alpha\} \mapsto \{\beta\}$ is clearly an order-preserving isomorphism and therefore a member of $\mathcal{F}$, making $\mathcal{F}$ a non-empty set.

We can introduce an order in $\mathcal{F}$ by inclusion. That is, if $f_1, f_2 \in \mathcal{F}$ then $f_1 \le f_2$ if $f_1 \subset f_2$. Let $\mathcal{S}$ be a linearly ordered subset of $\mathcal{F}$. $\mathcal{S}$ has an upper bound consisting of the union of all its elements. Since $\mathcal{F}$ is ordered by set-inclusion, it is definitely a partially-ordered set. We also showed that any linearly ordered subset of $\mathcal{F}$ has an upper bound. Therefore, by Zorn's lemma, $\mathcal{F}$ has at least one maximal element, say $h$.

Let, if possible, domain of $h$ be $V(x)$ for some $x \in V$ and range of $h$ be $W(y)$ for some $y \in W$. Then $h^\ast = h \cup \{(x, y)\}$ is also an order- preserving isomorphism and a member of $\mathcal{F}$. Moreover $h^\ast \ge h$ violating the fact that $h$ is the maximal element.

Therefore, either domain of $h$ is V, in which case $\mathfrak{v} < \mathfrak{w}$ or the range of $h$ is $W$, in which case $\mathfrak{w} < \mathfrak{v}$ or both are true, in which case $\mathfrak{v} = \mathfrak{w}$.