# Does $2^X=2^Y\Rightarrow |X|=|Y|$ imply the axiom of choice?

The Generalized Continuum Hypothesis can be stated as $2^{\aleph_\alpha}=\aleph_{\alpha+1}$. We know that GCH implies AC (Jech, The Axiom of Choice, Theorem 9.1 p.133).

In fact, a relatively weak formulation: $|X|\le|Y|< 2^X\implies |X|=|Y|$ would already imply the axiom of choice, although in this case the proof is slightly longer. [Note: in Herrlich's book he refers to GCH stated above as "The Aleph Hypothesis" and the weak formulation is called GCH]

GCH itself is independent of the axiom of choice, we can have the axiom of choice and power sets can grow wildly, or just "a little bit". We can have the continuum function to be injective, but the continuum hypothesis can fail on a proper class of cardinals (for example $2^\kappa=\kappa^{++}$ for regular cardinals).

Let ICF (Injective Continuum Function) be the assertion: $$2^X=2^Y\implies |X|=|Y|.$$

Question: Assuming ZF+ICF, can we deduce AC?

(I looked around Equivalents of the Axiom of Choice, but couldn't find much. It is possible that I missed this, though.)

Edits:

1. In an exercise in Jech he states that if there exists an infinite Dedekind-finite cardinal, then ICF does not hold. From the assumption that it holds we can deduce that there are no infinite D-finite sets.

2. Note that if $f\colon X\to Y$ is a surjection then $A\subseteq Y\mapsto f^{-1}(A)$ is an injection from $P(Y)$ into $P(X)$. This means that ICF implies the Dual Cantor-Schroeder-Bernstein theorem:

Assume that $X$ and $Y$ have surjections from one onto the other, then there are injections between their power-sets therefore $2^X=2^Y$ and thus $|X|=|Y|$.

3. We shall abbreviate Goldstern's variant of ICF as Homomorphic Continuum Function, or HCF: $$2^X\leq 2^Y\implies |X|\leq|Y|$$ One major observation is that HCF implies The Partition Principle (PP), which states that $A$ can be mapped onto $B$ (or $B$ is empty) if and only if $B$ can be injected into $A$. This principle is quite an open choice principle, and it is unknown whether or not it implies AC in ZF.

To see that HCF implies PP, we observe the following: if $f\colon A\to B$ is surjective then the preimage map is an injection from $2^B$ into $2^A$, i.e. $2^B\leq 2^A$, from HCF it follows that $B\leq A$, i.e. there is $g\colon B\to A$ injective.

-
The implication from $2^{\aleph_\alpha}=\aleph_{\alpha+1}$ to AC is not quite trivial. It is a starred exercise in Kunen's book (III.9). There are two reasons why I call it non-trivial: The axiom of foundation seems to be necessary; and the limit step is not as trivial as it may appear to the naive reader. –  Goldstern Nov 17 '11 at 22:21
I'm inclined to agree with Goldstern, because I've seen too many students give the standard false proof of "If power sets of well-orderable sets are well-orderable then AC holds," even after being warned that there is a standard false proof. –  Andreas Blass Nov 18 '11 at 0:21
Andreas, Goldstern: I thought it over and you both were right. The transfinite induction argument cannot hold because we cannot assure that the union of well ordered families of well ordered sets is well orderable. I gave reference to the proof, which is not very hard but indeed less trivial than I'd expected. –  Asaf Karagila Nov 18 '11 at 10:15
A reasonable (possibly easier) variant of your question: Does $\forall X,Y:( 2^X\le 2^Y \Rightarrow X \le Y)$ imply AC? –  Goldstern Nov 18 '11 at 12:17
Steve, yes somewhat relevant but under choice the question I ask is moot. In ZFC everything implies AC :-) –  Asaf Karagila Apr 17 '12 at 7:53

Here is a little progress towards AC.

Theorem. ICF implies the dual Cantor-Schröder-Bernstein theorem, that is $X$ surjects onto $Y$ and $Y$ surjects onto $X$, then they are bijective.

Proof. You explain this in the edit to the question. If $X\twoheadrightarrow Y$, then $2^Y\leq 2^X$ by taking pre-images, and so if also $Y\twoheadrightarrow X$, then $2^X\leq 2^Y$ and so $X\sim Y$ by ICF. QED

Theorem. ICF implies that there are no infinite D-finite sets.

Proof. (This is a solution to the exercise that you mention.) If $A$ is infinite and Dedekind-finite, then let $B$ be the set of all finite non-repeating finite sequences from $A$. This is also D-finite, since a countably infinite subset of $B$ easily gives rise to a countably infinite subset of $A$. But meanwhile, $B$ surjects onto $B+1$, since we can map the empty sequence to the new point, and apply the shift map to chop off the first element of any sequence. So $B$ and $B+1$ surject onto each other, and so by the dual Cantor-Schöder-Bernstein result, they are bijective, contradicting the fact that $B$ is D-finite. QED

Here is the new part:

Theorem. ICF implies that $\kappa^+$ injects into $2^\kappa$ for every ordinal $\kappa$.

Proof. We may assume $\kappa$ is infinite. Notice that $2^{\kappa^2}$ surjects onto $\kappa^+$, since every $\alpha<\kappa$ is coded by a relation on $\kappa$. Since $\kappa^2\sim\kappa$, this means $2^\kappa\twoheadrightarrow\kappa^+$ and consequently $2^{\kappa^+}\leq 2^{2^\kappa}$, by taking pre-images. It follows that $2^{2^\kappa}=2^{2^\kappa}\cdot 2^{\kappa^+}=2^{2^\kappa+\kappa^+}$ and so by ICF we get $2^\kappa+\kappa^+=2^\kappa$, which implies $\kappa^+\leq 2^\kappa$, as desired. QED

This conclusion already contradicts AD, for example, since AD implies that there is no $\omega_1$ sequence of distinct reals, which violates the conclusion when $\kappa=\omega$. In particular, this shows that ICF implies $\neg$AD, and so in every AD model, there are sets of different cardinalities, whose power sets are equinumerous.

-
Indeed. It is simple to see that in ZF+AD $2^\omega=2^{\omega_1}$ (and for many many more ordinals) so ICF fails bad. Furthermore every cardinal below $\mathcal P(\mathbb R)$ which is a quotient of $\mathbb R$ (read: cardinal of equivalence classes of some relation) will have the same power set as $\mathbb R$ itself. There are so many of these as well. But the new part is interesting indeed! –  Asaf Karagila Aug 24 '12 at 22:29
Joel, it may be worth pointing out that the non-existence of infinite D-finite sets already follows from dual Schroeder-Bernstein. –  Andres Caicedo Aug 24 '12 at 23:23
The third theorem also follows from dual CSB using surjections $2^\kappa \to 2^{\kappa + \kappa} \to 2^\kappa \times 2^\kappa \to 2^\kappa \times \kappa^+ \to 2^\kappa$. –  Trevor Wilson Aug 25 '12 at 6:22
@Asaf: In ZF + AD, $2^\omega \ne 2^{\omega_1}$. The coding lemma gives a surjection, but there cannot be an injection (just look at singleton subsets of $\omega_1$.) –  Trevor Wilson Aug 25 '12 at 6:32
Trevor, indeed, under AD we have $2^\omega\neq 2^{\omega_1}$, since $\omega_1$ does not inject into $2^\omega$, but since under AD those power sets surject onto each other, we get $2^{2^\omega}=2^{2^{\omega_1}}$ via pre-images. –  Joel David Hamkins Aug 25 '12 at 11:41