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.)

  • $\begingroup$ I suggest Set Theory: An Introduction To Independence Proofs by K. Kunen for most of the basics on ordinals. $\endgroup$ Dec 2 '17 at 4:13
  • $\begingroup$ Yeah, that's the book that I have. The proof that I mentioned was very vague, and I haven't found a proof anywhere of statement #5 (which is what's most important to me). All the introductions I've read essentially define von Neumann ordinals first and then demonstrate their properties, which I think is silly because it doesn't lend intuition as to why von Neumann chose the set of all lesser ordinals as canonical representatives of order types. Thus, proving this theorem is relatively integral to my understanding/my lecture. @DanielWainfleet $\endgroup$
    – singerng
    Dec 2 '17 at 4:18
  • $\begingroup$ Hmm, perhaps a proof by transfinite induction? It seems trivial for successor ordinals, but I'm not sure about limit ordinals. $\endgroup$
    – singerng
    Dec 2 '17 at 4:22
  • $\begingroup$ For the motivation of getting a transitive set, maybe math.stackexchange.com/questions/2516263/… can be helpful. $\endgroup$
    – Asaf Karagila
    Dec 2 '17 at 7:15
  • $\begingroup$ Perhaps von Neumann tried "looking up" from the empty set to see which sets can be shown to exist and worked it out by looking at examples, eventually arriving at $\cup_{\lambda \in On}V_{\lambda}.$ He had deep and diverse insight. $\endgroup$ Dec 2 '17 at 7:25

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'\}$.

  • $\begingroup$ How can we prove that this final set $A’$, under ordinal comparison, is order isomorphic to $A$? $\endgroup$
    – singerng
    Dec 2 '17 at 12:58
  • $\begingroup$ I want to use that fact as a motivation for why ordinals are what they are. $\endgroup$
    – singerng
    Dec 2 '17 at 13:10

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.