Proof that each well ordered set is similar to a unique ordinal number (according to Halmos)

Question

I'm trying to follow the proof that is given in the "Naive Set Theory" by Halmos that each well ordered set is similar to a unique ordinal number (which Halmos calls the Counting Theorem):

Counting Theorem. Each well ordered set is similar to a unique ordinal number.

Since for ordinal numbers similarity is the same as equality, uniqueness is obvious. Suppose now that $X$ is a well ordered set and suppose that an element $a$ of $X$ is such that the initial segment determined by each predecessor of $a$ is similar to some (necessarily unique) ordinal number. If $S(x, \alpha)$ is the sentence that says "$\alpha$ is an ordinal number and $s(x)$ is similar to $\alpha$", then, for each $x$ in $s(a)$, the set $\{\alpha: S(x, \alpha)\}$ can be formed; in fact, that set is a singleton. The axiom of substitution implies the existence of a set consisting exactly of the ordinal numbers similar to the initial segments determined by the predecessors of $a$. It follows, whether $a$ is the immediate successor of one of its predecessors or the supremum of them all, that $s(a)$ is similar to an ordinal number. This argument prepares the way for an application of the prinicple of transfinite induction; the conclusion is that each initial segment in $X$ is similar to some ordinal number. This fact, in turn, justifies another application of the axiom of substitution, just like the one made above; the final conclusion is, as desired, that $X$ is similar to some ordinal number.

I cannot understand what is the justification of the step: "It follows, whether $a$ is the immediate successor of one of its predecessors or the supremum of them all, that $s(a)$ is similar to an ordinal number."

I understand the construction of the set $\{\alpha: S(x, \alpha)\}$, but I only see that each element of that set is an ordinal number which is similar to some of the initial segments of $s(a)$. I also see that they are ordered by continuation (but so is any set of ordered numbers). From the step that puzzles me, I expect that the said set has to be an ordinal number, or at least to be similar to an ordinal number, but I can't see how this can be shown (or how this can be obvious).

PS. As far as I know, some of the terms that Halmos uses have modern equivalents: similar = order-isomorphic Axiom of Substitution = Axiom of Replacement

Halmos also has proven a fact hat every set of ordinal numbers has a supremum in the text just before that. This might be helpful, as $\{\alpha: S(x, \alpha)\}$ is definitely a set of ordinal numbers. So it must have a supremum, but what is it to do next, I don't understand.

UPDATE

After asking the question I think I pinpointed the part which is difficult to me.

Halmos asserts the fact that $s(a)$ is similar to an ordered number whether $a$ is the immediate successor of one of its predecessors, or the supremum of them.

In case $a$ is the immediate successor, it's easy to see that $s(a)$ is similar to some ordered number. There should be some $b \in s(a)$ such that $a$ is the immediate successor of $b$. Then $s(b)$ is similar to some ordinal number, say $\beta$ and $s(a)$ is similar to $\beta^+$. But I don't understand how to show the same if $a$ is the supremum of $s(a)$.

Answer 1

I prefer the following development, which is done in ZF minus the axioms of Infinity and Foundation (a.k.a. Regularity):

(1). Well-Orders. For a well-order $<$ on a set $A$ we define an initial segment of $A$ as $\{b\in A: b<a\}$ for some (any) $a\in A.$ And write $pred_< a=\{b\in A: b<a\}.$ ("pred" for predecessors).

(1.1). The only isomorphism of a well-order to itself is the identity.

(1.2). There is at most one isomorphism from one well-order to another.

(1.3) A well-order is not isomorphic to an initial segment of itself.

(1.4). Distinct initial segments are not isomorphic to each other.

(1.5). The Main Theorem. Trichotomy.

For any well-orders $A, B$ exactly one of the following is true:

(i). $A$ is isomorphic to $B.$

(ii). $A$ is isomorphic to an initial segment of $B.$

(iii). $B$ is isomorphic to an initial segment of $A.$

Proof of (1.5): Let $<_A, <_B$ be the well-ordering relations on $A, B$ respectively. Let $A^*$ be the set of those $a\in A$ for which there is an isomorphism $f_a:pred_{<_A}\to pred_{<_B}b$ for some $b\in B.$

(i'). By (1.3), $b$ is unique, and by that and (1.2), $f_a$ is unique. So let $g(a)=b$ (By Replacement applied to $A^*$). So for $a\in A^*,$ we have $f_a:pred_{<_A}\to pred_{<_B}g(a).$

(ii'). Let $a\in A^*$ and $a'<_A a.$ The restriction of $f_a$ to $pred_{<_A}a'$ is an isomorphism to an initial segment $pred_{<_B}b'$ of $B,$ so $a'\in A^*.$ Also, by (i') and (1.3) and (1.2) we have $b'=g(a')$ and the restriction of $f_a$ to $pred_{<_A}a'$ is $f_{a'}.$ It should be clear that $g(a')<_B g(a).$

Furthermore, if $b''<_B g(a)$ then because $f_a$ is an isomorphism, the set $(f_a)^{-1}pred_{<_B}b''$ is equal to $pred_{<_A}a''$ for some $a''\le_A a,$ so $b''=g(a'').$

So $A^*$ is either $A$ or an initial segment of $A,$ and the set $G=\{g(a):a\in A^*\}$ is either $B$ or is an initial segment of $B,$ and $g:A^*\to G$ is an isomorphism.

(iii'). (Case One). If $A^*=A$ then (i) or (ii) of the Theorem is true,but not both, by (1.3). And (iii) cannot be true because if $h$ was an isomorphism of $B$ to an initial segment of $A$ then $(h|_G)\circ g$ would be an isomorphism from $A$ to an initial segment of $A,$ contrary to (1.3).

(iv'). (Case Two). If $A^*=pred_{<_A}\alpha$ then $G=B.$ Otherwise, if $G=pred_{<_B}\beta,$ then $g:pred_{<_A}\alpha\to pred_{<_B}\beta$ is an isomorphism. But then the definition of $A^*$ implies $\alpha \in A^*,$ which is absurd because $A^*=pred_{<_A}\alpha.$

So if $A^*$ is an initial segment of $A$ then (iii) of the Theorem is true, and by applications of (1.3), (i) and (ii) are false.

(2). Ordinals. Let $<_A$ be a well-order on $A .$ To prove $A$ is isomorphic to an ordinal:

Case I: If there exists ordinal $B$ such that (i) holds, we are done.

Case II: If there exits ordinal $B$ such that (ii) holds, then since an initial segment of an ordinal is also an ordinal, we are done.

Case III. If cases I and II never hold then (iii) holds for every $B\in On$ (every ordinal $B$). Now for any $a\in A$ the set $pred_{<_A}a$ is isomorphic to at most one $B\in On$ by (1.3) because if $B,B'$ are distinct ordinals then one of them is an initial segmnt of the other. So for $a\in A$ let $h(a)=B$ if $pred_{<_A}a$ is isomorphic to $B\in On,$ and $h(a)=\emptyset$ otherwise. By Replacement the set $\{h(a):a\in A\}=On$ exists, but this is impossible. So Case I or Case II must apply and we are done.

(3).Remarks.

(3a). Lemmas (1.1),(1.2), (1.3) and (1.4) are easy to prove by contradiction. E.g. for (1.1) suppose $f:A\to A$ is an isomorphism and $a_0$ is the least $a\in A$ such that $f(a)\ne a.$ And we use (1.1) to prove (1.2). For (1.3) suppose $f:A\to pred_<a$ is an isomorphism . Then $f(a)<a,$ so consider the least $\alpha \in A$ such that $f(\alpha)\ne \alpha$.....Let me know if you need help with them.

(3b). Remember that in the language of Set Theory in use here, $B\in On$ does not assert there exists a set $On$. It is an abbreviation for "$\forall b\in B\,(b\subset B),$ and $B$ is well-ordered by $\in$".

Answer 2

I am going to give my attempt at completing the proof even though it is in many respects similar to the one given by @Kevin Osborn.

---

Let $(W,\leq)$ be a well-ordered set, then we claim that there exists a unique ordinal number $\alpha$ such that $W \cong \alpha$.

Proof: First of all notice that if a well-ordered set is similar to an ordinal number then this must be unique because similarity and equality are the same thing for ordinal numbers. Now, define $$ S \equiv \{x \in W: \exists \alpha_x \text{ ordinal number}: s(x) \cong \alpha_x\} $$ and suppose that $s(x) \subseteq S$. Let $s(y,\alpha)$ be the sentence "$y \in s(x)$, $\alpha$ is an ordinal number, $s(y) \cong \alpha$" so that $\forall y \in s(x)$ we can construct the set $\{\alpha:S(y,\alpha)\}$ which is just $\{\alpha_y\}$ (a singleton by what we said before on uniqueness). The Axiom of Substitution then states that there exists a function $F$ with domain $s(x)$ such that $\forall y \in s(x), F(y) = \{\alpha_y\}$, therefore consider the set $\alpha_x \equiv \bigcup \text{ran}(F)$ which only consists of ordinal numbers and thus it is well-ordered by the relation of belonging. We claim that $\alpha_x$ is also an ordinal number. Indeed, fix an arbitrary element of $\alpha_x$, i.e. $\alpha_y$ for some $y \in s(x)$, then we just need to show that $\alpha_y \subseteq s(\alpha_y)$, since surely $s(\alpha_y) \subseteq \alpha_y$, where $s(\alpha_y)$ is the initial segment determined by $\alpha_y$ in $\alpha_x$. Suppose $\beta \in \alpha_y$ then, since $\beta = s(\beta)$ (initial segment in $\alpha_y$), $\beta$ is similar to an initial segment of $s(y)$ which is just an initial segment of $s(x)$ determined by some element $z$ so that $\beta \cong s(z)$ and thus $\beta \in \alpha_x$. Finally, $\alpha_x$ and $s(x)$ are both well-ordered, hence, by the Comparability Theorem for well-ordered sets, exactly one of the following three options must be true:

1. $s(x)$ is similar to an initial segment of $\alpha_x$
2. $\alpha_x$ is similar to an initial segment of $s(x)$
3. $s(x) \cong \alpha_x$

Clearly 1 and 2 can not hold for otherwise we would have that a well-ordered set is similar to one of its initial segments, therefore only 3 holds and it tells us that $s(x)$ is similar to an ordinal number. By transfinite induction we have shown that $\forall x \in W, x \in S$. Now we just need to repeat the exact procedure to show that $W$ is similar to an ordinal number: first we define the sentence $p(x,\alpha)$ as "$x \in W$, $\alpha$ is an ordinal number, $s(x) \cong \alpha$", then we apply the Axiom of Substitution using the previously proved result and finally the union of the range of the function thus obtained is the desired ordinal number. $\square$

Answer 3

Been reading this book to fill some knowledge gaps on set theory, so here's my solution (taking uniqueness of ordinal equivalence for granted):

Claim: Suppose that $X$ is a well-ordered set such that every initial segment of $X$ is similar to an ordinal number. Then $X$ is itself similar to an ordinal number.

Proof: For any $x \in X$, we know that there exists an ordinal number similar to $x$ by hypothesis; the singleton set containing this ordinal is then precisely the set $\{ \alpha : \alpha \text{ is an ordinal and } \alpha \cong s(x) \}$ by uniqueness of ordinal similarity. By the axiom of substitution, there exists a function $F$ with domain $X$ such that $F(x)$ is the aforementioned set for each $x \in X$. Since each element $F(x)$ is a (non-empty) singleton set, we can form the unique function $f$ of domain $X$ satisfying $F(x) = \{ f(x) \}$ (i.e. $f$ removes the curly braces from the result of $F$). The result is a function $f$ with the property that, for all $x \in X$, $f(x)$ is an ordinal and $f(x) \cong s(x)$.

Denote by $S$ the range of $f$. We claim that $S$ is an ordinal. As established, $S$ is a set of ordinals, so it is well ordered under set inclusion/membership. Suppose now that $\alpha \in S$. The initial segment of $\alpha$ in $S$ is included in $\alpha$ by definition; it remains to be shown that every element of $\alpha$ is included in $S$ (and therefore also in its initial segment). Suppose $\beta \in \alpha$. Then if $\alpha$ is the image of $x \in X$, it is similar to $s(x)$, say through the similarity $\varphi$. Now it is easy to show that $\varphi$ restricts over the initial segment of $\beta$ in $\alpha$ to a similarity. Noting that $\varphi(s(\beta)) = s(\varphi(\beta))$ as a consequence of the fact that $\varphi$ is a similarity, $\left.\varphi\right|_{s(\beta)}$ is a similarity between $s(\beta) = \beta$ (taking $\beta \in \alpha$, an ordinal) and $s(\varphi(\beta))$. Since $\varphi(\beta) \in s(x) \subseteq X$, we have $\beta \in S$ as desired.

Now the sets $X$ and $S$ are each well-ordered, and so there are three cases. If they are similar, we are done. If $X$ is similar to an initial segment of $S$, then since an initial segment of an ordinal is again an ordinal, we are done. Finally, suppose $S$ is similar to an initial segment $s(x)$ of $X$. We then have that $s(x)$ is similar to the ordinals $f(x)$ and $S$, so that $f(x) \cong S \implies f(x) = S$. However, $f$ has range $S$, so $f(x) \in S \implies f(x) \in f(x) \implies f(x) < f(x)$, a contradiction. $\blacksquare$

Now the proof in the book goes as follows:

Since for the ordinal numbers similarity is the same as equality, uniqueness is obvious. Suppose now that $X$ is a well ordered set and suppose that an element $a$ of $X$ is such that the initial segment determined by each predecessor of $a$ is similar to some (necessarily unique) ordinal number. By the claim, $s(a)$ itself is then similar to some ordinal number. Applying transfinite induction, all of the initial segments of $X$ are similar to some ordinal number. Applying the claim now to $X$, $X$ itself is similar to some ordinal number.

I still unfortunately can not answer what the hell the author intended with the phrase "whether $a$ is the immediate successor of one of its predecessors or the supremum of them all, that $s(a)$ is similar to an ordinal number."