7.1. Infinite Cardinality 211
7.1.3 Power sets are strictly bigger
Cantor’s astonishing discovery was thatnot all infinite sets are the same size. In
particular, he proved that for any set,A, the power set, pow.A/, is “strictly bigger”
thanA. That is,
Theorem 7.1.11.[Cantor] For any set,A,
Astrict pow.A/:Proof. To show thatAis strictly smaller than pow.A/, we have to show that ifgis
a function fromAto pow.A/, thengisnota surjection. To do this, we’ll simply
find a subset,AgAthat is not in the range ofg. The idea is, for any element
a 2 A, to look at the setg.a/Aand ask whether or notahappens to be ing.a/.
First, define
AgWWDfa 2 Aja...g.a/g:
Agis now a well-defined subset ofA, which means it is a member of pow.A/. But
Agcan’t be in the range ofg, because if it were, we would have
AgDg.a 0 /for somea 02 A, so by definition ofAg,
a 2 g.a 0 / iff a 2 Ag iff a...g.a/for alla 2 A. Now lettingaDa 0 yields the contradiction
a 02 g.a 0 / iff a 0 ...g.a 0 /:Sogis not a surjection, because there is an element in the power set ofA, specifi-
cally the setAg, that is not in the range ofg.
Cantor’s Theorem immediately implies:Corollary 7.1.12.pow.N/is uncountable.
The bijection between subsets of ann-element set and the lengthnbit-strings,
f0;1gn, used to prove Theorem 4.5.5, carries over to a bijection between subsets of
a countably infinite set and the infinite bit-strings,f0;1g!. That is,
pow.N/bijf0;1g!:This immediately implies
Corollary 7.1.13.f0;1g!is uncountable.