Well ordering of $\mathbb{R}$ in ZF

Question

I am solving a problem about a certain set $S$(which exists in ZF and ZFC) where I have to show that it is countable. I know that $|S|\le|\mathbb{R}|$ so I assume by way of contradiction that there is a bijection between them. I can then prove that $S$ is well ordered, lets say by some ordering $\prec$. I claim this is a contradiction because, say $f: \mathbb{R}\leftrightarrow S$ is a bijection, then $x<y\iff f(x)\prec f(y)$ is a well ordering of $\mathbb{R}$(where the LHS is the proposed well ordering of $\mathbb{R}$). Have I solved this problem in ZF, but not in ZFC?

Sidenote: I have been intentionally vague about $S$ because I just want to know if my conclusion is valid. There are tonnes of questions on here e.g., but they either go over my head or don't give a straight answer to my question above.

EDIT: Following the previous proof, suppose $S\lt|\mathbb{R}|$ but is still uncountable. The construction of $S$ does not require choice, so this would be a contradiction to the fact that the contiuum hypothesis is unprovable in ZF.

Answer 1

You have definitely not solved the problem in ZF.

This is because there is no way in ZF to prove that $\mathbb{R}$ is not well-ordered (assuming ZF is consistent). For if we could prove in ZF that $\mathbb{R}$ is not well-ordered, then we could disprove the axiom of choice in ZF and thus ZFC would be inconsistent.

Furthermore, even if you showed that $S$ is not in bijection with $\mathbb{R}$, that still would not show that $S$ is countable. You are implicitly relying on the continuum hypothesis, which states that every subset of $\mathbb{R}$ not in bijection with $\mathbb{R}$ is countable. But the continuum hypothesis also cannot be proved in ZF (in fact, cannot be proved in ZFC).

As mentioned in the comments, you are confusing proof and truth. There are three possibilities:

1. In all models of ZF, $S$ is countable. In this case, you can prove $S$ is countable in ZF.
2. In all models of ZF, $S$ is not countable. In this case, you can prove $S$ is uncountable in ZF.
3. $S$ is countable in some models of ZF but not in others. In this case, you can neither prove nor disprove that $S$ is countable in ZF.

Note that if you can prove $S$ is (un)countable in ZF, that exact proof is also a proof that $S$ is (un)countable in ZFC. So it doesn't make any sense to "[solve] this problem in ZF, but not in ZFC".

Answer 2

As Mark Saving says, you have not in fact proved the relevant claim. However, there is indeed a way we can leverage the fact that $\mathsf{ZF}\not\vdash$ "$\mathbb{R}$ can be well-ordered" to prove something - it's just that the thing(s) we get out of it are a bit more technical.

Specifically, suppose I have a (definition of a) set $S$ and $\mathsf{ZF}$ proves that $(i)$ $\vert S\vert\le\vert\mathbb{R}\vert$ and $(ii)$ $S$ can be well-ordered. Then $\vert S\vert=\vert\mathbb{R}\vert$ is inconsistent (over $\mathsf{ZF}$) with "$\mathbb{R}$ cannot be well-ordered" - and so we have a proof of $\vert S\vert<\vert\mathbb{R}\vert$ in the theory $\mathsf{ZF}$ + "$\mathbb{R}$ cannot be well-ordered." But note that this falls short of a $\mathsf{ZF}$-proof, or even a $\mathsf{ZFC}$-proof, of $\vert S\vert<\vert\mathbb{R}\vert$.

The most we can say about what $\mathsf{ZF}$ can prove about $\vert S\vert$ is the following: if $\mathsf{ZF}$ is consistent in the first place, then $\mathsf{ZF}\not\vdash\vert S\vert=\vert\mathbb{R}\vert$. This is because if $\mathsf{ZF}\vdash\vert S\vert=\vert\mathbb{R}\vert$ then per the above $\mathsf{ZF}$ + "$\mathbb{R}$ cannot be well-ordered" is inconsistent, but we know that this latter theory is consistent if $\mathsf{ZF}$ itself is. But again, this is far from a proof in $\mathsf{ZF}$ or even $\mathsf{ZFC}$ that $\vert S\vert<\vert\mathbb{R}\vert$.

---

That said, it is quite possible that your $\mathsf{ZF}$-proof that $S$ can be well-ordered (if in fact correct) can be modified to give a $\mathsf{ZF}$-proof that $\vert S\vert<\vert\mathbb{R}\vert$, so it's not worth abandoning without further consideration.