Cantor, the man who sought infinity

How many numbers are there?

Infinity.

Yes, but what kind of infinity?

In 1891, Georg Cantor showed that not all infinities are created equal. Some are bigger than others. For this brilliant insight, he was shunned by mainstream mathematicians for most of his life. His lifelong desire to work in a prestigious university like the University of Berlin was thwarted by the leading mathematicians pf the day. Even his former teacher Kronecker termed him a “corrupter of the youth” for his unconventional mathematical ideas. Cantor spent his entire career in the University of Halle.

Georg Cantor and the University of Halle

The basic idea that Cantor proposed was something called a bijection. Briefly, it means that if any 2 sets have elements that can be mapped uniquely to each other, then both sets have the same number of elements.

Let us see what this means. Say on a street, Palm Drive, there live these families:

Kumars, Ahmeds, Singhs, Bhatias and Sinhas.

The houses on this street are numbered 123, 124, 125, 126 and 127.

Now if we map a family to a house. Say the Kumars live in house number 123, the Ahmeds in house 124, the Singhs in house 125 and so on, then we see that each family lives in a unique house also no house has more than 1 family.

Kumars -> 123

Ahmeds -> 124

Singhs -> 125

Bhatias -> 126

Sinhas -> 127

This means there have to be as many families as houses and vice versa (in this case 5) because a bijection exists between the set of families and the set of houses.

In general if we have any 2 sets of things say students and roll numbers such that they can be mapped uniquely, by this I mean each student has 1 and only 1 roll number and each roll number corresponds to only 1 student, then we can say there are as many elements in one set as the other. So there are as many roll numbers as there are students. It is easy to think of other examples, say the number of voters is equal to the number of voter identifications. In other words, the set of voters contains as many elements as the set of voter ids.

This looks pretty trivial.

But things get controversial once sets get bigger, a lot bigger, say infinite. Let us take one strange result. Cantor showed there are as many whole numbers as there are fractions.

For the moment, we’ll stick to positive numbers for simplicity, but the same logic also works for negative numbers. So by whole numbers, we mean numbers like 1, 2, 3, 4, 5, 6 …, and fractions mean things like 1/5, 2/3 and so on.

The idea that these 2 can be equal sounds absurd. After all, we can take any whole number say 5 and write it as 5/1, a fraction. So on the face of it, the set of fractions contains all the whole numbers and also some numbers (like 2/3) which are not in the set of whole numbers. So shouldn’t there be more fractions than whole numbers?

Cantor came up with this table:

1/1        2/1       3/1       4/1       5/1       6/1       …

1/2       2/2       3/2       4/2       5/2       6/2       …

1/3       2/3       3/3       4/3       5/3       6/3       …

1/4       2/4       3/4       4/4       5/4       6/4       …

All the elements in a row have the same denominator and numerators increase steadily in steps of 1 as we go from left to right. Similarly, all the elements in a column have the same numerator and the denominator increases from top to bottom.

It is easy to see that any fraction will lie somewhere on the table. To take a fraction at random 312/542 will lie on the 542nd row and 312th column.

Cantor showed there was a way to map this table to the set of whole numbers.

Also note that all the whole numbers lie on the 1st row of the table. So on the face of it, a bijection sounds difficult. After all, if we start mapping from left to right, say 1/1 -> 1, 2/1 ->2 and so on, then we’ll never get past row 1.

Cantor’s idea was to start diagonalizing. He moved along this table using a diagonal line like in the figure below.

diagonalizationCAntor.jpg

So now we get the sequence: 1/1, ½. 2/1. 3/1. 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, 5/1, 4/2, 3/3, 2/4 …

We can simplify some of these fractions such as 4/2 = 2, 2/4 = ½ to get:

1, ½, 2, 3, 1, 1/3, ¼, 2/3, 3/2, 4, 5, 2, 1, ½ …

Now removing numbers that have already occurred, we get

1, ½, 2, 3, 1/3, ¼, 2/3, 3/2. 4. 5. …

Now Cantor mapped whole numbers to this sequence

1 -> 1

2 -> ½

3 -> 3

4 -> 1/3

5 -> ¼

6 -> 2/3

So the 512th fraction in this sequence would be mapped by the whole number 512 and so on.

Let us recap, every fraction in the table (hence all possible fractions) gets mapped diagonally to a sequence. Since we have removed all repetitions, every fraction in this sequence is unique. Hence all fractions are mapped uniquely to this sequence. Now this sequence is again mapped uniquely to whole numbers.

Go over the whole argument again if you don’t understand it the first time. It can take a while for it to sink in. What we have done is to map (uniquely) every fraction to a whole number. We have created a bijection between fractions and whole numbers. According to Cantor, this was enough to show there are as many whole numbers as there are fractions. After all, if its true for students and roll numbers, why not for this. The 2 infinite sets are exactly as big as each other.

Using a similar diagonalizing trick, he showed that the number of real numbers (which includes irrational numbers which can’t be expressed either as whole or fractions, e.g. pi = 3.14159…. etc.) was greater than the number of whole numbers, that there was no bijection possible between them. Hence, not all infinite sets are equally big, some are bigger than others.

Cantor felt his insights were inspirations from God. Leading mathematicians of his day like Henri Poincare thought they were a “grave disease” in mathematics. Fortunately, towards the end of his life, Cantor’s genius was recognized. In 1904, the Royal Society awarded him their highest honor, the Sylvester medal.

But many mathematicians were disturbed by the aftermath of Cantor’s results. His unconventional approach seemed to have opened a Pandora’s box of dodgy and uncertain reasoning in mathematics. Mathematicians started coming up with all sorts of strange results using novel and usually wrong reasoning about infinities and infinite sets.

In reaction to this, mathematicians like David Hilbert arose. Hilbert was one of Cantor’s staunch defenders and he spent much of his life formalizing and making mathematics rigorous, dispelling such woolly thinking. A new movement called Formalism arose with Bertrand Russel as one of its pioneers in the early part of the 20th century which aimed to finally define all mathematics precisely and rigorously so that no one could ever be led astray.

David Hilbert and Bertrand Russell

This movement sank in the whirlpool unleashed by Kurt Godel in 1931 with his famous “incompleteness theorems”. But all this is another story, hopefully for another post.

Kurt_gödel.jpg

Kurt Godel

Please help me improve this post. If there is anything that you think is unclear in this explanation or if you can think of better examples than the ones I just made up, please put them in the comments section.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s