# How to prove there exists an uncountable well-ordered set without using axiom of replacement

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?

• No: one can construct a model where replacement fails and there is no uncountable ordinal. It's actually pretty easy (think about some $V_\lambda$'s) – Max Jul 9 '18 at 14:32
• According to Wikipedia this is impossible. – Crostul Jul 9 '18 at 14:36
• One of you should post this as an answer. I'd upvote it, even if it can be found on Wikipedia; I didn't know about these $V_\lambda$ models for ZF minus replacement. – Lee Mosher Jul 9 '18 at 14:41
• @LeeMosher : but actually I just realized that $V_\lambda$ only answers "can we prove without relacement that there are uncountable ordinals ?", not the sape statement with "well-ordered set" instead of "ordinal". In fact for this second statement the answer is more subtle (and I'm not sure I know it) – Max Jul 9 '18 at 15:25
• @spaceisdarkgreen : yep, just realized this. But then the mention of ordinals in the question is rather odd – Max Jul 9 '18 at 15:28

## 4 Answers

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.

• I feel like your concern about the transfinite recursion is a little misplaced. More generally, Replacement is never needed to construct a (partial) function $f:A\to B$ by transfinite recursion where $A$ is a well-ordered set and $B$ is a set. The place where Replacement comes up is when you are trying to define a function on $A$ but you do not know that the codomain is a set yet. – Eric Wofsey Jul 9 '18 at 22:15
• @EricWofsey Yes, that wasn't very well written. I was trying to describe a reasonable source of worry, not saying that it was actually a problem; I've rephrased to make things clearer. – Noah Schweber Jul 10 '18 at 0:26

You don't need to mention ordinals to construct an uncountable well-ordered set. Say $S$ is the family of all well-orders of $\Bbb N$. Say two well-orders are equivalent if they are isomorphic, and consider the quotient $S/\sim$. Now show that given two elements of $S/\sim$, one is isomorphic to an initial segment of the other; use that to define a linear order on $S/\sim$, and it turns out that $S/\sim$ is an uncountable well ordered set.

I'm not going to assert that that does not use replacement, but I don't see how it does.

• Yes, replacement only comes into the picture if one tries to replace "well-ordered set" with "ordinal". – Andrés E. Caicedo Jul 9 '18 at 16:19

Despite the already existing answers, it may be worth mentioning that the answer to the question "can we prove that every well-ordered set is isomorphic to an ordinal without replacement ?" is no, as there are models of ZFC-replacement(=ZC) in which this theorem fails.

The easiest example is probably $V_\lambda$ for a countable limit ordinal $\lambda>\omega$. Indeed for such an ordinal, $V_\lambda$ is a model of Zermelo set theory (and choice if we've assumed choice), but not of replacement.

Moreover, the ordinals of $V_\lambda$ are precisely the ordinals $<\lambda$, and for a countable $\lambda$, they are all countable (even in $V_\lambda$: it's easy to check that a bijection between $\alpha<\lambda$ and $\omega$ is in $V_\lambda$). Hence $V_\lambda$ is a model of Z and "there are no uncountable ordinals".

Taking $\lambda=\omega+\omega$ proves the claim of Noah Schweber that we can't even prove that $\omega+\omega$ exists without replacement.

However, the question of whether there are uncountable well-ordered sets without replacement is more subtle.

The answer to that uses the fact that we can "model" $\omega_1$ even without having access to it, because we know what it is : it's the set of countable ordinals. That's what Noah Schweber and David C.Ulrich showed in their answers (note that their answers can easily be extended to an arbitrary set $X$, showing the "weak" version of Hartog's theorem : for any set $X$, there is a well-orderes set $O$ with no injection $O\to X$)

As is explained above, Hartogs' 1915 construction shows that Z (= ZF minus Replacement) proves that a well-ordering of type $$\omega_1$$ (which is just an uncountable well-ordering all of whose proper initials are countable) exists. (In fact, the well-ordering is one of a subset of $$P(P(\omega))$$, i.e., it well-orders sets of reals.)

This construction can be iterated any finite number of times, proving in Z: for every $$n\in\omega$$, there exists a well-ordering of type $$\omega_n$$ (that is to say, ...). However, without Replacement, this is as far as it goes, as is illustrated by a natural model $$V_{\omega+\omega}$$ that satiesfies GCH.

• It's such an old post... Anyway, thanks for your contribution. Keep it up. – YuiTo Cheng Feb 16 at 1:28