13
$\begingroup$

A friend of mine told me that $X \cong Y \Rightarrow 2^X \cong 2^Y$ ($X$ and $Y$ being sets), which is very easy to prove, but he was wondering about the converse in ZF, i.e., can one take logarithms? Since the (apparently) simpler question of whether it is possible to divide by a natural number is not particularly trivial without assuming the axiom of choice (see Doyle, Conway: Division by three), I would imagine that this problem doesn't have an easy answer either.

  • 0
    See also [here](http://math.stackexchange.com/a/420484/462).2013-06-15

2 Answers 2

7

Actually this statement is not even provable within ZFC.

See this mathoverflow question

8

In fact, not only is it not provable without the Axiom of Choice, it's not provable with the Axiom of Choice! For instance, it's consistent with AC that $2^{\aleph_0} = 2^{\aleph_1} = \aleph_2$. On the other hand, if $X$ and $Y$ are finite then certainly $2^X\cong 2^Y \implies X\cong Y$, and proving this doesn't require AC at all since all the quantities involved are finite. More broadly, Easton's Theorem says that aside from some mostly-trivial constraints (e.g., $A \gt B \implies 2^A \gt 2^B$), the cardinalities of power sets (of regular cardinals) can be entirely arbitrary.

  • 0
    (Something closer to a proof, just to satisfy myself: the equality $\alpha+1=\beta+1$ is witnessed by two order-preserving one-to-one functions $f,g$ s.t. $f:\alpha+1\mapsto\beta+1$ and $g:\beta+1\mapsto\alpha+1$. Since $f$ and $g$ must map one order's terminal element onto the other order's, their restrictions $f|\alpha, g|\beta$ witness that $\alpha=\beta$)2011-10-21