5 ms·

I don’t get for Cantor’s diagonalization proof, why do we need to use the diagonal digits to form the new number? Would the proof work the same if we instead u

I don’t get for Cantor’s diagonalization proof, why do we need to use the diagonal digits to form the new number? Would the proof work the same if we instead used the first digit of every number in the list?

miloignis 5y ago
There are only 10 possible first digits of the new number, so you can't choose a number that will differ from all other numbers in the first digit. If you do it diagonally, you'll always have 9 other options to choose from, since you just have to make it different from that one number!
- arduinomancer 5y ago
  Makes sense, thanks
tpetrina 5y ago
That wouldn't work because n-th digit differing from 1st digit of n-th number doesn't guarantee that the new number isn't accounted for already.
pavpanchekha 5y ago
To fill in some details: Two real numbers are different if in the same place they have different digits. [1] So the idea is to take your infinite, hypothetical list of all real numbers A[] and make a new real number X, where for all i, there's some digit where A[i] and X differ. Easiest way is to make X differ from A[i] at digit i. [1] There's a subtlety here about repeating nines at the end of a number, but it is inessential.
pfortuny 5y ago
Then you cannot guarantee that when you change the first digit of the second number, what you get is not the first number.
erdos4d 5y ago
You need the diagonal because you are making a new number in (0,1) that can't be in the list by just choosing the nth digit of said number different than the nth digit of the diagonal.
ceh123 5y ago
To give a concrete example for you, lets start with the finite set: {0.22, 0.32, 0.33} We now construct a new number in this way: First digit of the first number is 2, so we take 3 which is different as our first digit. First digit of the second number is 3 so we take 2 as our second number. Now we have 0.32 First digit of the third number is 3 so we take 0 as our third number. We've constructed the number: 0.320 = 0.32 which is in the set already. So this construction method doesn't guarantee that it's a new number, only that it's different from the first. With Cantor's Diagonalization argument we guarantee it's different from the first number since it's different in the first digit, then we guarantee it's different from the second since it's different in the second digit, etc. etc. it's different from all the numbers in our list. To take the same set above as an example, we end up creating a number like: 0.318 which is definitely different from the numbers in the set

miloignis 5y ago

There are only 10 possible first digits of the new number, so you can't choose a number that will differ from all other numbers in the first digit. If you do it diagonally, you'll always have 9 other options to choose from, since you just have to make it different from that one number!

arduinomancer 5y ago
Makes sense, thanks

tpetrina 5y ago

That wouldn't work because n-th digit differing from 1st digit of n-th number doesn't guarantee that the new number isn't accounted for already.

pavpanchekha 5y ago

To fill in some details: Two real numbers are different if in the same place they have different digits. [1] So the idea is to take your infinite, hypothetical list of all real numbers A[] and make a new real number X, where for all i, there's some digit where A[i] and X differ. Easiest way is to make X differ from A[i] at digit i. [1] There's a subtlety here about repeating nines at the end of a number, but it is inessential.

pfortuny 5y ago

Then you cannot guarantee that when you change the first digit of the second number, what you get is not the first number.

erdos4d 5y ago

You need the diagonal because you are making a new number in (0,1) that can't be in the list by just choosing the nth digit of said number different than the nth digit of the diagonal.

ceh123 5y ago

To give a concrete example for you, lets start with the finite set: {0.22, 0.32, 0.33} We now construct a new number in this way: First digit of the first number is 2, so we take 3 which is different as our first digit. First digit of the second number is 3 so we take 2 as our second number. Now we have 0.32 First digit of the third number is 3 so we take 0 as our third number. We've constructed the number: 0.320 = 0.32 which is in the set already. So this construction method doesn't guarantee that it's a new number, only that it's different from the first. With Cantor's Diagonalization argument we guarantee it's different from the first number since it's different in the first digit, then we guarantee it's different from the second since it's different in the second digit, etc. etc. it's different from all the numbers in our list. To take the same set above as an example, we end up creating a number like: 0.318 which is definitely different from the numbers in the set