#diagonal argument

Cantor (1845-1918) conceived of "set theory" and used this concept to cut into "infinity". This is a field that other mathematicians have not dabbled in because of its monstrous appearance.

The weapon is "one-on-one correspondence". For example, natural numbers 1, 2, 3, 4... and even numbers 2, 4, 6...

Which one is more? Suppose you asked me. It is normal to think that "the even numbers are the natural numbers minus the odd numbers, so there are more natural numbers", but Cantor's answer is different. An even number 2 is the first, an even number 4 is the second, and so on. Since all natural numbers and even numbers can be in one-to-one correspondence, it means that there are the same number of natural numbers and even numbers. In this way, we can conclude that there are as many fractions (= rational numbers) as there are natural numbers.

"Then what about irrational numbers?" --Here is a very interesting proof. The goal is to reach a conclusion based on the law of contradiction that "there are more irrational numbers than natural numbers."

If it is possible to have a one-to-one correspondence with the natural numbers, the irrational numbers will be expressed as decimals (rational numbers will be converted to recurring decimals) and all of them will be arranged to create a list. Now, take a number that differs from the first number in the list in the first decimal place, and from the number in the second list in the second digit, and so on. The number obtained by the procedure is not in the list ! ・・・ I was able to derive a contradiction due to contradiction. Irrational numbers are infinitely more than natural numbers. In an elegant proof, this is called the diagonal argument.

Kronecker (1823-1891) raises an objection. This person was quite eccentric and professed that the natural numbers were created by God, and that all other numbers were created by humans. Kronecker seems to have had the ambition to rebuild all mathematics on the basis of natural numbers. That's why he couldn't help but hate Cantor, the guy who came to the conclusion that there are more irrational numbers than natural numbers. Kronecker persecutes Cantor at every opportunity. As a result, he suffered from mental illness and spent the last half of his life in and out of mental hospitals.

In 1891, at the first meeting of the Deutsche Mathematiker-Vereinigung, Georg Cantor read a paper wherein he, again, showed that there is more than one kind of infinity, without using real numbers. The method that he used is now known as Cantor's Diagonal Argument.

The method works, in general, as follows: take an arbitrary set X. Using X we build an other set MX; it consists of all possible maps from X to {0,1}. So, if X={0,1,2} for example then MX is made up of eight sequences of zeros and ones of length three and if X=N, the set of natural numbers, then MN consists of all sequences of zeros and ones.

We can couple every x∈X with a member fx of MX: the map defined by fx(x)=1 and fx(t)=0 when t≠x. Note that fx≠fy whenever x≠y; the coupling (x,fx) shows that MX has at least as many elements as X itself.

Now we show that MX really has more elements than X. Consider a coupling between members of X and members of MX, so every x∈X is coupled with a map gx. We make a map g that is not coupled with any x. That is surprisingly easy: define g(x)=1-gx(x). Because g(x)≠gx(x) it follows that g≠gx for all x.

Why is this called a `diagonal argument'? Think of the case X={0,1,2}; it is then immediately clear that MX has more elements than X, it has eight and X has three. The diagonal argument works also if you have not learned how to count yet. Take a sequence for each element of {0,1,2}, say g0=(0,1,1), g1=(1,1,1), and g2=(1,0,0). The g produced by the diagonal argument (1,0,1); we made it by changing the numbers on the diagonal: (0,1,0). Without any counting we explicitly made a g that was different from g0, g1, and g2.

Because X was arbitrary this shows that for every set we can make an other one with strictly more elements. If we start with N then we can create a sequence of ever larger sets; we get infinitely many kinds of infinity.