Without AC, it is consistent that there is a function with domain $\mathbb{R}$ whose range has cardinality strictly larger than that of $\mathbb{R}$?

I stumbled across this question earlier, and the top comment on the bottom answer asserts two claims: Without the Axiom of Choice,

• It is consistent that there exists a function with domain $\mathbb{R}$ whose range has cardinality strictly larger than that of $\mathbb{R}$.
• It is consistent that there exist surjective maps $X\to Y$ but $|X|$ and $|Y|$ are incomparable.

I haven't studied set theory in years, but I find both these claims surprising and intriguing. I couldn't find any mention or proof of these facts online. Does anybody have a proof or reference to either of these? Thanks.

Solution 1:

As Brian remarks, this is not quite right. And it's not quite what I said there.

Without the axiom of choice it is still consistent (read: possible) that $\Bbb R$ is well-orderable, in which case the usual theorems that assume choice hold. It is possible that the axiom of choice fails so far away from the "usual" sets, so for all practical purpose we can assume that the axiom of choice is true.

But it is also possible that the axiom of choice fails pretty bad at the real numbers. And here are some examples.

1. There are models where $\aleph_1\nleq|\Bbb R|$. Namely there is no injective function from $\omega_1$ into $\Bbb R$. Examples for such models are the Solovay model, Feferman-Levy model, Truss models, Gitik's model, and very naturally in models of $\sf AD$.

   But it is true that $\Bbb R$ can always be mapped onto $\omega_1$ (and in the case $\aleph_1\nleq|\Bbb R|$ these are incomparable), and by considering such a surjection from $[0,1]$ onto $\omega_1$, and mapping the rest of the real numbers to themselves we have a map from $\Bbb R$ onto a set of size $\aleph_1+2^{\aleph_0}$, which here is strictly larger than $2^{\aleph_0}$.

2. It is consistent to have a set which can be partitioned into countably many pairs, but have no countably infinite subset. This sort of set can be mapped onto $\Bbb N$, but of course those sets are incomparable in their cardinality.

   Here is an example of the second case. The canonical model with such example is Cohen's second model where the axiom of choice fails.

Now these are consistency results. We can't quite prove them from the failure of $\sf AC$. The first one is obvious, as I remarked, the axiom of choice might fail and the real numbers behave as usual. In that case the first example is invalid, of course.

But what about the second case? Well, we can prove from the failure of $\sf AC$ that there are two cardinals which are incomparable with respect to the orders of injections, and the orders of surjections. But now consider the following statement:

The Partition Principle. If there is a surjection from $X$ onto $Y$, then there is an injection from $Y$ into $X$.

If the partition principle holds, then the second example you are looking for is impossible. If there is a surjection from $X$ onto $Y$, then they are comparable. This principle is easily provable from the axiom of choice, but we don't know whether or not it implies the axiom of choice itself. This is one of the oldest open problems of set theory. If this principle fails, then this means that there is an example for the second question, but we don't know if the failure of choice implies the failure of this principle as well.