5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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) $\endgroup$ – Max Jul 9 '18 at 14:32
  • $\begingroup$ According to Wikipedia this is impossible. $\endgroup$ – Crostul Jul 9 '18 at 14:36
  • $\begingroup$ 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. $\endgroup$ – Lee Mosher Jul 9 '18 at 14:41
  • 2
    $\begingroup$ @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) $\endgroup$ – Max Jul 9 '18 at 15:25
  • $\begingroup$ @spaceisdarkgreen : yep, just realized this. But then the mention of ordinals in the question is rather odd $\endgroup$ – Max Jul 9 '18 at 15:28
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Jul 9 '18 at 22:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Jul 10 '18 at 0:26
6
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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.

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

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.