5
$\begingroup$

Cantor's diagonal argument consists of two parts: bijection and the extraction of the new number. If he shows that a given architecture of bijection doesn't work, why does it imply that any other architecture of bijection should not work either?

Just an addendum to make my point clearer:

Another possible architecture that comes to my mind is to write real numbers in the table and correspond them to the nth power of 2. Then we start to construct new numbers that weren't listed in our table and correspond them with powers of 3. After that we construct new numbers from the table of power of 3 (even if without checking we had them in the first table) we correspond them to the nth power of 5, and so on and so forth. It is easy to notice that this is a poor bijection architecture as you can put them back into one list and just repeat the construction of the new number. Why can it be mapped back to a simple list for any architecture?

On the other hand we can easily think of correspondence of natural numbers to itself, in a way that we will end up having extra unlisted numbers.E.g.(1->2,2->4, etc...). Obviously it doesn't imply that there are more natural numbers than 'natural numbers'.

$\endgroup$
  • 5
    $\begingroup$ The proof starts with an arbitrary potential bijection and shows that it is missing some element. $\endgroup$ – Tobias Kildetoft Oct 4 '16 at 9:04
  • 4
    $\begingroup$ Every potential bijection is missing a candidate. He does not show that some given architecture works. It's a proof by contradiction, in this case of atmost countability. $\endgroup$ – астон вілла олоф мэллбэрг Oct 4 '16 at 9:05
  • 2
    $\begingroup$ @guser The standard way of thanking people is to upvote their answers and accept one of them. $\endgroup$ – 5xum Oct 4 '16 at 9:11
  • 4
    $\begingroup$ @5xum: Users cannot upvote with less than 15 points. $\endgroup$ – Asaf Karagila Oct 4 '16 at 9:35
17
$\begingroup$

If he shows that a given architecture of bijection doesn't work, why does it imply that any other architecture of bijection should not work either?

That's not what he shows. He shows how every architecture is doomed to fail. Basically, Cantor's proof gives you a blueprint that you can use on any architecture to show that it is flawed.


On the other hand we can easily think of correspondence of natural numbers to itself, in a way that we will end up having extra unlisted numbers.E.g.(1->2,2->4, etc...). Obviously it doesn't imply that there are more natural numbers than 'natural numbers'.

Well, no it doesn't imply. But what's that got to do with anything?


Cantor's proof is not saying that there exists some flawed architecture for mapping $\mathbb N$ to $\mathbb R$. Your example of a mapping is precisely that - some flawed (not bijective) mapping from $\mathbb N$ to $\mathbb N$.

What the proof is saying is that every architecture for mapping $\mathbb N$ to $\mathbb R$ is flawed, and it also gives you a set of instructions on how, if you are given a particular architecture, you can find at least one number that is missing.

$\endgroup$
7
$\begingroup$

If he shows that a given architecture of bijection doesn't work, why does it imply that any other architecture of bijection should not work either?

Except he doesn't show "a given architecture", what he shows is that an ARBITRARY architecture, or equivalently, ANY architecture or as such that EVERY architecture possible to concieve will not work no matter what.

$\endgroup$
7
$\begingroup$

This is an inference rule called "universal generalization", if we can prove $\varphi(x)$, then we can deduce $\forall x\varphi(x)$.

Namely, if we can prove a property holds for an arbitrary object, then it holds for every object. If an arbitrary function is not a bijection, then every function is not a bijection.

It is true, however, that different enumerations might result in different "diagonal number". But this diagonal number will not be in the enumeration from which it was generated.

$\endgroup$
7
$\begingroup$

Long comment

Can be useful to read Cantor's original proof of the theorem :

There are infinite sets that cannot be put into one-to-one correspondence with the set of positive integers

into :

Let consider a set $M$ of elements of the form $E = (x_1, x_2, \ldots, x_{\nu}, \ldots)$ where each "coordinate" $x_i$ is either $m$ or $w$.

If $E_1, E_2, \ldots, E_{\mu}, \ldots$ is any infinite list [unendliche Rehie] of elements of the set $M$, then there is always and element $E_0$ of $M$ that does not match any $E_{\nu}$ [keine $E_{\nu}$ übereinstimmt].

The "diagonal argument" follows.

The key-points of the proof are :

  • its generality : introducing sequences of abstract symbols, Cantor shows that the uncountability is not depending on some specific property of real numbers

  • the proof is "constructive" : for any given list, it gives us a "procedure" to manufacture a new element not in the list.


See also :

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.