Cantors diagonals Listable vs. countable

  • Thread starter jVincent
  • Start date
In summary: For example, the set of all positive integers is a "list": 1, 2, 3, ... There is no last number. But it is still a list because there is a "first" and a "next". The natural numbers do have a "first" (1) but they don't have a "next" or a "last". That is what makes them unlistable.In summary, the conversation discusses the concept of listability and uncountability in relation to Cantor's diagonal argument. It is concluded that the key point is not the existence of a diagonal, but the fact that the natural numbers are finite sequences with no last element, making them unlistable. This
  • #1
jVincent
20
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 really proves is that it's absurd to talk about a complete list of even a countable set.
 
Mathematics news on Phys.org
  • #2
jVincent said:
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 really 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
What do you think a list is?
 
  • #4
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 existence of a diagonal, but that the natural numbers are finite sequences, even though there are infinite many such sequences.
 
  • #5
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 to Cantors diagonals Listable vs. countable

1. What is Cantor's diagonal argument?

Cantor's diagonal argument is a mathematical proof devised by German mathematician Georg Cantor in the late 19th century. It shows that there are different sizes of infinite sets, and that some infinite sets are larger than others.

2. How does Cantor's diagonal argument relate to listable vs. countable?

In the context of Cantor's diagonal argument, "listable" refers to a set that can be listed in a sequence, while "countable" refers to a set that can be counted. Cantor's diagonal argument shows that not all infinite sets can be listed or counted, and therefore there are different sizes of infinity.

3. Can you give an example of a listable set?

Yes, the set of all natural numbers (1, 2, 3, 4, ...) is a listable set because it can be listed in a sequence. This set is also countable, as each number can be counted.

4. What is an example of a set that is not listable but countable?

An example of a set that is not listable but countable is the set of all real numbers between 0 and 1. This set is uncountable, meaning it cannot be listed or counted in a sequence.

5. How does Cantor's diagonal argument impact mathematics and science?

Cantor's diagonal argument has had a significant impact on mathematics and science, as it has changed our understanding of infinity and the concept of size. It has also led to the development of new branches of mathematics, such as set theory and topology, and has implications in fields such as computer science and physics.

Similar threads

  • General Math
Replies
22
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
664
  • Set Theory, Logic, Probability, Statistics
2
Replies
43
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
3
Replies
86
Views
7K
Replies
1
Views
10K
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Back
Top