Why doesn't Cantor's diagonal argument also apply to natural numbers?
Clash Royale CLAN TAG#URR8PPP
up vote
32
down vote
favorite
In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string.
My question is: why can't we begin by representing each natural number as an infinite bit string? So that 0 = 00000000000..., 9 = 1001000000..., 255 = 111111110000000...., and so on.
If we could, then the diagonal argument would imply that there is a natural number not in the natural numbers, which is a contradiction.
analysis elementary-set-theory
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
asked Apr 26 '11 at 0:29
usul
1,4441421
add a comment |Â
up vote
32
down vote
favorite
In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string.
My question is: why can't we begin by representing each natural number as an infinite bit string? So that 0 = 00000000000..., 9 = 1001000000..., 255 = 111111110000000...., and so on.
If we could, then the diagonal argument would imply that there is a natural number not in the natural numbers, which is a contradiction.
analysis elementary-set-theory
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
asked Apr 26 '11 at 0:29
usul
1,4441421
If you try the diagonal argument on any ordering of the natural numbers, after every step of the process, your diagonal number (that's supposed to be not a natural number) is in fact a natural number. Also, the binary representation of the natural numbers terminates, whereas binary representations of real numbers do no. That's the basics for why the proof doesn't work.
– Michael Chen
Apr 26 '11 at 0:36
1
I don't think these arguments are sufficient though. For a) your diagonal number is a natural number, but is not in your set of rationals. For b), binary reps of the natural numbers do not terminate leftward, and diagonalization arguments work for real numbers between zero and one, which do terminate to the left.
– usul
Apr 26 '11 at 1:11
I upvote this question because I had it too, despite I do not understand why do we need to stack at binary strings, since the method is normally demonstrated with decimal expansion. It is extra unnecessary requirement, IMO.
– Val
Aug 15 '13 at 17:17
@Gaurang: Capitalizing every (or most) word in a title is a matter of style and taste.
– Asaf Karagila♦
Sep 2 at 12:09
@AsafKaragila I agree. I was mainly focused on removing the thanks. I have an automated capitalization corrector setup, so I just used it. I agree with you it's a matter of taste but the general tradition - if you looked at the highest voted questions - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/
– Gaurang Tandon
Sep 2 at 12:32
add a comment |Â
up vote
32
down vote
favorite
up vote
32
down vote
favorite
In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string.
My question is: why can't we begin by representing each natural number as an infinite bit string? So that 0 = 00000000000..., 9 = 1001000000..., 255 = 111111110000000...., and so on.
If we could, then the diagonal argument would imply that there is a natural number not in the natural numbers, which is a contradiction.
analysis elementary-set-theory
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
asked Apr 26 '11 at 0:29
usul
1,4441421
In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string.
My question is: why can't we begin by representing each natural number as an infinite bit string? So that 0 = 00000000000..., 9 = 1001000000..., 255 = 111111110000000...., and so on.
If we could, then the diagonal argument would imply that there is a natural number not in the natural numbers, which is a contradiction.
analysis elementary-set-theory
analysis elementary-set-theory
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
asked Apr 26 '11 at 0:29
usul
1,4441421
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
asked Apr 26 '11 at 0:29
usul
1,4441421
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
edited Sep 2 at 8:45
Gaurang Tandon
3,38822147
3,38822147
asked Apr 26 '11 at 0:29
usul
1,4441421
asked Apr 26 '11 at 0:29
usul
1,4441421
asked Apr 26 '11 at 0:29
usul
1,4441421
1,4441421
If you try the diagonal argument on any ordering of the natural numbers, after every step of the process, your diagonal number (that's supposed to be not a natural number) is in fact a natural number. Also, the binary representation of the natural numbers terminates, whereas binary representations of real numbers do no. That's the basics for why the proof doesn't work.
– Michael Chen
Apr 26 '11 at 0:36
1
I don't think these arguments are sufficient though. For a) your diagonal number is a natural number, but is not in your set of rationals. For b), binary reps of the natural numbers do not terminate leftward, and diagonalization arguments work for real numbers between zero and one, which do terminate to the left.
– usul
Apr 26 '11 at 1:11
I upvote this question because I had it too, despite I do not understand why do we need to stack at binary strings, since the method is normally demonstrated with decimal expansion. It is extra unnecessary requirement, IMO.
– Val
Aug 15 '13 at 17:17
@Gaurang: Capitalizing every (or most) word in a title is a matter of style and taste.
– Asaf Karagila♦
Sep 2 at 12:09
@AsafKaragila I agree. I was mainly focused on removing the thanks. I have an automated capitalization corrector setup, so I just used it. I agree with you it's a matter of taste but the general tradition - if you looked at the highest voted questions - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/
– Gaurang Tandon
Sep 2 at 12:32
add a comment |Â
If you try the diagonal argument on any ordering of the natural numbers, after every step of the process, your diagonal number (that's supposed to be not a natural number) is in fact a natural number. Also, the binary representation of the natural numbers terminates, whereas binary representations of real numbers do no. That's the basics for why the proof doesn't work.
– Michael Chen
Apr 26 '11 at 0:36
1
I don't think these arguments are sufficient though. For a) your diagonal number is a natural number, but is not in your set of rationals. For b), binary reps of the natural numbers do not terminate leftward, and diagonalization arguments work for real numbers between zero and one, which do terminate to the left.
– usul
Apr 26 '11 at 1:11
I upvote this question because I had it too, despite I do not understand why do we need to stack at binary strings, since the method is normally demonstrated with decimal expansion. It is extra unnecessary requirement, IMO.
– Val
Aug 15 '13 at 17:17
@Gaurang: Capitalizing every (or most) word in a title is a matter of style and taste.
– Asaf Karagila♦
Sep 2 at 12:09
@AsafKaragila I agree. I was mainly focused on removing the thanks. I have an automated capitalization corrector setup, so I just used it. I agree with you it's a matter of taste but the general tradition - if you looked at the highest voted questions - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/
– Gaurang Tandon
Sep 2 at 12:32
If you try the diagonal argument on any ordering of the natural numbers, after every step of the process, your diagonal number (that's supposed to be not a natural number) is in fact a natural number. Also, the binary representation of the natural numbers terminates, whereas binary representations of real numbers do no. That's the basics for why the proof doesn't work.
– Michael Chen
Apr 26 '11 at 0:36
If you try the diagonal argument on any ordering of the natural numbers, after every step of the process, your diagonal number (that's supposed to be not a natural number) is in fact a natural number. Also, the binary representation of the natural numbers terminates, whereas binary representations of real numbers do no. That's the basics for why the proof doesn't work.
– Michael Chen
Apr 26 '11 at 0:36
1
1
I don't think these arguments are sufficient though. For a) your diagonal number is a natural number, but is not in your set of rationals. For b), binary reps of the natural numbers do not terminate leftward, and diagonalization arguments work for real numbers between zero and one, which do terminate to the left.
– usul
Apr 26 '11 at 1:11
I don't think these arguments are sufficient though. For a) your diagonal number is a natural number, but is not in your set of rationals. For b), binary reps of the natural numbers do not terminate leftward, and diagonalization arguments work for real numbers between zero and one, which do terminate to the left.
– usul
Apr 26 '11 at 1:11
I upvote this question because I had it too, despite I do not understand why do we need to stack at binary strings, since the method is normally demonstrated with decimal expansion. It is extra unnecessary requirement, IMO.
– Val
Aug 15 '13 at 17:17
I upvote this question because I had it too, despite I do not understand why do we need to stack at binary strings, since the method is normally demonstrated with decimal expansion. It is extra unnecessary requirement, IMO.
– Val
Aug 15 '13 at 17:17
@Gaurang: Capitalizing every (or most) word in a title is a matter of style and taste.
– Asaf Karagila♦
Sep 2 at 12:09
@Gaurang: Capitalizing every (or most) word in a title is a matter of style and taste.
– Asaf Karagila♦
Sep 2 at 12:09
@AsafKaragila I agree. I was mainly focused on removing the thanks. I have an automated capitalization corrector setup, so I just used it. I agree with you it's a matter of taste but the general tradition - if you looked at the highest voted questions - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/
– Gaurang Tandon
Sep 2 at 12:32
@AsafKaragila I agree. I was mainly focused on removing the thanks. I have an automated capitalization corrector setup, so I just used it. I agree with you it's a matter of taste but the general tradition - if you looked at the highest voted questions - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/
– Gaurang Tandon
Sep 2 at 12:32
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
35
down vote
accepted
If you represent a natural number as an infinite string, the string will become identically $0$ after a certain point. If you think it through, the "diagonal argument" in this case doesn't produce a natural number; it will produce a string with infinitely many $1$s.
On the other hand, you can consider possibly infinite binary strings --- i.e. strings in which there can be infinitely many $1$; this is one way to think of
the set of $2$-adic numbers, which
is indeed an uncountable extension of the set of natural numbers (as one sees using the precise diagonal argument that you suggest).
answered Apr 26 '11 at 0:39
Matt E
103k8211375
1
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes?
– Michael Chen
Apr 26 '11 at 0:45
2
You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$.
– Thomas Andrews
Apr 26 '11 at 0:57
1
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s.
– Matt E
Apr 26 '11 at 0:58
2
@b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc.
– Michael Chen
Apr 26 '11 at 1:23
3
@b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list.
– joriki
Apr 26 '11 at 4:49
 |Â
show 5 more comments
up vote
13
down vote
The reason is simply that natural numbers have a finite representation. (In set theory, Each one is a finite number of successions from 1, where the successor of n is n+1.) Your representation scheme essentially respects this, since for any natural number (which will be on the list), after some finite number of digits it becomes all zeros. Your diagonal element will either be one of these, and so on the list, or a sequence of ones and zeros which never 'zeros out'. This string is NOT a natural number; it corresponds to nothing in your representation scheme. The reason the diagonal argument works for real numbers is that they do not have a finite representation. In set theory they are represented as the limit of an infinite series.
answered Apr 26 '11 at 3:58
Matt Phillips
1312
1
This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!
– Ken Bellows
Aug 1 '16 at 16:53
add a comment |Â
protected by user99914 Dec 4 '17 at 4:58
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
35
down vote
accepted
If you represent a natural number as an infinite string, the string will become identically $0$ after a certain point. If you think it through, the "diagonal argument" in this case doesn't produce a natural number; it will produce a string with infinitely many $1$s.
On the other hand, you can consider possibly infinite binary strings --- i.e. strings in which there can be infinitely many $1$; this is one way to think of
the set of $2$-adic numbers, which
is indeed an uncountable extension of the set of natural numbers (as one sees using the precise diagonal argument that you suggest).
answered Apr 26 '11 at 0:39
Matt E
103k8211375
1
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes?
– Michael Chen
Apr 26 '11 at 0:45
2
You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$.
– Thomas Andrews
Apr 26 '11 at 0:57
1
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s.
– Matt E
Apr 26 '11 at 0:58
2
@b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc.
– Michael Chen
Apr 26 '11 at 1:23
3
@b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list.
– joriki
Apr 26 '11 at 4:49
 |Â
show 5 more comments
up vote
35
down vote
accepted
If you represent a natural number as an infinite string, the string will become identically $0$ after a certain point. If you think it through, the "diagonal argument" in this case doesn't produce a natural number; it will produce a string with infinitely many $1$s.
On the other hand, you can consider possibly infinite binary strings --- i.e. strings in which there can be infinitely many $1$; this is one way to think of
the set of $2$-adic numbers, which
is indeed an uncountable extension of the set of natural numbers (as one sees using the precise diagonal argument that you suggest).
answered Apr 26 '11 at 0:39
Matt E
103k8211375
1
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes?
– Michael Chen
Apr 26 '11 at 0:45
2
You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$.
– Thomas Andrews
Apr 26 '11 at 0:57
1
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s.
– Matt E
Apr 26 '11 at 0:58
2
@b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc.
– Michael Chen
Apr 26 '11 at 1:23
3
@b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list.
– joriki
Apr 26 '11 at 4:49
 |Â
show 5 more comments
up vote
35
down vote
accepted
up vote
35
down vote
accepted
If you represent a natural number as an infinite string, the string will become identically $0$ after a certain point. If you think it through, the "diagonal argument" in this case doesn't produce a natural number; it will produce a string with infinitely many $1$s.
On the other hand, you can consider possibly infinite binary strings --- i.e. strings in which there can be infinitely many $1$; this is one way to think of
the set of $2$-adic numbers, which
is indeed an uncountable extension of the set of natural numbers (as one sees using the precise diagonal argument that you suggest).
answered Apr 26 '11 at 0:39
Matt E
103k8211375
If you represent a natural number as an infinite string, the string will become identically $0$ after a certain point. If you think it through, the "diagonal argument" in this case doesn't produce a natural number; it will produce a string with infinitely many $1$s.
On the other hand, you can consider possibly infinite binary strings --- i.e. strings in which there can be infinitely many $1$; this is one way to think of
the set of $2$-adic numbers, which
is indeed an uncountable extension of the set of natural numbers (as one sees using the precise diagonal argument that you suggest).
answered Apr 26 '11 at 0:39
Matt E
103k8211375
edited Apr 25 '13 at 10:20
answered Apr 26 '11 at 0:39
Matt E
103k8211375
answered Apr 26 '11 at 0:39
Matt E
103k8211375
answered Apr 26 '11 at 0:39
Matt E
103k8211375
103k8211375
1
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes?
– Michael Chen
Apr 26 '11 at 0:45
2
You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$.
– Thomas Andrews
Apr 26 '11 at 0:57
1
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s.
– Matt E
Apr 26 '11 at 0:58
2
@b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc.
– Michael Chen
Apr 26 '11 at 1:23
3
@b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list.
– joriki
Apr 26 '11 at 4:49
 |Â
show 5 more comments
1
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes?
– Michael Chen
Apr 26 '11 at 0:45
2
You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$.
– Thomas Andrews
Apr 26 '11 at 0:57
1
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s.
– Matt E
Apr 26 '11 at 0:58
2
@b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc.
– Michael Chen
Apr 26 '11 at 1:23
3
@b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list.
– joriki
Apr 26 '11 at 4:49
1
1
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes?
– Michael Chen
Apr 26 '11 at 0:45
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes?
– Michael Chen
Apr 26 '11 at 0:45
2
2
You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$.
– Thomas Andrews
Apr 26 '11 at 0:57
You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$.
– Thomas Andrews
Apr 26 '11 at 0:57
1
1
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s.
– Matt E
Apr 26 '11 at 0:58
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s.
– Matt E
Apr 26 '11 at 0:58
2
2
@b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc.
– Michael Chen
Apr 26 '11 at 1:23
@b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc.
– Michael Chen
Apr 26 '11 at 1:23
3
3
@b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list.
– joriki
Apr 26 '11 at 4:49
@b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list.
– joriki
Apr 26 '11 at 4:49
 |Â
show 5 more comments
up vote
13
down vote
The reason is simply that natural numbers have a finite representation. (In set theory, Each one is a finite number of successions from 1, where the successor of n is n+1.) Your representation scheme essentially respects this, since for any natural number (which will be on the list), after some finite number of digits it becomes all zeros. Your diagonal element will either be one of these, and so on the list, or a sequence of ones and zeros which never 'zeros out'. This string is NOT a natural number; it corresponds to nothing in your representation scheme. The reason the diagonal argument works for real numbers is that they do not have a finite representation. In set theory they are represented as the limit of an infinite series.
answered Apr 26 '11 at 3:58
Matt Phillips
1312
1
This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!
– Ken Bellows
Aug 1 '16 at 16:53
add a comment |Â
up vote
13
down vote
The reason is simply that natural numbers have a finite representation. (In set theory, Each one is a finite number of successions from 1, where the successor of n is n+1.) Your representation scheme essentially respects this, since for any natural number (which will be on the list), after some finite number of digits it becomes all zeros. Your diagonal element will either be one of these, and so on the list, or a sequence of ones and zeros which never 'zeros out'. This string is NOT a natural number; it corresponds to nothing in your representation scheme. The reason the diagonal argument works for real numbers is that they do not have a finite representation. In set theory they are represented as the limit of an infinite series.
answered Apr 26 '11 at 3:58
Matt Phillips
1312
1
This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!
– Ken Bellows
Aug 1 '16 at 16:53
add a comment |Â
up vote
13
down vote
up vote
13
down vote
The reason is simply that natural numbers have a finite representation. (In set theory, Each one is a finite number of successions from 1, where the successor of n is n+1.) Your representation scheme essentially respects this, since for any natural number (which will be on the list), after some finite number of digits it becomes all zeros. Your diagonal element will either be one of these, and so on the list, or a sequence of ones and zeros which never 'zeros out'. This string is NOT a natural number; it corresponds to nothing in your representation scheme. The reason the diagonal argument works for real numbers is that they do not have a finite representation. In set theory they are represented as the limit of an infinite series.
answered Apr 26 '11 at 3:58
Matt Phillips
1312
The reason is simply that natural numbers have a finite representation. (In set theory, Each one is a finite number of successions from 1, where the successor of n is n+1.) Your representation scheme essentially respects this, since for any natural number (which will be on the list), after some finite number of digits it becomes all zeros. Your diagonal element will either be one of these, and so on the list, or a sequence of ones and zeros which never 'zeros out'. This string is NOT a natural number; it corresponds to nothing in your representation scheme. The reason the diagonal argument works for real numbers is that they do not have a finite representation. In set theory they are represented as the limit of an infinite series.
answered Apr 26 '11 at 3:58
Matt Phillips
1312
answered Apr 26 '11 at 3:58
Matt Phillips
1312
answered Apr 26 '11 at 3:58
Matt Phillips
1312
answered Apr 26 '11 at 3:58
Matt Phillips
1312
1312
1
This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!
– Ken Bellows
Aug 1 '16 at 16:53
add a comment |Â
1
This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!
– Ken Bellows
Aug 1 '16 at 16:53
1
1
This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!
– Ken Bellows
Aug 1 '16 at 16:53
This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!
– Ken Bellows
Aug 1 '16 at 16:53
add a comment |Â
protected by user99914 Dec 4 '17 at 4:58
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
If you try the diagonal argument on any ordering of the natural numbers, after every step of the process, your diagonal number (that's supposed to be not a natural number) is in fact a natural number. Also, the binary representation of the natural numbers terminates, whereas binary representations of real numbers do no. That's the basics for why the proof doesn't work.
– Michael Chen
Apr 26 '11 at 0:36
1
I don't think these arguments are sufficient though. For a) your diagonal number is a natural number, but is not in your set of rationals. For b), binary reps of the natural numbers do not terminate leftward, and diagonalization arguments work for real numbers between zero and one, which do terminate to the left.
– usul
Apr 26 '11 at 1:11
I upvote this question because I had it too, despite I do not understand why do we need to stack at binary strings, since the method is normally demonstrated with decimal expansion. It is extra unnecessary requirement, IMO.
– Val
Aug 15 '13 at 17:17
@Gaurang: Capitalizing every (or most) word in a title is a matter of style and taste.
– Asaf Karagila♦
Sep 2 at 12:09
@AsafKaragila I agree. I was mainly focused on removing the thanks. I have an automated capitalization corrector setup, so I just used it. I agree with you it's a matter of taste but the general tradition - if you looked at the highest voted questions - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/
– Gaurang Tandon
Sep 2 at 12:32