Mathematics for Computer Science

4.5. Finite Cardinality 95

for 0 i 5. Since 5  3 , thisfis a surjection.
So we have figured out that ifAandBare finite sets, thenjAjjBjif and only if
AsurjB. All told, this argument wraps up the proof of a theorem that summarizes
the whole finite cardinality story:

Theorem 4.5.4.[Mapping Rules] Forfinitesets,A;B,

jAjjBj iff AsurjB; (4.5)

jAjjBj iff AinjB; (4.6)

jAjDjBj iff AbijB; (4.7)

4.5.1 How Many Subsets of a Finite Set?

As an application of the bijection mapping rule (4.7), we can give an easy proof of:

Theorem 4.5.5.There are 2 nsubsets of ann-element set. That is,

jAjDn implies jpow.A/jD 2 n:

For example, the three-element setfa 1 ;a 2 ;a 3 ghas eight different subsets:

; fa 1 g fa 2 g fa 1 ;a 2 g
fa 3 g fa 1 ;a 3 g fa 2 ;a 3 g fa 1 ;a 2 ;a 3 g
Theorem 4.5.5 follows from the fact that there is a simple bijection from subsets
ofAtof0;1gn, then-bit sequences. Namely, leta 1 ;a 2 ;:::;anbe the elements
ofA. The bijection maps each subset ofSAto the bit sequence.b 1 ;:::;bn/
defined by the rule that
biD 1 iff ai 2 S:

For example, ifn D 10 , then the subsetfa 2 ;a 3 ;a 5 ;a 7 ;a 10 gmaps to a 10-bit
sequence as follows:

subset: f a 2 ; a 3 ; a 5 ; a 7 ; a 10 g

sequence:. 0; 1; 1; 0; 1; 0; 1; 0; 0; 1 /

Now by bijection case of the Mapping Rules 4.5.4.(4.7),

jpow.A/jDjf0;1gnj:

But every computer scientist knows^6 that there are 2 nn-bit sequences! So we’ve
proved Theorem 4.5.5!

(^6) In case you’re someone who doesn’t know how manyn-bit sequences there are, you’ll find the
2 nexplained in Section 14.2.2.