Gamow starts by alerting us to the Hottentot tribe in Africa. Members of this tribe cannot formally count beyond three. How then do they compare commodities such as animals whose numbers are greater than three? By employing one of the most logical and primitive methods of counting- the method of counting by one-to-one correspondences or put more simply, by pairing objects with each other. So if a Hottentot has ten animals and she wishes to compare these with animals from a rival tribe, she will pair off each animal with its counterpart. If animals are left over in her own collection, she wins. If they are left over in her rival’s collection, she has to admit the rival tribe’s superiority in sheep.

What is remarkable is that this simplest of counting methods allowed the great German mathematician Georg Cantor to discover one of the most stunning and counter-intuitive facts ever divined by pure thinking. Consider the set of natural numbers 1, 2, 3… Now consider the set of even numbers 2, 4, 6…If asked which set is greater, commonsense would quickly point to the former. After all the set of natural numbers contains both even

*and*odd numbers and this would of course be greater than just the set of even numbers, wouldn’t it? But if modern science and mathematics have revealed one thing about the universe, it’s that the universe often makes commonsense stand on its head. And so it is the case here. Let’s use the Hottentot method. Line up the natural numbers and the even numbers next to each other and pair them up.

1 2 3 4 5…

2 4 6 8 10…

So 1 pairs up with 2, 2 pairs up with 4, 3 pairs up with 6 and so on. It’s now obvious that every natural number n will always pair up with an even number 2n. Thus the set of natural numbers is equal to the set of even numbers, a conclusion that seems to fly in the face of commonsense and shatters its visage. We can extend this conclusion even further. For instance consider the set of squares of natural numbers, a set that would seem even ‘smaller’ than the set of even numbers. By similar pairings we can show that every natural number n can be paired with its square n

^{2}, again demonstrating the equality of the two sets. Now you can play around with this method and establish all kinds of equalities, for instance that of whole numbers (all positive and negative numbers) with squares.

But what Cantor did with this technique was much deeper than amusing pairings. The set of natural numbers is infinite. The set of even numbers is also infinite. Yet they can be compared. Cantor showed that two infinities can actually be compared and can be shown to be equal to each other. Before Cantor infinity was just a place card for ‘unlimited’, a vague notion that exceeded man’s imagination to visualize. But Cantor showed that infinity can be mathematically precisely quantified, captured in simple notation and expressed more or less like a finite number. In fact he found a precise mapping technique with which a certain kind of infinity can be defined. By Cantor’s definition, any infinite set of objects which has a one-to-one mapping or correspondence with the natural numbers is called a ‘countably’ infinite set of objects. The correspondence needs to be strictly one-to-one and it needs to be exhaustive, that is, for every object in the first set there must be a corresponding object in the second one. The set of natural numbers is thus a ruler with which to measure the ‘size’ of other infinite sets. This countable infinity was quantified by a measure called the ‘cardinality’ of the set. The cardinality of the set of natural numbers and all others which are equivalent to it through one-to-one mappings is called ‘aleph-naught’, denoted by the symbol . The set of natural numbers and the set of odd and even numbers constitute the ‘smallest’ infinity and they all have a cardinality of . Sets which seemed disparately different in size could all now be declared equivalent to each other and pared down to a single classification. This was a towering achievement.

The perplexities of Cantor’s infinities led the great mathematician David Hilbert to propose an amusing situation called ‘Hilbert’s Hotel’. Let’s say you are on a long journey and, weary and hungry, you come to a fine-looking hotel. The hotel looks like any other but there’s a catch: much to your delight, it contains a countably infinite number of rooms. So now when the manager at the front desk says “Sorry, but we are full”, you have a response ready for him. You simply tell him to move the first guest into the second room, the second guest into the third room and so on, with the n^{th} guest moving into the (n+1)^{th} room. Easy! But now what if you are accompanied by your friends? In fact, what if you are so popular that you are accompanied by a countably infinite number of friends? No problem! You simply ask the manager to move the first guest into the second room, the second guest into the fourth room, the third guest into the sixth room…and the n^{th} guest into the 2n^{th} room. Now all the odd-numbered rooms are empty, and since we already know that the set of odd numbers is countably infinite, these rooms will easily accommodate all your countably infinite guests, making you even more popular. Mathematics can bend the laws of the material world like nothing else.

Let’s consider the set of real numbers, numbers defined with a decimal point as a.bcdefg... The real numbers consist of the rational and the irrational numbers. Is this set countably infinite? By Cantor’s definition, to demonstrate this we would have to prove that there is a one-to-one mapping between the set of real numbers and the set of natural numbers. Is this possible? Well, let’s say we have an endless list of rational numbers, for instance 2.823, 7.298, 4.001 etc. Now pair up each one of these with the natural numbers 1, 2, 3…, in this case simply by counting them. For instance:

S1 = 2.823

S2 = 7.298

S3 = 4.001

S4 = …

Have we proved that the rational numbers are countably infinite? Not really. This is because I can construct a new real number not on the list using the following prescription: construct a new real number such that it differs from the first real number in the first decimal place, the second real number in the second decimal place, the third real number in the third decimal place…and the nth real number in the nth decimal place. So for the example of three numbers above the new number can be:

S0 = 3.942

(9 is different from 8 in S1, 4 is different from 9 in S2 and 2 is different from 1 in S3)

*always*construct a number which is not on the list since it will differ from the 1

^{st}number in the first decimal place, 2

^{nd}number in the second decimal place…and from the nth number in the nth decimal place.

Cantor called this argument the ‘diagonal argument’ since it really constructs a new real number from a line that’s diagonally drawn across all the relevant numbers after the decimal points in each of the listed numbers. The image from the Wikipedia page makes the picture clearer:

In this picture, the new number is constructed from the red numbers on the diagonal. It’s obvious that the new number Eu will be different from every single number E1…En on the list. The diagonal argument is an astonishingly simple and elegant technique that can be used to prove a deep truth.

With this comparison Cantor achieved something awe-inspiring. He showed that one infinity can be greater than another, and in fact it can be infinitely greater than another. This really drives the nail in the coffin of commonsense, since a ‘comparison of two infinities’ appears absurd to the uninformed mind. But our intuitive ideas about sets break down in the face of infinity. A similar argument can demonstrate that while the rational numbers are countably infinite, the irrational numbers are uncountably so. This leads to another shattering comparison; it tells us that the tiny line segment between 0 and 1 on the number line containing real numbers (denoted by [0, 1]) is ‘larger’ than the entire set of natural numbers. A more spectacular case of David obliterating Goliath I have never seen.

The uncountably infinite set of reals comprises a separate cardinality from the cardinality of countably infinite objects like the naturals which was denoted by . Thus one might logically expect the cardinality of the reals to be denoted by ‘’. But as usual reality thwarts logic. This cardinality is actually denoted by ‘c’ and not by the expected . Why this is so is beyond my capability to understand, but it is fascinating. While it can be proven that 2^ = c,the hypothesis that c = is actually just a hypothesis, not a proven and obvious fact of mathematics. This hypothesis is called the ‘continuum hypothesis’ and happens to be one of the biggest unsolved problems in pure mathematics. The problem was in fact the first of the 23 famous problems for the new century proposed by David Hilbert in 1900 during the International Mathematical Congress in France (among others on the list were the notorious Riemann hypothesis and the fond belief that the axioms of arithmetic are consistent, later demolished by Kurt Gödel). The brilliant English mathematician G H Hardy put the continuum at the top of his list of things to do before he died (he did not succeed). A corollary of the hypothesis is that there are no sets with cardinality between and c. Unfortunately the continuum hypothesis may be forever beyond our reach. The same Gödel and the Princeton mathematician Paul Cohen damned the hypothesis by proving that, assuming the consistency of the basic foundation of set theory, the continuum hypothesis is undecidable and therefore it cannot be proved nor disproved. This is assuming that there are no contradictions in the basic foundation of set theory, something that itself is 'widely believed' but not proven. Of course all this is meat and drink for mathematicians wandering around in the most abstract reaches of thought and it will undoubtedly keep them busy for years.

But it all starts with the Hottentots, Cantor and the most primitive methods of counting and comparison. I happened to chance upon Gamow’s little gem yesterday, and all this came back to me in a rush. The comparison of infinities is simple to understand and is a fantastic device for introducing children to the wonders of mathematics. It drives home the essential weirdness of the mathematical universe and raises penetrating questions not only about the nature of this universe but about the nature of the human mind that can comprehend it. One of the biggest questions concerns the nature of reality itself. Physics has also revealed counter-intuitive truths about the universe like the curvature of space-time, the duality of waves and particles and the spooky phenomenon of entanglement, but these truths undoubtedly have a real existence as observed through exhaustive experimentation. But what do the bizarre truths revealed by mathematics actually mean? Unlike the truths of physics they can’t exactly be touched and seen. Can some of these such as the perceived differences between two kinds of infinities simply be a function of human perception, or do these truths point to an objective reality ‘out there’? If they are only a function of human perception, what is it exactly in the structure of the brain that makes such wondrous creations possible? In the twenty-first century when neuroscience promises to reveal more of the brain than was ever possible, the investigation of mathematical understanding could prove to be profoundly significant.

Blake was probably not thinking about the continuum hypothesis when he wrote the following lines:

*To see a world in a grain of sand,*

And a heaven in a wild flower,

Hold infinity in the palm of your hand,

And eternity in an hour.

And a heaven in a wild flower,

Hold infinity in the palm of your hand,

And eternity in an hour.

But mathematics would have validated his thoughts. It is through mathematics that we can hold not one but an infinity of infinities in the palm of our hand, for all of eternity.

Great post! I was a double major in applied analysis and organic chemistry, and even though I went to grad school for chemistry, I miss the math. I always found the concept of differing infinities to be fascinating, and I had dreams of solving the continuum hypothesis. Too bad that many mathematicians think that it might be undecidable -- ah, the incompleteness theorem ...

ReplyDeleteNice site, nice article.

ReplyDeleteHilton's Hotel is not a paradox. Empty rooms are created because there will be guests moving around looking for an empty room. In a hotel with infinite rooms and infinite guests occupying all rooms you cannot create empty rooms by moving guests.

PS I am aware that some travel agencies think the opposite regarding bookings.

The diagonalization argument works in general for any set and its power set (set of all subsets), and it's possible to prove that the real numbers have the same size as the power set of the natural numbers.

ReplyDeleteThe tower of power sets of the natural numbers are the "beth" (beis if you're ashkenazi) numbers; and so the continuum hypothesis is the assertion that aleph-one = beth-one.

There are some very interesting results, including a famous one proving that continuum cannot be aleph-sub-omega-six.

As to what omega six is... I'd suggest reading about "ordinal" infinites, you get strange things like inifnity plus one not being equal to one plus infinity.

Thanks for the comments. I will check out the links. I would be interested in knowing why mathematicians believe the consistency of ZF axiomatic set theory. About Hilbert's Hotel, there should not be a problem with countably infinite rooms and countably infinite guests. It's amazing that you can get such fantastic results from relatively simple arguments.

ReplyDelete"I would be interested in knowing why mathematicians believe the consistency of ZF axiomatic set theory."

ReplyDeleteBecause it's convenient? You try coming up with a different set theory. It's exhausting!

Brilliant post! I was actually similarly introduced to the beauty of Cantor's arguments, in my freshmen year of high school. Needless to say, we were quite impressed.

ReplyDelete