How big is the smallest not well-orderable set in $\mathsf{ZF}$?

Question

I know that $\mathsf{ZF}$ alone (i.e., without the Axiom of Choice) cannot prove (nor disprove) that $\Bbb R$ can be well-ordered. Then again, without the Continuum Hypothesis, we cannot know whether there exist any cardinalities between $\aleph_0$ and $|\Bbb R|=2^{\aleph_0}$. So I wonder:

• Is it consistent with $\mathsf{ZF}$ that every well-orderable set is countable?
• If not: How high in cardinalities can we go and still well-order without choice? How much higher with some typical "mild" forms of Choice?

Answer 1

Construction of $\omega_1$, the set of all countable ordinals, can be done in ZF. It is well-ordered and uncountable (proved in ZF).

I guess a Dedekind finite (but not finite) set is not well-orderable. So "how high in cardinalities" would you consider it to be?

Answer 2

No, it is not consistent that in ZF, every well-ordered set is countable. Consider the set $K = \{(S, <) \mid S \in P(\mathbb{N}), <$ is a well-order on $S\}$.

Then for each $(S, <) \in K$, there is a unique ordinal which is order-isomorphic to it. So consider $O = \{x$ an ordinal: $x$ is order-isomorphic to $(S, <)$ for some $(S, <) \in K\}$, which exists by the axiom of replacement.

$O$ is the set of all countable ordinals. If all ordinals were countable, then $O$ would be the set of all ordinals. But this is a contradiction.

For any ordinal $\kappa$, it's possible to form an ordinal $\kappa'$ with greater cardinality even in ZF by essentially repeating the same argument and replacing $\mathbb{N}$ with $\kappa$. So there is no "greatest ordinal up to cardinality" in ZF.

Answer 3

Expanding on Mark Saving's answer, we can prove in $\mathsf{ZF}$ alone that for every set $X$ there is an ordinal onto which $X$ does not surject. So not only is there no largest well-orderable cardinality, the well-orderable cardinalities are unbounded in a stronger sense.

On the other hand, we can always make the first failure of choice happen as high up as we want. Formally, if $M$ is a countable model of $\mathsf{ZFC}$ and $\alpha$ is an ordinal in $M$, there is a symmetric extension $N\supset M$ such that every set of $N$-rank $<\alpha$ is well-orderable in $N$ but $N\models\neg\mathsf{AC}$.