## You are here

HomeCantor's diagonal argument

## Primary tabs

# Cantor’s diagonal argument

One of the starting points in
Cantor’s development of set theory was his discovery that there are
different degrees of infinity. The rational numbers, for example, are
countably infinite; it is *possible* to enumerate all the rational
numbers by means of an infinite list. By contrast, the real numbers
are uncountable. it is *impossible* to enumerate them by means of an
infinite list. These discoveries underlie the idea of cardinality,
which is expressed by saying that two sets have the same cardinality
if there exists a bijective correspondence between them.

In essence, Cantor discovered two theorems: first, that the set of real numbers has the same cardinality as the power set of the naturals; and second, that a set and its power set have a different cardinality (see Cantor’s theorem). The proof of the second result is based on the celebrated diagonalization argument.

Cantor showed that for every given infinite sequence of real numbers $x_{1},x_{2},x_{3},\ldots$ it is possible to construct a real number $x$ that is not on that list. Consequently, it is impossible to enumerate the real numbers; they are uncountable. No generality is lost if we suppose that all the numbers on the list are between $0$ and $1$. Certainly, if this subset of the real numbers in uncountable, then the full set is uncountable as well.

Let us write our sequence as a table of decimal expansions:

$\begin{array}[]{rlllll}0\;.&d_{{11}}&d_{{12}}&d_{{13}}&d_{{14}}&\ldots\\ 0\;.&d_{{21}}&d_{{22}}&d_{{23}}&d_{{24}}&\ldots\\ 0\;.&d_{{31}}&d_{{32}}&d_{{33}}&d_{{34}}&\ldots\\ 0\;.&d_{{41}}&d_{{42}}&d_{{43}}&d_{{44}}&\ldots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}$ |

where

$x_{n}=0.d_{{n1}}d_{{n2}}d_{{n3}}d_{{n4}}\ldots,$ |

and the expansion avoids an infinite trailing string of the digit $9$.

For each $n=1,2,\ldots$ we choose a digit $c_{n}$ that is different from $d_{{nn}}$ and not equal to $9$, and consider the real number $x$ with decimal expansion

$0.c_{1}c_{2}c_{3}\ldots$ |

By construction, this number $x$ is different from every member of the given sequence. After all, for every $n$, the number $x$ differs from the number $x_{n}$ in the $n^{{\scriptscriptstyle\text{th}}}$ decimal digit. The claim is proven.

## Mathematics Subject Classification

03E10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## oops

In my correction, I said

X is n (a natural number) such that n \in X only if n \not\in N_x

This should be

X is n (a natural number) such that n \in X only if n \not\in N_n

sorry.

-apk

## Re: oops

Ah, I see the usage now. I'll file a more complete entry on the 'morrow. =)

## Cantor Diagonal

If "between" means "strictly between" then you want to add "make at least one ci not zero" . For example you might choose c1 first and make it not zero.

## Cantor’s diagonal argument

In the same manner, write a full list of rational numbers. How can you proof that the missing numbers Cantor constructs are all irrationals? Can you proof that, for every n, you can’t find at least one rational x, missing from the sequence?

## Cantor’s diagonal argument

Due to Cantor’s diagonal argument(!) you cannot actually construct that first table of ”decimal expansions” of all numbers that contain $d_{{nn}}$ for arbitarily large nn. It would be better to take a countable list of decimals between 0 and 1, taking the terminating version where possible. For example 0.5 and 0.4999… are the same number - we would choose 0.5.

Taking the first number in our list, if the first decimal is a ’3’ we will write out a two (if the first decimal is not a ’3’ we shall write out a three). So our number will differ from the first number in our list. We repeat the same action with the second decimal in our second number in the list. This will differ from the first number (in the first decimal) and the second number (in the second decimal).

Repeat for each number in the list.

If the list is finite, all numbers will have been exhausted but our diagonal number will differ from all of them.

Should you wish to keep adding numbers to the list, the diagonalization process will continue to generate a number which is not on the list.

Conclusion: the real numbers cannot be countable.

## reply

My question was slightly different. Make a full list of rational numbers. Why can't you construct the diagonal number dnn in the same way? And if you can, this can be seen as a proof that Q is uncountable?

## Cantor's Diagonal Argument is a fallacy.

Cantor's Delusions:

http://www.spacetimeandtheuniverse.com/math/4507-0-999-equal-one-556.htm...