# Cantors diagonals Listable vs. countable

So i'm familier with cantos diagonals, but fail to see how something being unlistable makes it uncountable. Now a set being countable is to say it has a one to one corrospondance to the natural numbers, but using the diagonal method one can prove that the natural numbers are themselves unlistable.

Given any table of all the natural numbers, one can construct a number not in the table, simply by chosing something other then the n'th character in each number given, (ofcause chosing anything when no character apears).

Can someone clearify this for me? So far my conclusion is that either my textbooks are not being rigid enough in their proofs or the only thing cantors diagonal proof realy proves is that it's absurd to talk about a complete list of even a countable set.

HallsofIvy
Homework Helper
So i'm familier with cantos diagonals, but fail to see how something being unlistable makes it uncountable. Now a set being countable is to say it has a one to one corrospondance to the natural numbers, but using the diagonal method one can prove that the natural numbers are themselves unlistable.

Given any table of all the natural numbers, one can construct a number not in the table, simply by chosing something other then the n'th character in each number given, (ofcause chosing anything when no character apears).

Can someone clearify this for me? So far my conclusion is that either my textbooks are not being rigid enough in their proofs or the only thing cantors diagonal proof realy proves is that it's absurd to talk about a complete list of even a countable set.
A "list" means to have a "first", a "second" etc. A list is precisely a one-to-one correspondence with the natural numbers.

I can't speak to whether your textbooks are not being rigid (did you mean "rigorous"?) enough but your "proof" that the natural numbers are unlistable doesn't work.
"Choosing something other than the nth character in each number given" will, since there are an infinite number of natural numbers, result in a resulting infinite sequence of digits. That is NOT "a number not in the table" because it is NOT a natural number. All natural numbers have a finite number of digits.

Hurkyl
Staff Emeritus
Gold Member
What do you think a list is?

Well as they refere to a list in my textbook, they refere to "imaginary" listings like on a blackboard, and while this implies a ordering, it also requires both a first element and a last element, which the natural numbers have not.

But thank you HallsofIvy for the answer, I understand now that the key point isn't the existance of a diagonal, but that the natural numbers are finite sequences, even though there are infinite many such sequences.

HallsofIvy