The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us

4. Infinity Puzzles

4 The last function of reason is to recognize that there is an infinity of things which are beyond it. It is but feeble if it does not see so far as to know this.1 —Blaise Pascal (1623–1662) To infinity and beyond! —Buzz Lightyear, Toy Story (1995) There’s an infinite number of monkeys outside who want to talk to us about this script for “Hamlet” they’ve worked out. —Douglas Adams (1952–2001), The Hitchhiker’s Guide to the Galaxy Since ancient times, people have contemplated the infinite and its properties . For most of that time, our thoughts on the infinite were mired in strange ideas that could not withstand the rigor of exact reasoning. With such confusion, the medievals would endlessly discuss inane questions, like “How many angels can dance on the head of a pin?” In the late nineteenth century, Georg Cantor (1845–1918) and several associates were finally able to grab ahold of this slippery topic and make some progress. However, the new science of infinity has many counterintuitive concepts that are challenging to our intuition. It is important to realize that ideas about infinity are not abstract scholastic thoughts that plague absentminded professors in the ivy-covered towers of academia. Rather, all of calculus is based on the modern notions of infinity mentioned in this chapter. Calculus, in turn, is the basis of all of the modern mathematics, physics, and engineering that make our advanced technological civilization possible. The reason the counterintuitive ideas of infinity are central to modern science is that they work. We cannot simply ignore them. Infinity Puzzles 66 Chapter 4 Section 4.1 is concerned with the basic language of sets. I restrict myself to the familiar world of finite sets and give a nice definition that determines when two sets are the same size. In section 4.2 I take this definition that works so well with finite sets and see what happens when we move to infinite sets. The strange world of infinity starts making life more interesting . The core of this chapter is section 4.3, where we encounter the different levels of infinity. Along the way, we will learn about a powerful proof technique called diagonalization. I close with section 4.4, where more advanced and philosophical topics are discussed. 4.1 Sets and Sizes The ideas of infinity are expressed in the language of sets. A set is a collection of distinct objects. The objects can be anything and everything (including other sets). The objects in a set are called elements or members of the set. Sets can be denoted by braces (curly brackets) around their elements . So, the set {a, b, c} has three elements, which are the letters a, b, and c. We can talk about the set of students in a class, the set of red cars, the set of U.S. residents, the set of fractions, and so on. There are different ways of denoting a set. We can list the elements of the set, such as {dogs, cats, parrots, fish, snakes}, or we can describe the same set by giving a description: {x: x is one of the five most popular household pets}. This is read as “The set of all x, such that x is one of the five most popular household pets.” Another example is {3, 5, 7, 9, 11}. This is the same set as {x: x is an odd whole number greater than or equal to 3 and less than 12}. Sometimes, when talking about infinite sets, I will use an ellipsis (. . .) to mean that the sequence continues. For example, the prime numbers can be written as {2, 3, 5, 7, 11, 13, . . .}. Infinity Puzzles 67 Capital letters will be used as names to describe certain sets: D = {1, 3, 5, 7, 9, 11, 13, 15, . . . }. Two sets are equal if every element of one set is an element of the other set. So if F = {x: x is a whole odd number} it is obvious that D = F. Certain sets will be subsets of other sets. It is obvious that the set of women in a class is a subset of the set of all students in the class. This is because every woman in the class is a student in the class. In general, given two sets, S and T, we say that S is a subset of T if every...