ON THE INFINITE, IN THREE PARTS
William A. Wisdom

This article was written for serialization in the bi-monthly newsletter of the Philadelphia Association for Critical Thinking (PhACT). I have left it in three parts, rather than rewrite it to integrate the parts, because the breaks provide occasions to review where we've been and where we're going. They should make the whole article somewhat easier to follow. While I say that this is a popular introduction to the concept of infinitude, I realize that it is sometimes rather compact, and requires close attention. ("The infinite" and cognate terms will be defined in the article.)

THE INFINITE (PART 1 OF 3)

I submitted to our editor a popular--though I hope clear and rigorous--introduction to the concept of infinitude and some interesting things that can be known about it. We agreed both that it was worth publishing, and that it was too long for inclusion in a single issue. So it will be serialized in three consecutive issues.

Over the years I've come to realize that a great many bright and well-educated people have no clear grasp of what the infinite is. For example, I've heard it said that our merely finite minds are unable to comprehend the infinite. In a trivial sense, this is true: I can't think, one by one, of each of the members of an infinite set of things from beginning to end--this simply because there is no end (or no beginning). But there are a great many things that we can understand about infinitude. For example, I know that there is not an infinitely large chicken in my back yard. And there are many other far more interesting and perhaps startling things that we can prove and hence know about infinitude.

Many bright and well-educated people say, or have a strong tendency to believe, that all infinite collections of things are the same size. "After all, infinite is infinite. Each infinitude is just as big as any other." I guess I understand this impulse. But no minimally sensible person would say that all finite collections are the same size: "After all, finitude is finitude." I'm not here saying that some infinite sets are larger than others. To decide whether this is so or not, we need a clear understanding of what such terms as "infinite", "same size", and "larger than" mean.

I intend to consider only the infinitude of sets, collections, groups of things--bottle caps or years or numbers or, for that matter, any miscellaneous collection of possibly disparate things. So what I have to say will apply to duration (as in: infinitely many years), but not, I should think, to love or power or wisdom, which are not so easily thought of as collections of things.

We need a few preliminary definitions. The POSITIVE INTEGERS are the numbers 1, 2, 3, 4, ... . The NATURAL NUMBERS are the numbers 0, 1, 2, 3, 4, ... : i.e., the positive integers and zero. One set is a SUBSET of a second set if there is no member of the first that is absent from the second. (You can think of this more simply as: "...every member of the first is a member of the second", if you remember that this is a somewhat casual way to put it.) By virtue of the definition above, the set with no members (the EMPTY set) is a subset of every set S--this because there is no member of the empty set absent from S (since there is no member of the empty set). It also follows from the definition of a subset that every set is a subset of itself. But a set is a PROPER SUBSET of a second set if the first is a subset of the second, but is not that second set itself. The set of positive integers, then, is a proper subset of the set of natural numbers.

To PAIR the members of two sets--whether finite or infinite--is to establish a one-to-one correspondence between their members, so that each member of each set is matched with exactly one member of the other, with nothing left over unmatched in either set. Two sets--whether finite or infinite--are THE SAME SIZE, or have the same number of members, if their members can be paired, or put in a one-to-one correspondence. The notion that two sets are the same size is more basic than the notion of how many members a set has. I can know that there are the same number of people and chairs in a room without knowing how many people or chairs there are. I just see that each person is sitting alone in a chair, and no chair is empty. The set of people and the set of chairs can be paired.

A set is FINITE if either it has no members or it is the same size as the set of the first n positive integers, this for any positive integer n. There are two equivalent ways of defining the infinitude of a set: (a) a set is infinite if it is not finite; or (b) a set is INFINITE if it is the same size as at least one of its own proper subsets. Satisfy yourself that the set of natural numbers is infinite because it is the same size as the set of positive integers (a proper subset of the set of natural numbers). What you need to do is show that the members of the two sets can be paired. String them out in their ordinary order by size, and pair the first member of one string with the first member of the other, the second with the second, the third with the third, and so on. With any member n of the set of natural numbers you pair the member n+1 of the set of positive integers; and with any member m of the set of positive integers you pair the member m-1 of the set of natural number: a one-to-one correspondence, with no unmatched member in either set. So the set of positive integers is not a little bit smaller than the set of natural numbers--it's exactly the same size. And hence it's infinite by definition (b). Similarly, the set of positive integers counts as infinite because it's the same size as the set of odd positive integers, an obvious proper subset of the former. And the set of odd positive integers is infinite because it's the same size as its proper subset containing 3, 5, 7, 9, 11, 13, ... .

An infinite set is DENUMERABLE if it's the same size as the set of positive integers, and a set is COUNTABLE if it's either finite or denumerable. One way to show that an infinite set is denumerable is to show that its members can be strung out as a first, a second, a third, and so on, exhaustively. Not that you'd ever come to the end of the enumeration. But it makes sense to think of the members as coming in an order such that, for each positive integer n, each member of the infinite set turns up exactly once, in the n-th position.

A set is UNCOUNTABLE if it's not countable--i.e., if it's neither finite nor denumerable. We have established that there are denumerable sets; and it's obvious that there are finite sets. At this point in the article it's an open question whether any sets are uncountable. Such a set would have to be infinite and incapable of being paired with the positive integers.

Any set is SMALLER than another if the first is not the same size as the second, but the first is the same size as a proper subset of the second. And, conversely, a set is LARGER than a second if the second is not the same size as the first, but the second is the same size as a proper subset of the first. (So a first set is smaller than a second if and only if the second is larger than the first. These definitions apply equally to finite and infinite sets. It's not hard to show that uncountable sets, if there are any, would have to be larger than the set of positive integers.)

To show that a set S is larger than the set of positive integers, you'd have to show that the members of S can't be paired with the positive integers (and that the members of the set of positive integers can be paired with a proper subset of S). So far we haven't shown that there are any infinite sets larger than the set of positive integers. (Incidentally, denumerable sets are the smallest infinite sets: any set smaller than a denumerable set is finite.)

Here ends Part 1. It consisted largely of two things: (a) an introduction to the subject-matter of the article, and a number of key definitions needed later. It is admittedly rather dry. But it should get more interesting as we begin to explore THE INFINITE in PART 2.

THE INFINITE (PART 2 OF 3)

In PART 1 we began our introduction to thinking clearly and rigorously about the concept of infinity as it applies to sets or collections of things. Much of that part was taken up with the presentation, illustration, and brief discussion of a number of definitions needed for the remainder of this article, here and in PART 3.

Let's play a game. Imagine the Denumerable Hilton Hotel, which has denumerably many rooms, strung out from the reception desk down a (very) long hall as Room 1, Room 2, Room 3, and so on ad infinitum. Each has a distinct positive integer on its door. They're very strict about one rule: no two people in a room. Imagine the hotel filled to capacity with denumerably many guests. Now Mary and Joseph arrive, asking for a room apiece. Can they be accommodated? After all, the hotel is full. No room at the inn? No, they can be accommodated. The manager announces to all the guests over the public address system: "Please add 2 to the number on your door, and move to that room." That frees up Rooms 1 and 2 for Mary and Joseph. (Where, one might ask, do the people at the end of the hall, in the last two rooms, go? What is the answer?)

This would work for any finite number of late arrivals. But suppose that denumerably many new guests arrive. Can they be accommodated? Well, yes. This time the manager announces: "Please double the number on your door, and move to that room." That frees up all the odd-numbered rooms for the new guests, and we saw earlier that the set of odd positive integers is infinite (and hence it is denumerable). This ploy would work for any finite number of denumerable sets of new guests. ("Multiply your room number by three and move [to make room for two denumerable sets of guests], or by four [to make room for three], or by five, or ... .")

But what if denumerably many denumerably large conventions (with no overlapping memberships) wanted accommodations? Could all those conventioneers find a room apiece in a hotel with only denumerably many rooms? Perhaps we have now encountered a set of people larger than the set of positive integers. Well, we haven't. The collection of all these conventioneers is "only" denumerably large. To prove that, we have to find a way to arrange them in order as a first, a second, a third, and so on, exhaustively and without repetition.

Each conventioneer can be uniquely identified by a pair of numbers: the convention number 1, 2, 3, 4, ... , and the registration number within that convention: 1, 2, 3, 4, ... . So let's put on each conventioneer a big badge with that person's registration number in the top half, and convention number in the bottom half. Here's how to assign a unique positive integer to each conventioneer. Add the two numbers together, and collect in clusters in the (infinitely large) ballroom the people whose sum is the same. There'll be one person in the "2" group (the first registrant in the first convention: 1+1=2), there'll be two in the "3" group (registrant 1 from convention 2, and registrant 2 from convention 1), there'll be three in the "4" group (registrant 1 from convention 3, registrant 2 from convention 2, and registrant 3 from convention 1), and so on--always finitely many people in each cluster. Within each sum-cluster string out the conventioneers by registration number; and then string out the strings of like-summed conventioneers by their sum-clusters: cluster 2 first, then cluster 3, then cluster 4, and so on. This will yield a unique pairing of the members of the denumerably many denumerably large conventions with the positive integers, since they'll all be strung out as a first, second, third, etc.

By the way, a procedure only a little bit more complicated than this will prove that there are only denumerably many positive RATIONAL NUMBERS ("fractions"). This is a bit surprising, since the natural ordering of the rational numbers from smaller to bigger is DENSE: between any two rational numbers in that order there is another. This is not true of either the positive integers or the natural numbers. And while there is a smallest positive integer, and a smallest natural number, there is no smallest positive rational number. Still, there are only denumerably many positive rational numbers.

So, our best effort to find or produce a set larger than the set of positive integers has so far failed. This may not surprise you. I've often heard it said that "infinite is infinite...all infinite sets are the same size". But it turns out that this intuition is wrong. (If you have this erroneous intuition, consider: you'd never say: "finite is finite...all finite sets are the same size".) There is not only one larger infinitude; there are at least denumerably many entries in the hierarchy of larger and larger infinitudes. But we'll settle for showing that there is one larger infinitude than denumerability.

[Let me give you a puzzle to be thinking about. I have a ball with certain features. Call the instant that the ball hits the ground an impact, and the time between one impact and the next an interval. My ball bounces so that each interval is followed by another just half as long. Now suppose that I drop it from such a height that the first interval--the time between the first impact and the next--is exactly one second. I have two questions. (1) How many times will it bounce: i.e., how many impacts, and hence intervals, will there be? And (2) how long will it bounce: i.e., how long after the first impact will it no longer be bouncing? Answers below.]

THE INFINITE (PART 3 OF 3)

In PART 2 we tried to find a collection larger than the set of positive integers, a collection that is uncountably large. We found that we could fit denumerably many denumerably large conventions into "just" denumerably many rooms, one conventioneer per room. And we (almost) proved that there are the same number of positive rational numbers (fractions) as there are positive integers. Both of these results may be a little surprising. But our effort to find a set larger than the set of positive integers, an uncountable set, was unsuccessful. Perhaps there is none. We shall see. [What follows is called a "diagonal argument", and was first exploited for our purpose by Georg Cantor (1845-1918).]

Imagine a denumerably long string of 0s and 1s--as many entries in the string as there are positive integers. There are of course lots of different such strings. How many? Well, suppose for the sake of argument that there are denumerably many, which commits you to an exhaustive, complete enumeration of the strings of 0s and 1s as a first string, a second string, a third string, and so on ad infinitum. On this supposition, each different string of 0s and 1s appears somewhere, just once, in the enumeration as string #1 or string #2 or string #3 or so on.

Now go down the diagonal, taking whatever appears in the first or leftmost position of string #1 (0 or 1), followed by whatever appears in the second position of string #2, followed by whatever appears in the third position of string #3, and so on ad infinitum. Call that denumerably long string of 0s and 1s "D" (for "the diagonal string"). Now exchange each 0 in D for a 1, and each 1 in D for a 0. Call that new denumerably long string of 0s and 1s "A-D" (for "the anti-diagonal string"). I hope you see that A-D can appear nowhere in what originally was to be a complete enumeration of denumerably long strings of 0s and 1s--in what had to be a complete enumeration, if the set of denumerably long strings was itself denumerable. The string A-D can appear nowhere in that alleged enumeration, since it differs from string #1 with respect to what appears in its first position, from string #2 with respect to what appears in its second position, from string #3 with respect to what appears in its third position, and so on. For each positive integer n, A-D differs from string #n with respect to what appears in the n-th position. So that enumeration cannot be complete--indeed, no enumeration of denumerably long strings of 0s and 1s can be complete. So the set of positive integers is smaller than the set of all denumerably long strings of 0s and 1s, which latter is therefore larger than the set of positive integers. Clearly that set of strings is infinite (and has a proper subset the same size as the set of positive integers). So there is an infinitude larger than the infinitude of positive integers.

It turns out that there are lots of familiar sets the same size as our set of denumerably long strings of 0s and 1s. The set of all sets of positive integers is this size, as is the set of all points on a finitely or infinitely long line (or in a finitely or infinitely large cube). So is the set of real numbers between 0 and 1 (those that can be represented by a finitely or denumerably long decimal fraction--like one half, or the decimal part of pi or of the square root of 2), and the set of positive real numbers. All these sets are uncountable--larger than the set of positive integers. And remember that one hallmark of any set of this size (or larger) is that it makes no sense to think of all its members coming in some order as a first, a second, a third, a fourth, and so on.

One puzzle remains. None of the standard axiomatizations of set theory either proves or disproves the Continuum Hypothesis: that there is no set larger than the set of positive integers and smaller than the set of positive real numbers; that the size of the set of positive real numbers is the next largest size after that of the set of positive integers. This is so easy to express that you’d think both that it is either true or false, and that some plausible (not ad hoc) systematization of set theory would settle it one way or the other. But none does.

[Answers to the final puzzle in PART 2 of this article. (1) My ball will bounce infinitely many times--indeed, denumerably many times. Remember: each interval is followed by another interval of some positive duration. But (2) after two seconds it will no longer be bouncing. If you doubt this, get out a piece of paper and check the total elapsed time from the first impact to the second (one second), from the first to the third (one and a half seconds), from the first to the fourth (one and three-quarter seconds), from the first to the fifth (one and seven-eighths seconds), and so on. As the number of bounces increases, the total elapsed time gets closer and closer to 2 seconds, but by smaller and smaller intervals. The entire series of intervals is indeed infinite, but the sum of that series is finite--in fact, it’s two seconds. What I find particularly mysterious is the fact that, although the ball stops bouncing, there is no last bounce! (Any impact that you consider the last one is followed by another...ad infinitum.)]

Copyright © 2004, William A. Wisdom