7 Infinite Sets
This chapter is about infinite sets and some challenges in proving things about
them.
Wait a minute! Why bring up infinity in a Mathematics forComputer Science
text? After all, any data set in a computer is limited by the size of the computer’s
memory, and there is a bound on the possible size of computer memory, for the
simple reason that the universe is (or at least appears to be) bounded. So why not
stick withfinitesets of some large, but bounded, size? This is a good question, but
let’s see if we can persuade you that dealing with infinite sets is inevitable.
You may not have noticed, but up to now you’ve already accepted the routine use
of the integers, the rationals and irrationals, and sequences of them—infinite sets,
all. Further, do you really want Physics or the other sciences to give up the real
numbers on the grounds that only a bounded number of bounded measurements
can be made in a bounded universe? It’s pretty convincing—and a lot simpler—to
ignore such big and uncertain bounds (the universe seems to be getting bigger all
the time) and accept theories using real numbers.
Likewise in computer science, it’s implausible to think that writing a program to
add nonnegative integers with up to as many digits as, say, the stars in the sky—
billions of galaxies each with billions of stars—would be different from writing a
program that would addanytwo integers, no matter how many digits they had. The
same is true in designing a compiler: it’s neither useful nor sensible to make use of
the fact that in a bounded universe, only a bounded number of programs will ever
be compiled.
Infinite sets also provide a nice setting to practice proof methods, because it’s
harder to sneak in unjustified steps under the guise of intuition. And there has
been a truly astonishing outcome of studying infinite sets. Their study led to the
discovery of fundamental, logical limits on what computers can possibly do. For
example, in Section 7.2, we’ll use reasoning developed for infinite sets to prove
that it’s impossible to have a perfect type-checker for a programming language.
So in this chapter, we ask you to bite the bullet and start learning to cope with
infinity.
