Here’s Mathematician KP Hart’s Math Question and Answer for Monday, December 28th!

### Counting, Part 5

In 1891, at the first meeting of the Deutsche Mathematiker-Vereinigung,  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 another 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.

The diagonal argument is very versatile, this article will tell you more.

*********************************

Read all of KP Harts math questions here!

About Dutch Mathematician KP Hart: In the beginning of this year the Dutch government opened a website, The Dutch Science Agenda, where everyone could post questions that they thought were of scientific interest. This was an attempt to involve the whole country in determining what the Dutch science agenda should be in the coming years.

I looked through the questions and searched for terms like `mathematics’, `infinity’ … to see what mathematical questions there were and I noticed various questions that already have answers (and have had for a long time). On a whim I decided to post answers to those questions, in Dutch. For your edification I will translate these posts into English.