Cantors diagonals Listable vs. countable

  • Thread starter jVincent
  • Start date
  • #1
18
0
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.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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.
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
What do you think a list is?
 
  • #4
18
0
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.
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,833
956
A list must always have a "first member" and there must always be a "next" member. But there does not have to be a "last" member.
 

Related Threads on Cantors diagonals Listable vs. countable

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
4K
Replies
19
Views
871
Replies
22
Views
1K
Replies
9
Views
2K
Replies
36
Views
8K
Replies
12
Views
4K
Replies
12
Views
4K
Replies
3
Views
9K
  • Last Post
Replies
5
Views
3K
Top