Cantor's infinite paradise

"No one shall drive us from the paradise which Cantor has created for us" - David Hilbert

The statement that the set of natural number is an infinite set is a common knowledge. I will not provide a solid definition of the natural numbers. One reason is that I do not know one. At least, I do not have one which would not be based on some previous knowledge, and as a consequence, I did not consider it self-contained. The second reason is that I think it is not needed, since I assume that almost all of us have a good intuition.

Anyway, to avoid any confusion, the set of natural numbers is the set of the form
 $$N={1,2,3,4,...,n-1,n,n+1,...}$$
When we look at this set of numbers, we can agree that this set of numbers is infinite. Of course, we all know that the natural numbers are infinite. Or we don't? This question seems easy to answer, but we are going to explore this notion of infinite in an enjoyable and easy to understand way (I hope). And if we are going to take a glimpse of the infinity, then Cantor is the best guide ever.

one to one correspondence

I think all of us remember when we first start to count things with fingers. Our teacher might been said: "I have \(2\) apples in one hand and \(3\) apples in the other hand. How many apples I have?". We can of course answer with \(4\), because the class is so boring and made us hungry enough, and we ate one of them. But beside the hunger, one mechanism worked every time: counting with fingers. The basic idea is for each finger I have, I put aside one apple. There is a one to one relation between the fingers and apples. Cantor used this idea and stated that any to sets of elements have the same number of elements, if for each element of the first set, not chosen before, I can assign a single element, not chosen before, from the second set. When we apply this idea to the natural numbers and other sets some strange things starts to happen.

Let's suppose that I have this subset of natural numbers
$$N_{+10}={10,11,12,13,..}$$
One question is the set \(N_{+10}\) has the same number of elements as \(N\)? Using the one to one correspondence idea of size of a set, Cantor noticed that
$$ 1 \leftrightarrow 11 ; \space 2 \leftrightarrow 12; \space 3 \leftrightarrow 13; ..; \space n \leftrightarrow n+10; \space ...$$
and the logical conclusion is that both sets have the same number of elements. But this is contrary to our intuition. If we compare a part with the whole, than these two can't be equal. In fact this idea is old enough and we know that Euclid told us. Well, Euclid seems to be wrong this time. Or at least he was right, but only when things are finite. A second though might give us some hope of discovering a small dirty trick: we compare an "infinite" with an "infinite minus 10". This infinite is such a huge thing that \(10\) is too tiny to be taken into account. It should be some trick somewhere.

Well, we can ask a second question. If the previous sets differs only by a small number what if we take two disproportionate sets, like \(N\) and some small subset like the one below?
$$N_{*1000}={1000,2000,3000,..,n*1000,...}$$
We follow the same approach and by now it is not too hard to see that even if \(N_{*1000}\) seems to have only \(0.1\%\) of the elements of \(N\), they still have the very same number of elements. The counting by fingers works.

why it works

I do not know how or why Cantor arrived at this correspondence. But I think one can see this very logical if you take it from a proper angle. But before I let you know about my perspective let's analyze some additional things.

You might remember that the Babylonians used sexagesimal base \(60\) when counting. If you don't, you can take a look here. Even today some of this positional numeric system can bee seen in astronomy, common time, navigation. A curious and closer look at their numeric system reveals that they used in fact only two symbols: one for unit and one for tens. That is a nice trick. Better than the Greeks who seems to use their whole alphabet to count their crops. Another example is the binary system, which is used everywhere if a modern computer of any sort is implied. For the binary system we use again only two symbols.

What this numeric systems have in common it is not the position, the base, or the number of symbols used, although it might happen to be the same. This numeric systems have in common an operation and a unit. All of them are artifacts of a single number \(1\) and the add operation \(+\). If you combine multiple \(1\)s by addition you get any number you want from these numeric systems. More formally by adding multiple times \(1\) you get any of the natural numbers. Any of them.

My perspective is that all those sets which have the same number of elements as the set of natural numbers are made from the same stuff: ones and additions.  It does not matter how you name them, or how you write them. The fabric of the natural numbers is the same. And all infinite sets made from the same stuff should have the same number of infinite elements.

what about other sets: rationals, primes, integers?

It seems that Cantor saw that idea some how. He also found that the set of integer numbers has the same number of elements as \(N\). Right now we are already good at that, and we might found not difficulties in showing that if we enrich our natural set with subtraction which is the reverse of adding (It's like in this Radio Erevan anecdote: It's true that X have won a car at lottery? It's true. However it was not a car, but a bicycle.  And he did not won it, but it was stolen from him).

Cantor also found that the set of rational numbers has the same number of elements. A rational number is any number of the form \(\frac{a}{b}\), where \(a,b\) are integer numbers. His proof is really nice to follow.

In order to prove that he noticed that the rational number can be arranged like

 It is not hard to see that this arrangement covers the whole range of rational numbers and there is a way to traverse this arrangement. Using the established arrangement and traversing operation we can assign to each element a position in the traversal. By that position, if we assume that two people are using this arrangement and traversal, they can transmit a number to one another only by position, which is a natural number! It is the same like in the case of the positional numeric system. If the extraterrestrials from Mars would write their numbers in the order specified by the arrows, they would end up with the same infinity as of the terrestrial natural numbers. It's a small world.

I found this thing astonishing, since it looks like the matrix arrangement of rational numbers seems to have two infinite dimensions! And indeed, that was another discovery for which we have to thank also to Georg Cantor. It seems like if you have a multi-dimensional set, and on each dimension you have natural numbers, the number of elements, even if infinite, is the same as of the natural number set! Again, these sets are made from the same fabric: ones and additions.

than all sets are infinite as \(N\)?

It looks like this infinite absorbs anything. Any set we might want to try to build, which is not finite (limited somehow), ends up having the same infinite number of elements. And other than looking like a black whole for the sizes of the sets, we can say nothing more about it.

However the story does not ends here. Cantor ended up into a mental hospital, praying to be taken home but left there, that is the sad truth. He was depressed from childhood and suffered when he was away from his own home. He saw his mathematical endeavors as a way to escape and built for him and for us, in his years or sometimes hours of lucidity a paradise which we just started to touch.

However it's too late in night for me to write now, and I will keep other dimensions of his paradise for another time.

A Mathematician's Apology

I have just read the awesome book written by G. C. Hardy in 1940: "A Mathematician's Apology". It is a must read. Among other things, he talks about the many aspects of Mathematics and I found there two beautiful theorems which he considers (and I agree) that are accessible to anyone. These two theorems are trustful witnesses of the glory and beauty of Mathematics.

I can hardly do better than go back to the Greeks. I will state and prove two of the famous theorems of Greek mathematics. They are ‘simple’ theorems, simple both in idea and in execution,but there is no doubt at all about their being theorems of the highest class. Each is as fresh and significant as when it has discovered—two thousand years have not written a wrinkle on either of them. Finally, both the statements and the proofs can be mastered in an hour by any intelligent reader, however slender his mathematical equipment.

1. The first is Euclid’s proof of the existence of an infinity of prime numbers. The prime numbers or primes are the numbers which cannot be resolved into smaller factors $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...$$ Thus \(37\) and \(317\) are prime. The primes are the material out of which all numbers are built up by multiplication: thus \(666 = 2 ⋅ 3 ⋅ 3 ⋅ 37\). Every number which is not prime itself is divisible by at least one prime (usually, of course, by several). We have to prove that there are infinitely many primes, i.e. that the series never comes to an end. Let us suppose that it does, and that \(2, 3, 5, ... , P\) is the complete series (so that \(P\) is the largest prime); and let us, on this hypothesis, consider the number \(Q\) defined by the formula $$Q = (2 ⋅ 3 ⋅ 5 ⋅ 3 ⋅..⋅ P) + 1$$ It is plain that \(Q\) is not divisible by and of \(2, 3, 5, ... , P\); for it leaves the remainder \(1\) when divided by any one of these numbers. But, if not itself prime, it is divisible by some prime, and therefore there is a prime (which may be \(Q\) itself) greater than any of them. This contradicts our hypothesis, that there is no prime greater than \(P\) ; and therefore this hypothesis is false.
The proof is by reductio ad absurdum, and reductio ad absurdum, which Euclid loved so much, is one of a mathematician’s finest weapons. It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game.

2. My second example is Pythagoras’s proof of the ‘irrationality’ of \(\sqrt{2}\). A ‘rational number’ is fraction \(\frac{a}{b}\), where \(a\) and \(b\) are integers: we may suppose that \(a\) and \(b\) have no common factor, since if they had we could remove it. To say that ‘\(\sqrt{2}\) is irrational’ is merely another way of saying that \(2\) cannot be expressed in the form \((\frac{a}{b})^2\); and this is the same as saying that the equation $$a^2 = 2b^2$$ cannot be satisfied by integral values of \(a\) and \(b\) which have no common factor. This is a theorem of pure arithmetic, which does not demand any knowledge of ‘irrational numbers’ or depend on any theory about their nature. We argue again by reductio ad absurdum; we suppose that the equation is true, \(a\) and \(b\) being integers without any common factor. It follows that \(a^2\) is even (since \(2b^2\) is divisible by \(2\)), and therefore that \(a\) is even (since the square of an odd number is odd). If \(a\) is even then $$a = 2c$$ for some integral value of \(c\); and therefore $$2b^2 = a^2 = (2c)^2 = 4c^2$$ or $$b^2 = 2c^2$$ Hence \(b^2\) is even, and therefore (for the same reason as before) \(b\) is even. That is to say, \(a\) and \(b\) are both even, and so have common factor \(2\). This contradicts our hypothesis, and therefore the hypothesis is false.
It follows from Pythagoras’s theorem that the diagonal of a square is incommensurable with the side (that their ratio is not a rational number, that there is no unit of which both are integral multiples). For if we take the side as our unit of length, and the length of the diagonal is \(d\), then, by a very familiar theorem also ascribed to Pythagoras, $$d^2 = 1^2 + 1^2 = 2$$ So that \(d\) cannot be a rational number.

I love this kind of stuff.