Fork me on GitHub
Math for the people, by the people.

User login

Cantor's diagonal argument

Cantor's diagonalization
Type of Math Object: 
Major Section: 
Groups audience: 

Mathematics Subject Classification

03E10 no label found


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



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

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.

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?

jeremyboden's picture

Due to Cantor’s diagonal argument(!) you cannot actually construct that first table of ”decimal expansions” of all numbers that contain dnnsubscriptdnnd_{{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.

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?

Subscribe to Comments for "Cantor's diagonal argument"