Question about Georg Cantor's Diagonal

  • B
  • Thread starter cyclogon
  • Start date
  • #1
14
0
Hello,
Is there a reason why you cannot use the diagonal argument on the natural numbers, in the same way (to create a number not on the list)
Eg: Long lists of numbers
123874234765234...
234923748273493...
234987239847234...

Take the diagonal (1,3,4,...) then, say, modulo 10 each number 1 becomes 2, 3 to a 4, 4 to a 5 etc
to get a new number (2,4,5,...) that can't be in the list? Where did I go wrong :)

Many Thanks
 

Answers and Replies

  • #2
74
15
Hello,
Is there a reason why you cannot use the diagonal argument on the natural numbers, in the same way (to create a number not on the list)
Eg: Long lists of numbers
123874234765234...
234923748273493...
234987239847234...

Take the diagonal (1,3,4,...) then, say, modulo 10 each number 1 becomes 2, 3 to a 4, 4 to a 5 etc
to get a new number (2,4,5,...) that can't be in the list? Where did I go wrong :)

Many Thanks
What are these Georg cantor's diagonals
 
  • #3
13,817
10,984
Hello,
Is there a reason why you cannot use the diagonal argument on the natural numbers, in the same way (to create a number not on the list)
Eg: Long lists of numbers
123874234765234...
234923748273493...
234987239847234...

Take the diagonal (1,3,4,...) then, say, modulo 10 each number 1 becomes 2, 3 to a 4, 4 to a 5 etc
to get a new number (2,4,5,...) that can't be in the list? Where did I go wrong :)

Many Thanks
The point is, that I can give you a list, namely
##1,2,3,4,5,6,7,8,9 ; 10,11, \ldots ##
which does contain all diagonals!

The statement for ##\mathbb{R}## is: Given any list, then there is a diagonal ...
But here I found a list of natural numbers, for which the diagonal argument doesn't work. Also, the digits in the list for ##\mathbb{R}## are infinte, those for the natural numbers are not, so our diagonal comes to an end and is thus found in the list.
 
  • Like
Likes cyclogon
  • #4
12,225
5,925
  • Like
Likes cyclogon
  • #5
14
0
hi, thanks for your answers :)

Ok, so the modulo 10 "thing" was my idea... lol
From what I've read, it just says "use a different number"

So instead of 2,4,5,... I would pick 2,5,7,... etc always different from the diagonal, so it can't be on the list
Thanks
 
  • #6
34,305
5,946
Take the diagonal (1,3,4,...) then, say, modulo 10 each number 1 becomes 2, 3 to a 4, 4 to a 5 etc
to get a new number (2,4,5,...)
What do you mean by this?
##1 \mod 10 \equiv 1##
##2 \mod 10 \equiv 2##
## \dots##
##10 \mod 10 \equiv 0##
##11 \mod 10 \equiv 1,## etc.
Why do you say that "1 becomes 2, 3 to a 4, 4 to a 5 etc"? That's not how the modulo operation works. ##a \mod b## is the remainder when b is divided by a.
 
  • Like
Likes cyclogon
  • #7
34,968
11,157
hi, thanks for your answers :)

Ok, so the modulo 10 "thing" was my idea... lol
From what I've read, it just says "use a different number"

So instead of 2,4,5,... I would pick 2,5,7,... etc always different from the diagonal, so it can't be on the list
Thanks
Your numbers are finite (they are natural numbers), they end, and your diagonal will end somewhere as well (as an example, both 1 and 2 have to be in the list, and they both have only one digit). The number you constructed will come at some point after the diagonal ended.
 
  • Like
Likes cyclogon
  • #8
14
0
+Mark44 Sorry, I was just trying say "add one to the number, and if it's a 9 it wraps round to 0 again" sorry for the confusion

+mfb After writing a few lists of numbers out, I see what you mean :)
1
2
3
4
5
6
7
8
9
10
11? I could start the diagonal at position '9', but then what has happened to the numbers 10,11,12... They would have to be added back into the list?
Shoot :) There doesn't seem to be anywhere to start the diagonal. I pictured it with infinitely long numbers, I forgot about the beginning of the list :)
Well, if I'm wrong I'm wrong - Hope I didn't take up too much of your time,
Thanks to everyone who replied :)


EDIT: Actually, looking back at my original question, it was written with regards to infinitely long numbers.
I could have said, given an infinitely long list of infinitely long numbers, is it possible to construct a diagonal that differs by at least one number :)
 
Last edited:
  • #9
jbriggs444
Science Advisor
Homework Helper
2019 Award
9,317
4,020
I could have said, given an infinitely long list of infinitely long numbers, is it possible to construct a diagonal that differs by at least one number :)
Yes, given a countably infinite list of countably infinite digit-strings, one can trace the diagonal, change each digit and thereby construct a countably infinite digit-string (an "anti-diagonal") which is different in at least one position from every digit-string on the original list.

If one attempts to diagonalize a list of decimal expansions of natural numbers in a similar fashion, an anti-diagonal can still be produced. It will be guaranteed to differ in at last one position from every string on the list. [One may wish to reverse the digit order and left justify so that the ones place is in column 1, the tens place is in column 2, etc. and treat blanks as zeroes]. However, there is no guarantee that the anti-diagonal so produced will end in all zeroes/blanks as is proper for a finite natural number.
 
  • Like
Likes cyclogon
  • #10
34,968
11,157
If you interpret infinite strings of decimal digits as decimal expansions of numbers between 0 and 1, then you get back Cantor's argument - you try to list all real numbers in this range (with some details to sort out like 0.499... vs. 0.5) and you arrive at a contradiction as expected.
 
  • Like
Likes cyclogon
  • #11
14
0
hi jbriggs44 - Thanks for your fascinating answer, it is much appreciated :)

So I was wondering, if the new anti-diagonal is not on the original list, and one assumed the list was countably infinite....
Doesn't that mean the list is... uncountable? :) and wouldn't that list be a subset of the natural numbers?
Thanks for your time
 
  • #12
34,968
11,157
and wouldn't that list be a subset of the natural numbers?
No, it has strings of infinite length. They are not a subset of the natural numbers. If we cut away trailing zeros you can make it a superset of the natural numbers. Alternatively you can interpret them as real numbers, see my previous post.
 
  • Like
Likes cyclogon
  • #13
jbriggs444
Science Advisor
Homework Helper
2019 Award
9,317
4,020
hi jbriggs44 - Thanks for your fascinating answer, it is much appreciated :)

So I was wondering, if the new anti-diagonal is not on the original list, and one assumed the list was countably infinite....
Doesn't that mean the list is... uncountable? :) and wouldn't that list be a subset of the natural numbers?
Thanks for your time
The list is whatever the list is. I think that you are referring to a list of decimal expansions of natural numbers. That is what is implied by:
If one attempts to diagonalize a list of decimal expansions of natural numbers in a similar fashion
The diagonal argument proves that any list of finite decimal expansions is incomplete. It misses some [possibly infinite] decimal expansions. That should come as no shock.

It certainly does not demonstrate that every list of natural numbers is uncountable. Nor does it demonstrate that a countable list of natural numbers is necessarily incomplete.
 
  • #14
14
0
+jbriggs444 "The list is whatever the list is" ??? Did I say something wrong

I was actually trying to stick to the natural numbers for now, if possible thanks
 
  • #15
jbriggs444
Science Advisor
Homework Helper
2019 Award
9,317
4,020
+jbriggs444 "The list is whatever the list is" ??? Did I say something wrong

I was actually trying to stick to the natural numbers for now, if possible thanks
My statement applies to any list of natural numbers. Arbitrarily sorted. Complete or incomplete. Not just the canonical list: 1, 2, 3, ...

If you want to use the canonical list then the generated anti-diagonal string is sure to be infinitely long and not end in all zeroes. Hence, it will not be the decimal expansion of a natural number.

There is nothing stopping you from using a different list of natural numbers and getting an anti-diagonal that is indeed the [finite] decimal expansion of a natural number not present on that list.

Code:
9
99
999
9999
[...]
One valid anti-diagonal for that list is the natural number 1.
 
Last edited:
  • Like
Likes cyclogon
  • #16
14
0
+mfb - You said "No, it has strings of infinite length. They are not a subset of the natural numbers."

So are you saying a number that starts as: 4565327...
is a 'string of infinite length' - and not a number, I was assuming it was still a natural number, as in 'natural numbers go on forever'?

Thanks
 
  • #17
jbriggs444
Science Advisor
Homework Helper
2019 Award
9,317
4,020
Every natural number has a finite decimal expansion. An infinite digit string does not correspond to any natural number. [Unless, of course, all but finitely many digits are zero]

There are infinitely many natural numbers. But every one of them is finite.
 
  • Like
Likes cyclogon
  • #18
14
0
"There are infinitely many natural numbers. But every one of them is finite."

Ah, ok :) I wasn't actually aware of this, sorry for my ignorance. I don't think my original idea works only finite numbers.
Well, at least I've learned something...

Thanks to everyone who took the time to answer, and your patience is appreciated :)
 
  • #19
34,968
11,157
"go on forever" means for every natural number there is a number one larger than it - there is no largest number and no upper bound on the size. But every number on its own is finite.
 
  • Like
Likes cyclogon and jbriggs444
  • #20
14
0
+mfb Ok, thanks for that :) I guess it's just the way I'm looking at it, but it's the - "no upper bound on the size... but still finite" part I'm having trouble with, haha. I do 'see' what you're saying though, and it does make sense. I'll have to do some more studying :)
Thanks again for your replies
 

Related Threads on Question about Georg Cantor's Diagonal

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