To Infinity… And Beyond?

“If you could count for a year,

Would you get to Infinity,

Or somewhere in that vicinity?”

—  That’s Mathematics, Tom Lehrer.

So, what is Infinity?

In classical times, infinity was a word that simply denoted the possibility of always generating new objects,that is, never running out of objects of a certain type. For example, when Euclid asserts that there are infinitely many prime numbers, he states it thus (translation of Sir Thomas Heath):

Prime numbers are more than any assigned multitude of prime numbers.

That is, whenever we are given a certain (finite) collection of prime numbers, we can rest assured that we can always generate a prime number which is not in this collection. This trend in the interpretation of infinity persisted even to fairly recent times. Even Henri Poincaré held similar views.

This was radically changed in 1874 when a German mathematician, Georg Cantor, published his ideas on how infinity can be treated as a true mathematical entity which can be measured and analysed.

Cantor’s main idea is very simple. Imagine a dance, where people are dancing in couples, and each couple consists of a man and a woman. Suppose that everyone is dancing. Then there must be exactly as many men as women present at the party. How do we know this? You probably already know the answer, but let’s try to state it in a precise way, so that we see how to generalize this simple idea.

Well, represent the men by dots on the left (blue), and the women by dots on the right (green). Then, draw an arrow from each man to his dancing partner. We know the following:

1. Every blue dot is connected to one, and only one, green dot.
2. Every green dot has one, and only one, blue dot connected to it.

If you think carefully about it, what (1) is saying is that there are at least as many green dots as blue dots, and (2) is saying that there are at least as many blue dots as green dots. Putting these two together, the conclusion must be that there are exactly as many blue dots as there are green.

What happened above, in mathematical language, is that we established a one-to-one correspondence, a bijection, between the set of blue dots and the sot of green gots. A bijection between sets A and B of objects is a correspondence, just like above, that satisfies the conditions:

1. Every element in A corresponds to one, and only one, element of B
2. Every element in B has one, and only one, element in A corresponding to it.

Actually, when we count object, this is exactly what we do (even if we don’t know it!): we set up a bijection between the set of objects we’re counting, and a set of numbers. For example, when counting how many blue dots we have in the above diagram, we point at the top one, and say “1”, then we point at the next one, and say “2”, and so on.

What Cantor realized was that we can use bijections to count even infinite sets. This generalization is so intuitive and natural, and yet Cantor was so shocked by some weird phenomena that occur in the realm of infinities, that he wrote to his friend Dedekind, saying: “Je le vois, mais je ne le crois pas” (I see it, but I do not believe it). Not only Cantor was shocked, but many mathematicians that were his contemporaries denounced his work, accusing Cantor of having created a theology instead of mathematics. Today, however, Cantor’s theory is the basis of a wide range of mathematical subjects, from analysis to algebra and geometry.

Countable Sets

Whenever a set can be put into bijection with the natural numbers (that is, its elements can be counted: 1,2,3,4,…), Cantor called it a countable set. An example of a countable is the set of natural numbers N = {1,2,3,4, …} itself, since it can be put into a bijection with itself in the stupid, obvious way (send 1 to 1, 2 to 2, etc).

What about the set of even numbers: 2,4,6,8,10,… ? Well, we can establish a correspondence between the even numbers and the natural numbers, simply by sending each even number to itself divided by 2:

2 -> 1

4 -> 2

6 -> 3

8 -> 4

…

You should be able to check that this is a bijection: you can get from right to left by dividing by 2, and from left to right by multiplying by 2, and there’s only one way you do can either of these operations.

But wait a minute. According to our reasoning above (with the counting at the dance), this seems to be saying that there are exactly as many even numbers as there are natural numbers. How can that be possible, when the even numbers are only a part of the natural numbers?

After all, the set of men is only a part of the set of humans, but obviously, there are much more humans than just men! The trick is, the set of humans is still finite (and it is not in bijection with the set of men). The set of natural numbers is infinite, and things will get weird. Here are other “sub”sets of the natural numbers, which also are in bijection with the whole set of natural numbers: the set of prime numbers, the set of square numbers, the set of integers ( that is, including the negative numbers: {…,-3,-2,-1,0,1,2,3,…}). Try to check for yourself that these are countable sets!

Hilbert’s Hotel

The great German mathematician David Hilbert was not in the lodging business, but let’s suppose that he is the proud owner of the Grand Hotel: a special hotel with infinitely many rooms. In fact, let’s say that the set of rooms at this hotel is countable, so we can attach a natural number to each of these rooms: room 1, room 2, room 3, etc. At the desk, there is a young clerk, newly hired, and still somewhat unaccustomed to thinking about infinite numbers.

One day, (the hotel was still empty, having been newly opened) a bus with a countably infinite number of seats pulls over, and a countably infinite number of passengers get off it. The young clerk is distraught: how will he assign rooms to all these guests? He calls Hilbert, and Hilbert explains to him that, since there are countably many guests, then we can assign each of them a natural number: guest 1, guest 2, guest 3, etc. Thus we can assign the guests to the rooms by matching the numbers: guest 1 to room 1, guest 2 to room 2, etc. Very simple, the clerk admits. He does exactly that, and the hotel is now full.

The next day, one more guest arrives. The clerk tries to politely explain that the hotel is full, and that there are no more rooms, but the guest (a very important person, let’s say) insists on having a room. The clerk calls Hilbert again, and Hilbert, as always, has an elegant solution: let each guest move to the room next to where they’re staying. So guest 1, who was in room 1, now moves to room 2. Guest 2, who was in room 2, moves to room 3. And so on. Now all the guests who were previously staying at the hotel, are still staying at the hotel: but room 1 is free! The new guest has a place to stay after all.

The next day, another countably infinite bus arrives. The young clerk is a nervous wreck (and seriously considers whether he should be in business with another mathematician ever again). Once more, he calls Hilbert. Hilbert calmly explains that there is no problem at all!

Let every guest currently staying at the hotel, Hilbert says, move to the room whose number is double the number of the room they’re currently staying in. This means, that whoever is staying in room 1 should move to room 2, whoever is staying in room 2 should move to room 4, whoever is staying in room 3 should move to room 6, and so on. The guests are all too happy to move, and after they’re done, all the guests are still at the hotel: they occupy the even-numbered rooms, and all the odd-numbered rooms are empty. The Grand Hotel now has a countably infinite number of empty rooms, ready to serve the new guests!

Un-countable sets?

The key to understanding the Grand Hotel is Cantor’s set theory. The above examples can be translated into the following propositions:

• If we add 1 object to a countable set, the new set will still be countable
• If we add countably many objects to a countable set, the new set will still be countable.

It seems no matter how many things we try to throw into the mix, we’re always ending up with countable sets. Is this really it? Is this infinity? Nothing beyond? Is it true that any set has size less than or equal to that of N, the set of the natural numbers? Or can we have sets that are bigger than that? What would that even mean?

Let’s make a first attempt at constructing a set that contains more objects than there are natural numbers (this is vague at the moment, but we’ll just try an example where it seems there are just too many things to make it countable.). The set Q of rational numbers, is the set of fractions: for example, 1/2, 4/3, 6/3, 1009/11125, etc. Two things should be noted here. The first is that Q already contains the natural numbers, since every natural number can be represented as a fraction: 1 = 1/1, 2 = 2/1, 3 = 3/1, etc. And so, the natural numbers are also rational numbers (or as we say, they’re a subset of the rationals).

The second observation is that between any two rational numbers x and y, there exists always a rational number z which is not equal to either x or y. This might be a bit tricky at first glance, but it’s actually quite easy to see: imagine the rational numbers as being ordered on a line, and for points x and y on that line representing any two rational numbers, take z to be the point in the middle lying between them. In other words, take z to be (x+y)/2.

Since we can generate rational numbers like that indefinitely, this shows that between any two rational numbers there are infinitely many rational numbers! This is certainly not true for natural numbers (there are no naturals between 1 and 2 !). This means that there is no immediately obvious way of ordering Q in such a way that we can say: this is the first rational, this is the second rational, etc. (Try it, what is the rational number that comes right after 0? is it 1/2? 1/3? 1/4? )

But Cantor figured out a way to make this ordering, and proved that Q is still countable. Here’s how he did it. First, since Q contains N, Q must be at least countable. That is, it must have at least as many elements as there are natural numbers. Then, Cantor proves that there are at most as many rational numbers as there are natural numbers. This establishes that Q and N have the same number of elements. This is how Cantor carried out the second part of that proof:

He ordered all fractionals in a grid, as above, and started counting the way indicated by the arrows. The first fraction is 1/1, then comes 2/1, 1/2, 1/3, 2/2, 3/1, and so on. From this, it is clear that there are countably many fractions, and since the rational numbers are fractions, it follows that there are at most countably many rational numbers. QED.

So, our first attempt to construct an infinite uncountable set failed. However, this is far from being the end of the story. Cantor himself was the first one to find an example of an infinite, uncountable set. The set R of real numbers.

The real numbers are the numbers that can be expressed as a decimal expansion. Any rational number is a real number. For example, 1 can be written as 1.0000….., while 1/2 can be written as 0.500000…. 1/3 can be written as 0.666666…. 1/11 is 0.09090909…. 1/7 is 0.142857142857142857…. In fact, the rational numbers correspond exactly to the real numbers whose expansion is made up of the same number repeating over and over.

Not all real numbers are rational, however. A famous example is “pi” = 3.1415926535897932…. No matter how far we go, we’ll never find periodicity in the digits of pi.

The way Cantor showed that the real numbers are uncountable is ingenious, and the same trick has been applied again and again in mathematics, that it earned a name for itself: the diagonal argument. This is how it goes. Cantor shows that the set of real numbers between 0 and 1 is uncountable. Since this is a part (subset) of R, this means that R is at least as big as an uncountable set, and so is uncountable itself.

Suppose that the real numbers between 0 and 1 can be counted, i.e. we can list them by saying: this is the first real number (between 0 and 1), this is the second, and we can exhaust all of them in that manner. For example, we might have someone claiming that the complete list of real numbers between 0 and 1 starts with something like this:

1:  0.23623775484599….

2: 0.357932946343912….

3: 0.78993747347839…..

4: 0.67812947437843…..

Cantor shows that this list cannot consist of ALL numbers between 0 and 1, no matter what numbers it has in it. The reason is because we can explicitly construct a number which, while lying between 0 and 1, cannot be on the list. To do this, let’s put 0. in front. The first number on the list has a decimal expansion starting with 2, so for my number, I will choose a digit different than 2, say 4. So far, I have 0.4.

For the second number on the list, the 2nd decimal digit is 5, so for my number, I will choose a digit different than 5, say 9. So far, I have 0.49.

For the third number on the list, the 3rd decimal digit is 9, so for my number, I will choose a digit different than 9, say 3. So far, I have 0.493.

I keep going in this manner, and I get a real number: 0.4932… which lies between 0 and 1, but it cannot be any number that appears on the list. If a number appears as the n’th entry in the list, my number will differ from it at the nth decimal digit! It differs with the 1st list number at the 1st decimal digit, with the 2nd list number at the 2nd decimal digit, and so on. This proves Cantor’s claim. R is uncountable.

Cantor proved much more than this. He showed that if you want to define infinity as the size of an infinite set, then no matter what set you choose, you can always find a set with a strictly larger number of elements. In other words, there is an infinite number of different infinities!

Some fun games with infinities

The readers who are more at ease with mathematics, could try to prove the following propositions (or sketch an argument).

• Draw any two line segments. Then they have exactly the same number of points. (Find a bijection between them. Might be easier if they’re parallel).
• The set of real numbers between 0 and 1 (not including 0 nor 1) has the exactly as many numbers as the whole set of real numbers.
• Draw a square. Then the square (along with its inner region) contains exactly as many points as a single side of the square (crazy, huh? that’s what prompted Cantor’s comment to Dedekind, mentioned above).
• Find more examples!

Disclaimer: The views and opinions expressed in this article are those of the author(s) and do not necessarily reflect the policy or position of the site administration and/or other contributors to this site.

Comments

comments