Showing that $\kappa^+ \leq 2^\kappa$ in ZF.

Question

I had a discission with one of my colleagues and he claimed that if $\kappa$ is an infinite cardinal number (aleph), then it is not possible to show that $\kappa^+ \leq 2^\kappa$ without axiom of choice. Buy I believe that it is not actually true. Here is my proof:

First, let ordinal $\alpha = h(\kappa)$ be Hartogs number of $\kappa$. Following the proof of existence of Hartogs numbers from the Wikipedia page (https://en.wikipedia.org/wiki/Hartogs_number), it is easy to see that there is injection from $\alpha$ into $2^{\kappa \times \kappa }$ (i.e. $|\alpha| \leq 2^{\kappa \times \kappa}$). AC is not used here.

Since $\kappa^+$ is the smallest cardinal such that there is no injection from it into $\kappa$, $\kappa^+ \leq \alpha$ as ordinals, and therefore $\kappa^+ \leq |\alpha| \leq 2^{\kappa \times \kappa}$ cardinality wise.

It is also can be shown without Axiom of Choice that $\kappa = \kappa \times \kappa$ for any aleph $\kappa$. Thus, $2^{\kappa \times \kappa} = 2^\kappa$, and $\kappa^+ \leq 2^\kappa$. All without AC.

Am I missing something? Thanks in advance!

Answer 1

it is easy to see that there is injection from $\alpha$ into $2^{\kappa\times\kappa}$

Actually, that's not correct: you cannot in fact get an injection from $h(\kappa)$ to $2^{\kappa\times\kappa}$ in $\mathsf{ZF}$ alone.

What you can do (and you mention this in the comments) is get a surjection the other way, but that doesn't give you an injection in the direction you want. In fact, the best $\mathsf{ZF}$ can do is the following: if there is a surjection from $X$ to $Y$, then there is an injection from $Y$ to $\mathcal{P}_{\not=\emptyset}(X)$ (send $y$ to the preimage of $y$ under a given surjection).

Interestingly, the exact strength of the statement "If there is a surjection $X\rightarrow Y$ then there is an injection $Y\rightarrow X$" is not known. It is called the partition principle (PP), and while it is known to be unprovable in $\mathsf{ZF}$ it is open in particular whether it is equivalent over $\mathsf{ZF}$ to the full axiom of choice. See Asaf Karagila's summary.

Answer 2

Just to complement Noah's answer with some garnished facts.

1. This is akin to the statement "countable union of countable sets is countable". It is suspiciously "obvious" that we can inject each countable set into $\{n\}\times\Bbb N$, for $n$ being the index in the enumeration of the whole family of sets, and that gives us an injection into $\Bbb{N\times N}$, which is easily countable.

   Alas, we falter in the same place here. These injections need to be chosen.

2. To finish the claim that it is indeed not provable that $\kappa^+$ injects into $2^\kappa$, just note that in Solovay's model this is the case. Indeed, if $\aleph_1<2^{\aleph_0}$ (at least in the presence of Dependent Choice) we get a set of reals which is non-measurable. Indeed, we also get a set of reals without the perfect set property (countable or contains a copy of the Cantor set). But since in Solovay's model we have that all sets of reals are Lebesgue measurable and have the perfect set property, we just can't have that.

3. Wait a minute, you are about to say, I've heard that Solovay's model requires large cardinals. And indeed it does. But, if we are willing to forego Dependent Choice, and introduce even more weirdness in the form of "there is a countable set of countable ordinals whose supremum is $\omega_1$", we can dispense of those large cardinal assumptions. This is the work of John Truss. Indeed, even before Solovay's work, Feferman and Levy produced a model in which $\Bbb R$ is a countable union of countable sets in which $\omega_1$ does not inject into $\Bbb R$ without any large cardinal assumptions.