5.5. Does All This Really Work? 103
5.5.1 Large Infinities in Computer Science
If the romance of different size infinities and continuum hypotheses doesn’t appeal
to you, not knowing about them is not going to limit you as a computer scientist.
These abstract issues about infinite sets rarely come up in mainstream mathematics,
and they don’t come up at all in computer science, where the focus is generally on
“countable,” and often just finite, sets. In practice, only logicians and set theorists
have to worry about collections that are “too big” to be sets. That’s part of the
reason that the 19th century mathematical community made jokes about “Cantor’s
paradise” of obscure infinite sets. But the challenge of reasoning correctly about
this far out stuff led directly to the profound discoveries about the logical limits of
computation described in Section 5.3, and that really is something every computer
scientist should understand.
Problems for Section 5.2
Practice Problems
Problem 5.1.
Prove that ifAandBare countable sets, then so isA[B.
Problem 5.2.
LetAD fa 0 ;a 1 ;:::;an 1 gbe a set of sizen, andBD fb 0 ;b 1 ;:::;bm 1 ga set
of sizem. Prove thatjABjDmnby defining a simple bijection fromABto
the nonnegative integers from 0 tomn 1.
Class Problems
Problem 5.3. (a)Several students felt the proof of Lemma 5.2.3 was worrisome,
if not circular. What do you think?