Introduction to Transfinite Numbers

Pascal

The shortest introduction to numbers ever written

When one tries to understand what are numbers, one eventually discovers that they are not entities in themselves, but properties of sets. For instance the set of natural satellites of Earth and the set of stars in the our solar system, both have something in common. Let us call this property ``1''. When another set happens to have the property 1, then we know that we can write a bijection between the set, and any other set that also have the property ``1".

What I said about 1 happens to be true for all others numbers.

Let us forget about numbers

What I want you to remember from the previous subsection is the word ``bijection". A bijection between two sets is a one to one mapping between them. The interest of working with bijections rather than numbers is that bijections being defined for infinite sets, we will be able to extend the idea of numbers to infinite sets.

Infinity in the eyes...

The purpose of this subsection is to show that infinity is stranger than you think.

Let us consider the set of natural integers, aka $\mathbb{N}$. This is the set of numbers 0, 1, 2, 3, 4 .... Let us also consider the set of all integers, including the negative ones, $\mathbb{Z}$. What I am going to show is that those two sets have got the same number of elements. In other words, I am going to build a bijection between $\mathbb{Z}$ and $\mathbb{N}$. I then have to attribute a natural integer (the positive ones) to every general integer (the positive and negative ones) in a one to one manner. How I am going to do that ? Simple.

Let us call $f$ this bijection between $\mathbb{Z}$ and $\mathbb{N}$. If $n$ is 0 then $f(n)=0$, in other words, $f(0)=0$. So far so good. If $n$ is a positive number, then $f(n)=2n$. For instance $f(1)=2$, $f(2)=4$, $f(3)=6$, $f(4)=8$, by now I think that you got the point. The point is that $f$ maps the positive numbers coming from $\mathbb{Z}$ into the even numbers of $\mathbb{N}$. When $n$ is negative, then $f(n)=-2n-1$. For instance, $f(-1)=1$, $f(-2)=3$, $f(-3)=5$, $f(-4)=7$, by now I think that you also got the point. The point, this time, is that $f$ maps the negative numbers coming from $\mathbb{Z}$ into the odd numbers of $\mathbb{N}$.

I want you to be sure that it actually works. So take your time. We have actually build a one to one relationship between $\mathbb{Z}$ and $\mathbb{N}$. The fact that this mapping exists says that $\mathbb{Z}$ and $\mathbb{N}$ have got the same number of elements.

Don't worry if you think that this is strange. It does this to everyone the fist time. Just like everyone fall the first time they try the jump program in the Matrix....

Oh, by the way, the function $f: \mathbb{Z} \to \mathbb{N}$ was defined by

$$f(n) = \left\{ \begin{array}{rcl} 2n & \textrm{if $n \geq 0$} \\ -2n-1 & \textrm{if $n < 0$} \end{array}\right.$$

Infinity in underwear...

Showing that there exists a one to one mapping between $\mathbb{Z}$ and $\mathbb{N}$ was impressive, but fear not, more surprises are waiting for us. Right now I will show that $\mathbb{N}^{2}$ and $\mathbb{N}$ have got the same number of elements. In other words, I will build a one to one relationship between both sets. But first let us make sure that we all know what exactly $\mathbb{N}^{2}$ is. $\mathbb{N}^{2}$ is simply the set of all couples $(a,b)$ where $a$ and $b$ are in $\mathbb{N}$, we are talking about things like $(4,7)$,$(2,0)$ or $(32430987247,29)$. For the readers with a good geometrical view, it is safe to see $\mathbb{N}^{2}$ as the 2-dimention version of $\mathbb{N}$. Now you will say ``well Pascal you managed to come up with a bijection between $\mathbb{Z}$ and $\mathbb{N}$ by warping $\mathbb{Z}$, fine, but there is no way that you can do the same with a 2D object and a 1D object".

Here you are, $f_{2}: \mathbb{N}^{2} \to \mathbb{N}$ defined by

$$f(a,b)=\frac{(a,b)(a+b+1)}{2}+b$$

We have $f(0,0)=0$, $f(1,0)=1$, $f(1,1)=4$, and I will let you do they others.... (not all of them, of course, otherwise you will be there for a while). And since I am nice, this is a table of values

$$\begin{array}{\vert ccccc \vert} \hline f(0,0)=0 & f(1,0)=1... ...)=19 & f(2,4)=25 & f(3,4)=32 & f(4,4)=41 \\ \hline \end{array}$$

Now the same table with only the values, something should come up in your mind

$$\begin{array}{\vert ccccc \vert} \hline 0 & 1 & 3 & 6 & 10 ... ...18 & 24 & 31 \\ 14 & 19 & 25 & 32 & 41 \\ \hline \end{array}$$

still nothing ?... My mistake, try like this...

$$\begin{array}{\vert ccccc \vert} \hline 0 & 1 & 3 & 6 & 10 ... ...12 & & \\ 9 & 13 & & & \\ 14 & & & & \\ \hline \end{array}$$

By now you should have got the point. The function $f_{2}$ does nothing else than warping $\mathbb{N}$ into $\mathbb{N}^{2}$ (or the opposite, depending upon how you see it).

Infinity naked...

Now that we have established that $\mathbb{N}^{2}$ and $\mathbb{N}$ are equipotent, by the way equipotent is the way to say that there exists a bijection between two sets, some of you will accept the fact that $\mathbb{Q}$ and $\mathbb{N}$ are also equipotent. Let me remind you that $\mathbb{Q}$ is the set of rational numbers, things of the form $\frac{a}{b}$. I will not show it here. Not because it is complicated but a bit long if you want to do it properly, so take my words for it. If you are interested is knowing how it is done, the very idea is that after all, between $\frac{a}{b}$ and $(a,b)$, what's the difference ?

Infinity reloaded

By now, there is something that you may have told yourself: ``so all infinite sets are equipotent to $\mathbb{N}$ in fact", in other words, for any given infinite set $A$, there exists a bijection between $A$ and $\mathbb{N}$. Unfortunately, you would be wrong. There are many different sizes for infinite sets.

As you may guess, showing that some infinite sets are equipotent to $\mathbb{N}$ is less difficult than showing that some other are not, because in the latter case we have to show that there is no bijection, this is more difficult than showing than there is one.

A very common set which is not equipotent to $\mathbb{N}$ is $\mathbb{R}$. No matter how hard you try, you will never be able to write a bijection between $\mathbb{N}$ and $\mathbb{R}$. In order to show that such a bijection doesn't exists, I will assume that there is one and I will show that from this assumption, a contradiction arises.

So let us assume that there exists a bijection $f_{3} : \mathbb{N} \to \mathbb{R}$. We know that $\arctan: \mathbb{R} \to (0,1)$ is a bijection (where $\arctan$ is the arc tangent, the inverse of the tangent function in trigonometry) and $(0,1)$ the subset of real numbers strictly between 0 and 1 (French people would have written it $]0,1[$). If you don't know about $\arctan$, don't worry, it doesn't matter. The only thing I need here is the fact that the function $\arctan \circ f_{3}$ would be a bijection from $\mathbb{N}$ to $(0,1)$. Let us call this latter bijection $f_{4}$.

Now, let us think. For all natural integer $n$, $f_{4}(n)$ is a real number of the form $0,.....$. For instance there exists an integer $n$ such that $f_{4}(n)=0.5=0.500000000....$, or another $n$ such that $f_{4}(n)=.33333333333...$, or another one such that $f_{4}(n)=0.14159...$ (I had in mind $f_{4}(n)=\pi-3$). But my point is that for all natural integer $n$, $f_{4}(n)$ is 0, followed by a coma, followed by some digits. What about calling $f_{4}(n)(1)$ the first digit of $f_{4}(n)$ and $f_{4}(n)(2)$ the second digit and so on. To have a clear mind about what is going on, given $f_{4}(n)=0.14159...$ for instance, we would have $f_{4}(n)(1)=1$ and $f_{4}(n)(2)=4$ and $f_{4}(n)(3)=1$ and $f_{4}(n)(4)=5$ etc...

Still with me, don't worry it is almost done.

Now I will introduce a number, and this number will be the real number $\lambda$ defined by

$$\lambda = 0,f_{4}(1)(1)f_{4}(2)(2)f_{4}(3)(3)...$$

The first digit of $\lambda$ is the first digit of $f_{4}(1)$. The second digit of $\lambda$ is the second digit of $f_{4}(2)$. The third digit of $\lambda$ is the third digit of $f_{4}(3)$ etc.... Not so complicated, isn't it ? In fact it is about to get more complicated, because I will in fact consider the real number $\lambda$ defined by

$$\lq\lq 0,[f_{4}(1)(1)][f_{4}(2)(2)][f_{4}(3)(3)]...''$$

where for any digit $x$, $[x]=x+1$. In the case of $x=9$, we define $[9]=0$. Given this, the thing I need for the rest of the proof is the fact that for all integer $n$, $f_{4}(n)(n)$ and $[f_{4}(n)(n)]$ are two different digits, so bear this in mind.

Now that we have this new number $\lambda$, what can we do with it. That's a good question actually, what can we possibly do with this bloody number ? Well, remember that $f_{4}$ is a bijection, so there must be an integer $\bar{n}$ such that $f_{4}(\bar{n})=\lambda$. $\bar{n}$ is a very particular integer, isn't it ?

Now let us think again (harder than last time). What about $f_{4}(\bar{n})(\bar{n})$? This is a digit right ? This digit is the $\bar{n}^{\rm th}$ digit of $\lambda$, in other words (and by definition of $\lambda$), this digit is $[f_{4}(\bar{n})(\bar{n})]$. Now we really have to sit down and think. We have just said that $f_{4}(\bar{n})(\bar{n})$ equals $[f_{4}(\bar{n})(\bar{n})]$. Isn't that impossible due to the fact that for all integer $n$, $f_{4}(n)(n)$ and $[f_{4}(n)(n)]$ are two different digits ? What have we done wrong ? Nothing. It is just that the assumption that $f_{3}$ exists was wrong... So there cannot be a bijection between $\mathbb{N}$ and $\mathbb{R}$.

Now what about really think about it until you are sure of getting it right....

Infinity reloaded - Again

Some may ask ``wait, couldn't we have done the same with the previous sets ?''. Well, actually what makes the proof working in the fact that the real number lambda was defined by this really weird (but well defined) method of taking digits from all other the place. The fact that you can actually define a proper real number that way is the key point. When one actually tries to go into the deepness of this real numbers thing, one discovers some of the most beautiful pieces of maths ever written.

Infinity and beyond

From what we have done, we are only two digits away, from discovering that there are many different sizes for infinite sets, that we can actually formalize correctly what we actually mean by the size of an infinite set, formalize formally the idea of transfinite numbers (like numbers but for infinite sets), and unless I have felt asleep first, I can even explain the thing about the continuous axiom (The fact that the truth about whether there are some transfinite numbers between the size of $\mathbb{N}$ and $\mathbb{R}$ is... well, neither true or false. It is an undecidable of the theory). After that, there are more interesting stuff, but you really don't want to know :-)

About this document ...

Introduction to Transfinite Numbers

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 TN_Introduction.tex

The translation was initiated by Pascal on 2006-07-02