Which sets are well-orderable without Axiom of Choice?

Question

I know that, assuming Axiom of Choice, every set is well-orderable. I know also that the assertion that $\mathbb{R}$ is NOT well-orderable is consistent with ZF. How can I find other sets such that, in ZF, I can't prove their well-orderability? For example, which elements of Von Neumann Hierarchy

$V_0 = \emptyset \\ V_{\alpha+1}=P(V_{\alpha}) \\ V_\lambda = \cup_{\alpha<\lambda} V_\alpha $

(except $V_n$ for $n$ finite ordinal, and $V_\omega$ ) can be well-ordered?

Answer 1

It is consistent that $V_{\omega + 1}$ that is not well-orderable.

$\omega \subset V_\omega$. So $\mathscr{P}(\omega) \subseteq P(V_\omega) = V_{\omega + 1}$. So if $V_{\omega + 1}$ could be well ordered, then $\mathscr{P}(\omega) = 2^\omega$ could be well-ordered. As you mentioned $\mathbb{R}$ which is isomorphic can be not well orderable..

As $V_\alpha \subseteq V_\beta$ for $\alpha < \beta$. Thus it is consistent that all $V_\alpha$ for $\alpha \geq \omega + 1$ are not well-orderable.

Answer 2

It's somewhat difficult to give a complete characterization, for several reasons.

1. $L$ is well-ordered, in fact $\rm HOD$ is well-ordered, so every subset of these models is always well-ordered. Since both of these are models of $\sf ZFC$ it guarantees that it's not as simple as you'd like it to be.

2. If $V$ is a model of $\sf ZF+\lnot AC$ and $M$ is an inner model satisfying $\sf AC$ then there is a set of ordinals in $V\setminus M$. So models disagreeing on the truth of $\sf AC$ will also disagree on the sets of ordinals. But given such set $A$, if we consider $M[A]$ it is still a model of $\sf ZFC$. So just by considering sets of ordinals we know that there is a difference, but it's hard to estimate it.

3. As you and William both note, it's consistent that $\Bbb R$ cannot be well-ordered. By a quick calculation, $|\Bbb R|=|V_{\omega+1}|$. Therefore in such model no $V_\alpha$ for $\alpha>\omega$ can be well-ordered. And we can using forcing and symmetric models ensure that the least non-well orderable $\alpha$ is pretty much anything.

4. If $V$ is a model of $\sf ZF$, then for every $x\in V$ there is a generic extension of $V$ such that $x$ can be well-ordered in that extension (e.g. making $x$ countable), so being non well-orderable is not absolute between models, and we cannot really talk about sets which "absolutely cannot be well-ordered".

If we combine the last two points, we get that we can mess the axiom of choice in so many ways, and we can control these ways relatively easily and nicely (especially if all we want is violation of choice, and not some stronger properties a-la determinacy). Pretty much anything goes.