My question, please, relates to a proof that: Every Well-ordered Set is Isomorphic to a Unique Ordinal and the use of the Axiom of Replacement in it.

The proof begins letting $S$ be a well-ordered set. It then defines a set

$T=\{x\in S:\text{there exists an ordinal $\alpha$ such that $\alpha\cong S_x$}\}$

It then claims that for each $x\in S$, the ordinal $\alpha$ is unique by a prior result that no two distinct ordinals can be isomorphic as well-ordered sets.

Then by virtue of the Axiom of Replacement, the following is determined to be a set:

$\{\alpha:\text{$\alpha$ is an ordinal and there exists an $x\in S$ with $\alpha\cong S_x$}\}$

which it then goes on to show is an ordinal itself. And the proof proceeds on that basis once this is established.

My question is:

Why could you not just start with the second set to begin with, rather than define $T$ and invoke the Axiom of Replacement?


  • 3
    $\begingroup$ how would you propose to prove it is a set? $\endgroup$ – spaceisdarkgreen Aug 20 '17 at 21:29
  • 1
    $\begingroup$ The collection of all ordinals is not a set, so the second isn't a valid definition of a set. The existence of this collection as a set is due to replacement. $\endgroup$ – Thomas Andrews Aug 20 '17 at 21:34
  • $\begingroup$ @ThomasAndrews Thanks. Is that Burali-Forte? $\endgroup$ – user12802 Aug 20 '17 at 21:53

The key problem in the absence of the axiom of replacement is that there may be well-ordered sets $S$ that are too large in the sense that they are longer than any ordinal. In that case, the collection of ordinals isomorphic to an initial segment of $S$ would be the class of all ordinals, which is not a set.

For example, with $\omega$ denoting as usual the first infinite ordinal, consider the set $V_{\omega+\omega}$. Recall that $V_0=\emptyset$, $V_{\alpha+1}=\mathcal P(V_\alpha)$ and $V_\lambda=\bigcup_{\beta<\lambda}V_\beta$ for all ordinals $\alpha$ and all limit ordinals $\lambda$. The set $V_{\omega+\omega}$ is a model of all axioms of set theory, except for the axiom of replacement. And indeed the theorem that every well-ordered set is isomorphic to an ordinal fails badly here: The ordinals in this model are precisely the ordinals smaller than $\omega+\omega$. However, all well-orderings of $\omega$ belong to $V_{\omega+\omega}$, and many are much longer than this bound (and much more is true, as $V_{\omega+\omega}$ contains plenty of uncountable well-orderings as well).

In this model, if you take as $S$ a well-ordering of $\omega$ of type $\omega+\omega$, then $T=S$, as each proper initial segment of $S$ has order type isomorphic to an ordinal smaller than $\omega+\omega$. However, the collection of ordinals isomorphic to an initial segment of $S$ is all of $\omega+\omega$, which is not a set from the point of view of the model. (And note that there is nothing difficult about finding an $S$ as indicated: Consider for instance the ordering of $\mathbb N$ where the odds and the evens are ordered as usual, but we make every odd number larger than every even number. To get a larger order-type, simply add an extra point on top of all of these.)

Of course, by taking as $S$ something longer, the problem is highlighted even more: Now $T$ is not all of $S$, and the collection of ordinals isomorphic to an initial segment of $S$ is again the class of all ordinals ($\omega+\omega$, in this case).

Maybe this illustrates how replacement avoids this problem: Suppose replacement holds (together with the other axioms) and we know that all ordinals smaller than $\omega+\omega$ "exist" (i.e., are sets). If $S$ is a well-ordered set of type $\omega+\omega$, then $\omega+\omega$ is the collection of ordinals isomorphic to a proper initial segment of $S$. Since $S$ is a set, then $T$ (which is a subclass of $S$) is also a set (in the case being discussed, $T=S$, of course). We know that each member $x$ of $T$ corresponds to a unique ordinal (i.e., there is a unique ordinal isomorphic to the initial segment of $S$ determined by $x$). By replacement, this means that the collection of all these ordinals is a set (it is the image of the set $T$ under the function mapping $x$ to the ordinal $S_x$ is isomorphic to). That is, $\omega+\omega$ exists as well.

If you examine the proof of the theorem you will see that the argument is essentially inductive: You go bit by bit ensuring that all initial segments of $S$, including $S$ itself, correspond to some ordinal. The proof, however, is usually not organized as an induction. Rather, you start with $S$ that is well-ordered. You extract $T$ from $S$ and note it is a (not necessarily proper) initial segment of $S$. You use replacement to conclude that there is a set of ordinals associated to $T$ as indicated. You argue that since $T$ is an initial segment of $S$, then this set of ordinals is also an ordinal, call it $\alpha_T$, which leads you to the conclusion that $T$ is order isomorphic to $\alpha_T$. Now you conclude that $T$ is indeed $S$, and you are done. The point is that if $T$ is not $S$, then $T=S_y$ for a unique $y\in S$, and we just proved that $S_y$ is order isomorphic to an ordinal, namely $\alpha_T$, so $y$ would have been in $T$ as well, and we get a contradiction.

| cite | improve this answer | |
  • $\begingroup$ Thanks - a work of art to be studied. $\endgroup$ – user12802 Aug 21 '17 at 15:02
  • $\begingroup$ My pleasure. Best regards, $\endgroup$ – user12802 Aug 23 '17 at 23:28
  • $\begingroup$ Dear Professor - I was so irked (euphemism) that this answer received a downvote that I wanted to give it an additional bounty. I even flagged the moderators, but they really can't do anything about downvotes. I was waiting to accumulate a few more points which I now have. Being a bit confused by the system when I tried to do it here, I offered it to another otherwise worthy answer amongst your many. While I have strong feelings about stealth downvotes without any substantiation, I am especially adamant when it comes to esteemed participants such as yourself as they can only serve as (cont.) $\endgroup$ – user12802 Aug 31 '17 at 13:46
  • $\begingroup$ discouragement, much to the detriment of users such as myself. $\endgroup$ – user12802 Aug 31 '17 at 13:50
  • $\begingroup$ Dear @Andrew, many thanks. Don't worry much about the downvotes, they tend not to mean much. Your appreciation more than compensates such things. $\endgroup$ – Andrés E. Caicedo Aug 31 '17 at 13:55

Andrés Caicedo's answer nicely describes the broader context of what's going on here, but he did not actually identify what is wrong with what you propose on a very basic level. You ask why we cannot just take the set $$X=\{\alpha:\text{$\alpha$ is an ordinal and there exists an $x\in S$ with $\alpha\cong S_x$}\}$$ to begin with. The answer is that not every collection is a set! You have to prove that any set you want to refer to exists, using only the axioms of ZFC (or whatever other axiomatic system you are working with). So somehow or other, you are going to need to prove that there exists a set $X$ whose elements are exactly the ordinals $\alpha$ such that there exists an $x\in S$ with $\alpha\cong S_x$. If you want to do this without first showing the set $T$ exists and then using Replacement, the burden is on you to describe how you would prove that this set $X$ exists by some other means.

You might ask why the argument using $T$ does not face this same issue: how do you know that $T$ is a set? But that is easy to justify: $T$ is defined as the set of elements of $S$ satisfying a certain condition, and since $S$ is a set we can use Separation to say that $T$ is a set. This method is unavailable for proving $T$ is a set, since there is no obvious set we already know exists which $T$ is a subset of.

| cite | improve this answer | |
  • $\begingroup$ Thanks for taking the time to provide such a nice, lucid explanation. With regards, $\endgroup$ – user12802 Sep 3 '17 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy