Mathematics for Computer Science

Chapter 5 Infinite Sets90

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 5.1.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 5.1.4.(5.3),

jP.A/jDjf0;1gnj:

But every computer scientist knows^1 that there are 2 nn-bit sequences! So we’ve

proved Theorem 5.1.5!

5.2 Infinite Cardinality

In the late nineteenth century, the mathematician Georg Cantor was studying the

convergence of Fourier series and found some series that he wanted to say con-

verged “most of the time,” even though there were an infinite number of points

where they didn’t converge. So Cantor needed a way to compare the size of infinite

sets. To get a grip on this, he got the idea of extending Theorem 5.1.4 to infinite

sets, by regarding two infinite sets as having the “same size” when there was a bi-

jection between them. Likewise, an infinite setAis be considered “as big as” a

setBwhenAsurjB, and “strictly smaller” thanBwhenAstrictB. Cantor got

diverted from his study of Fourier series by his effort to develop a theory of infinite

sizes based on these ideas. His theory ultimately had profound consequences for

the foundations of mathematics and computer science. But Cantor made a lot of

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