Chapter 5 Infinite Sets94
5.2.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,P.A/, is “strictly bigger”
thanA. That is
In particular,
Theorem 5.2.6.[Cantor] For any set,A,
AstrictP.A/:Proof. First of all,P.A/is as big asA: for example, the partial functionf W
P.A/!A, wheref.fag/WWDafora 2 Aandf is only defined on one-element
sets, is a surjection.
To show thatP.A/is strictly bigger thanA, we have to show that ifgis a
function fromAtoP.A/, thengis not a surjection. To do this, we’ll simply find a
subset,AgAthat is not in the range ofg. The idea is, for any elementa 2 A, to
look at the setg.a/Aand ask whether or notahappens to be ing.a/. Namely
define
AgWWDfa 2 Aja...g.a/g:
NowAgis a well-defined subset ofA, which means it is a member ofP.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, namely
the setAg, that is not in the range ofg.
Cantor’s Theorem immediately implies:Corollary 5.2.7.P.N/is uncountable.
The bijection between subsets of ann-element set and the lengthnbit-strings,
f0;1gn, used to prove Theorem 5.1.5, carries over to a bijection between subsets of
a countably infinite set and the infinite bit-strings,f0;1g!. That is,
P.N/bijf0;1g!:This immediately implies
Corollary 5.2.8.f0;1g!is uncountable.