15
$\begingroup$

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?)

$\endgroup$
5

1 Answer 1

26
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Additionally, one can arrange by class forcing that for any $\kappa$ there is a $\lambda\ne\kappa$ with $2^\kappa=2^\lambda$. $\endgroup$ Jun 10, 2011 at 22:23
  • 1
    $\begingroup$ 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 $\endgroup$ Jun 11, 2011 at 0:27
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 11, 2011 at 0:42
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 11, 2011 at 0:44
  • $\begingroup$ 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 $\endgroup$ Jun 11, 2011 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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