2
$\begingroup$

Hello all and first let me say thanks for reading this, this is my first post on this website.

I have some intuitive issues with Cantor's diagonal argument, briefly explained here https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument if you know it by another name.

I understand how it proves that there is no one to one mapping between real numbers and natural numbers, and I believe that is true. I do not like the proof itself, however, and I need someone to correct my understanding. To demonstrate my thought process, I will attempt to construct an example that uses the diagonal argument to prove there is no one to one mapping from natural to natural numbers, which is obviously a contradiction.

So, here it is. I begin by defining a bunch of sets that correspond to the natural numbers. They use the prime factorization of the numbers, such that the nth element of the set is the exponent of the nth prime number in the natural number that it corresponds to's prime factorization. That is worded confusingly, so I will show some examples.

2 -> (2^1)(3^0)(5^0)... -> {1, 0, 0, 0, 0, 0...}

45 -> (2^0)(3^2)(5^1)... -> {0, 2, 1, 0, 0, 0 ...}

90 -> {1, 2, 1, 0, 0, 0, ... }

Using this, I now have a set for each natural number. I can list them out like this:

S1 = {1, 0, 0, ...}

S2 = {0, 1, 0, ...}

S3 = {2, 0, 0, ...}

S4 = {0, 0, 1, ...}

S5 = {1, 1, 0, ...}

.

.

.

And so on. Those sets are in order, but it does not really matter what order they are in.

Using the diagonal argument, I can create a new set, not on the list, by taking the nth element of the nth set and changing it, by, say, adding one. Therefor, the new set is different from every set on the list in at least one way. This is straight from the Wikipedia article if I am not explaining this logic right.

Now here is the catch. The new set I created using the diagonal argument must not be on the list because it is different from everything on the list, but because I defined the list as the prime factorization of any natural number, than any set has to be on the list because "The fundamental theorem of arithmetic says that every positive integer has a single unique prime factorization."

To me, this is a contradiction. The diagonal argument does not make intuitive sense to me, I must be misunderstanding it. Hopefully one of you will understand what I tried to convey here and help me understand what I did wrong.

$\endgroup$
  • 3
    $\begingroup$ Your number is infinity and does not belong to natural numbers. $\endgroup$ – velut luna Mar 28 '16 at 4:20
  • 2
    $\begingroup$ The sequence you get by diagonalization has an infinite number of non-zero entries, so does not correspond to the prime power factorization of a natural number. $\endgroup$ – André Nicolas Mar 28 '16 at 4:21
1
$\begingroup$

Your number is infinity and does not belong to natural numbers. – Kyson 4 mins ago

The sequence you get by diagonalization has an infinite number of non-zero entries, so does not correspond to the prime power factorization of a natural number. – André Nicolas 3 mins ago

Both of these are true and make a lot of sense, thanks for the quick answers! It seems so obvious now, but it was bothering me.

Now i only wish I could close this question without waiting the 2 days to accept my own answer.

$\endgroup$
  • 1
    $\begingroup$ Why to close the question? Let it here for future curious people to read and learn. $\endgroup$ – DonAntonio Mar 28 '16 at 8:24

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.