It seems we must use the fact that every well-ordered set is isomorphic to a unique ordinal, which depends on the axiom of replacement, to prove the existence of an uncountable well-order set. Can anyone provide an alternative proof?
[Math] How to prove there exists an uncountable well-ordered set without using axiom of replacement
set-theorywell-orders
Related Solutions
You have to distinguish between two things:
- A set can be well-ordered.
- A set with a natural linear ordering is well-ordered with that natural ordering.
The axiom of choice implies that every set can be well-ordered. But of course not every set which has a natural linear order is well-ordered. You don't need to venture to the real numbers. Both $\Bbb Z$ and $\Bbb Q$ have a natural linear order which is most definitely not well-ordered.
The point is that given a set of real numbers, if it is well-ordered in the usual ordering of the real numbers, then it is countable. We can prove this by choosing a canonical rational point from each interval between a point and its successor. This choice of rational numbers is not using the axiom of choice, since we can always choose a canonical rational number from an interval (e.g., represent each rational as $\frac pq$ where $p,q\in\Bbb Z$, $p>0$ and $\gcd(p,q)=1$; then consider the rational with the smallest $p$ possible in the interval, and find the one with the denominator closest to $0$ (the positive if both options exist) that match this numerator).
And the main confusion people have with the well-ordering theorem, is that if $X$ is a set which has a natural linear ordering, then there is absolutely no reason for any well-ordering to agree with the natural linear ordering. Much like how we can define well-orderings of $\Bbb N$ which disagree with the usual ordering, or how we can define a well-ordering of the rational numbers which certainly disagrees with their natural order.
(What is true, as you mention, is that we cannot specifically define a set of real numbers in the language of set theory such that $\sf ZF$ proves that this set is both uncountable and can be well-ordered. Namely, it is consistent with the failure of the axiom of choice that only countable sets of real numbers can be well-ordered.)
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.
Best Answer
Yes, we can prove the existence of an uncountable well-ordered set without Replacement.
In Z alone (= ZF without Replacement), we can prove the existence of the set $X$ of equivalence classes of well-orderings of $\omega$ modulo order-isomorphism. It's easy to prove that $X$ is uncountable; the only remaining task is to show that $X$ is well-ordered by "$[x]\triangleleft[y]$ iff $x$ order-embeds as an initial segment of $y$" (this relation is clearly well-defined).
It's worth taking a bit of care here, however: the linearly-ordered-ness of $X$ depends on the ability to compare well-orderings, and this is a accomplished via transfinite recursion, but often arguments via transfinite recursion rely on Replacement. This is a reasonable source of worry, but it turns out to not be an issue here: since the "target" of our recursion is a set already, we don't actually need Replacement (see Eric's comment below).
Let me sketch how we can prove that $X$ is linearly ordered by $\triangleleft$ without relying on Replacement:
Say that $\alpha:A\rightarrow B$ is an initial segment embedding (where $A, B$ are linear orders) if it is order-preserving and has range an initial segment of $B$ (possibly all of $B$). We can show without Replacement that if $A, B$ are well-orderings, then there is at most one initial segment embedding from $A$ to $B$. (Think about the least element of the domain on which the two embeddings disagree ...)
Now suppose $A, B$ are well-orderings of $\omega$ and there is no initial segment embedding of $B$ into $A$ (that is, $B\not\trianglelefteq A$); we want to show that there is an initial segment embedding of $A$ into $B$ with range a proper subset of $B$ (so $A\triangleleft B$).
Let $S$ be the set of $a\in A$ such that there is an initial segment embedding from $(a)_A:=\{a'\in A: a'\le_Aa\}$ to $B$. Each $a\in S$ corresponds to a unique element $\hat{a}$ in $B$ by the observation two bulletpoints above; it's easy to see that the (a priori partial) map $m:\alpha\mapsto\hat{\alpha}$ exists and is an initial segment embedding.
Note that $m$ can't be surjective; otherwise, inverting $m$ would give an initial segment embedding of $B$ into $A$.
Now suppose $dom(m)$ is not all of $A$. Let $s$ be the $A$-least element of $A\setminus S$ and (by the above bulletpoint) let $t$ be the $B$-least element of $B\setminus ran(m)$. Then we can extend $m$ to a strictly larger partial initial segment embedding by sending $s$ to $t$, which is a contradiction.
So $dom(m)=A$; that is, $A\triangleleft B$.
It now only remains to show that $X$ has no $\triangleleft$-descending sequences, but this proceeds exactly as usual.
So the existence of big ordinals is much murkier than the existence of big well-orderings (indeed, ZC doesn't even prove that $\omega+\omega$ exists!). You should think of ordinals as being "normal forms" of well-orderings: in general, we need Replacement to show that an arbitrary well-ordering has a normal form.