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!

  • $\begingroup$ "it is easy to see that there is injection from $\alpha$ [i]nto $2^{\kappa\times\kappa}$." I don't think that's true. There is an injection from $\alpha$ into $2^{(2^{\kappa\times\kappa})}$, but that's different. $\endgroup$ Apr 25, 2022 at 0:52
  • $\begingroup$ How is $\kappa^+$ defined in the absence of choice? $\endgroup$ Apr 25, 2022 at 1:05
  • 1
    $\begingroup$ @MarkSaving Choice isn't needed to define $\kappa^+$ - it's the smallest ordinal not injectible into $\kappa$. $\endgroup$ Apr 25, 2022 at 1:11
  • $\begingroup$ @NoahSchweber Can you help me to see why we need to take power set once more time? It seems like we take well ordering, an element of $2^{\kappa \times \kappa}$, and map it to the corresponding ordinal. $\endgroup$
    – Gleb Chili
    Apr 25, 2022 at 1:20
  • 1
    $\begingroup$ @GlebChili That gives a surjection from $2^{\kappa\times\kappa}$ to $\alpha$, not an injection from $\alpha$ to $2^{\kappa\times\kappa}$. The ability to turn surjections one way into injections the other way is not something $\mathsf{ZF}$ alone has. What $\mathsf{ZF}$ can prove is that if there is a surjection from $X$ to $Y$ then there is an injection from $Y$ to $\mathcal{P}(X)$. $\endgroup$ Apr 25, 2022 at 1:29

2 Answers 2


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.

  • $\begingroup$ Thanks! I finally see why we can't prove existence of the injection from $h(\alpha)$ into $2^{\kappa \times \kappa}$: two different well-orderings of the subsets of $\kappa$ may have same order types. Thus, there is no bijection between proper subset of all well-orders and $h(\alpha)$. I didn't notice this initially. $\endgroup$
    – Gleb Chili
    Apr 25, 2022 at 5:02

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .