MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For two sets A and B. Suppose|2^A| = |2^B| (cardinality of power sets of A and B), does |A|=|B| ?

(It is easy to see that|A|=|B| if we assume generalized continuity hypothesis. Do we have the same result without it?)

share|cite|improve this question
More people know it as Generalized Continuum Hypothesis. Gerhard "Ask Me About System Design" Paseman, 2011.06.10 – Gerhard Paseman Jun 10 '11 at 22:11
Related question:… – Joel David Hamkins Jun 11 '11 at 2:19
Actually this is the same question (in ZFC). – Martin Brandenburg Jun 11 '11 at 10:01
Possibly pertinent, but probably not, is that for finite sets a bijection from $A^2=A\times A$ to $B^2$ yields one from $A$ to $B$ (without arbitrary choices) but the same is not true in the case of $2^A$ and $2^B$. – Aaron Meyerowitz Aug 15 '11 at 10:40
See also – Andrés E. Caicedo Jun 15 '13 at 3:23
up vote 18 down vote accepted

The answer is that if the axioms of set theory are consistent, then you cannot prove that conclusion. Although it seems very reasonable to expect that a smaller set must have strictly fewer subsets, which is another way of stating your property, in fact this property is independent of ZFC.

(The fact that many people find this surprising is the reason I posted this answer to the MO question requesting examples of reasonable-sounding statements that are independent of ZFC.)

You are asking whether the continuum function $\kappa\mapsto 2^\kappa$ is injective, and it turns out that if ZFC is consistent, then this assertion is neither provable nor refutable in ZFC.

On the one hand, the property is relatively consistent with ZFC, as you observe, since it follows easily from the GCH.

On the other hand, it is known by the method of forcing to be relatively consistent that the property fails. Specifically, in Cohen's original model of $\text{ZFC}+\neg\text{CH}$, he forced over a model of GCH to add $\omega_2$ many Cohen reals, and the result is $2^\omega=2^{\omega_1}=\omega_2$ in his model, which violates your property. Cohen's model has an uncountable set $B\subset\mathbb{R}$ that has the same number of subsets as the countable set $A=\mathbb{N}$. This is usually one of the first nontrivial forcing arguments that set-theorists learn, when first exposed to the technique, and when teaching this, I invariably find the situation somewhat magical.

It is also a consequence of Martin's Axiom that $2^\kappa=2^\omega$ for all $\kappa\lt\frak{c}$, and if one has MA plus $\neg\text{CH}$, which is known to be relatively consistent by the forcing method, then there are again counterexamples to the requested property.

Meanwhile, one can show by forcing that the injectivity of the continuum function is not equivalent to GCH, since by Easton's theorem, one can find a forcing extension (of any model of GCH) in which $2^{\aleph_n}=\aleph_{n+2}$ for every natural number $n$, and otherwise the GCH holds. Such a model exhibits the desired injectivity property, but does not satisfy GCH. One can use Easton's theorem more generally to make even more extravagant violations of GCH, while still ensuring an injective continuum function.

share|cite|improve this answer
Additionally, one can arrange by class forcing that for any $\kappa$ there is a $\lambda\ne\kappa$ with $2^\kappa=2^\lambda$. – Andrés E. Caicedo Jun 10 '11 at 22:23
Your exemplary explanation (at this writing) does not mention whether the poster's statement is independent of ZFC + CH, and your explanation might benefit from mentioning Goedel's work on the consistency of GCH with respect to ZF and ZFC. Gerhard "Gilded Lilies Are Pretty Too" Paseman, 2011.06.10 – Gerhard Paseman Jun 11 '11 at 0:27
Yes, it is also independent of ZFC+CH. Much of the full answer to this comes from Eason's theorem, which allows you to control completely the continuum function on the regular cardinals. For example, you can have $2^\omega=\omega_1$, whilst $2^{\omega_1}=2^{\omega_2}=\omega_3$, with GCH elsewhere. Also, you can have $2^{\aleph_n}=\aleph_{n+2}$ for $n\gt 0$, but $2^\omega=\aleph_1$, and GCH elsehwere, which satisfies injectivity, plus CH, but not GCH. – Joel David Hamkins Jun 11 '11 at 0:42
And Gerhard, you are correct that it is because of Goedel's work that we know ZFC+GCH is consistent, which I assumed implicitly in my answer. – Joel David Hamkins Jun 11 '11 at 0:44
I can't think of any more gold to add. Thanks for the additional comments. Gerhard "Ask Me About System Design" Paseman, 2011.06.10 – Gerhard Paseman Jun 11 '11 at 1:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.