Question about Georg Cantor's Diagonal

[cyclogon]

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

 

[jishnu]

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

 

[fresh_42]

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.

 

[jedishrfu]

The idea behind Cantor's argument is that given a list of real numbers, one can always find a new number that is not on the list using his diagonal construction. It showed that the real numbers are not a countable infinity like the rational numbers.

Wouldn't every natural number you created be in the list of natural numbers if computed this way?

https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

https://en.wikipedia.org/wiki/Georg_Cantor's_first_set_theory_article

 

[cyclogon]

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

 

[Mark44]

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.

 

[mfb]

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.

 

[cyclogon]

+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 :)

 

[jbriggs444]

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.

 

[mfb]

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.

 

[cyclogon]

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

 

[mfb]

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.

 

[jbriggs444]

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.

 

[cyclogon]

+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

 

[jbriggs444]

+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.

9
99
999
9999
[...]

One valid anti-diagonal for that list is the natural number 1.

 

[cyclogon]

+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

 

[jbriggs444]

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.

 

[cyclogon]

"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 :)

 

[mfb]

"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.

 

[cyclogon]

+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