Cantor diagonalization and fundamental theorem

Question

Can the Cantor diagonal argument be use to check countability of natural numbers? I know how it sounds, but anyway.

According to the fundamental theorem of arithmetic, any natural number can be expressed as an unique product of primes.

if we denote primes $2,3,5,\ldots$ as $P_1,P_2,P_3,\ldots$ and include $1$ as part of the system, we will get,

$$D = [1, P_1, P_2, P_3,\ldots]$$

we can write any natural number as series of $[d]$ that goes on forever, as we can keep on appending $1$ to any product of primes forever.

for example $6$ is $2 \cdot 3 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1.....$

Now, we use the Cantor diagonalization, and enumerate all possible combinations of D.

$$1 - D_{11}, D_{12}, D_{13}, D_{14}, ...$$ $$...$$ $$n - D_{n1}, D_{n2}, D_{n3}, D_{n4}, ...$$ $$...$$

Can we show that there is another number that is not in the list? If we assume that there is a function, $\operatorname{Next}(D)$, that gives as the next element in $[D]$.

$$P_1 = \operatorname{Next}(1)$$ $$P{n+1} = \operatorname{Next}(P_n)$$

since there is always the next prime, we can construct,

$$m = \operatorname{Next}(D_{11}) \cdot \operatorname{Next}(D_{22}) \cdot \operatorname{Next}(D_{33}) \cdot \operatorname{Next}(D_{44})...$$

This is analogous to adding $1$ to diagonal elements applied to real numbers.

From the same diagonalization argument this number, '$m$' cannot be in the list. It is a contradiction, and natural numbers aren't countable...

Can someone point on a rigurous discussion of such a reasoning?

Thanks!

Answer 1

Product of infinitely many primes is not a natural number.

Answer 2

Suppose we make start to make a list of the integers using your scheme: \begin{align} 1&\to 1,1,1,1,1,1,\ldots\\ 2&\to 2,1,1,1,1,1,\ldots\\ 3&\to 3,1,1,1,1,1,\ldots\\ 4&\to 2,2,1,1,1,1,\ldots\\ 5&\to 5,1,1,1,1,1\ldots\\ 6&\to 3,2,1,1,1,1\ldots\\ \end{align} and so forth. What happens if we apply the diagonal argument?

There are two possibilities: the diagonal contains infinitely many primes or finitely many primes. Let's consider these cases in turn:

• There are infinitely many primes on the diagonal. In that case, our string would contain an infinite number of primes. But that won't represent a natural number, since this would be infinitely large! So this would give no valid number.
• There are finitely many primes on the diagonal. If that's the case, the diagonal argument does give us a string which represents a natural number by its prime factors. To see which one, all we need do is multiply all the factors. But if it's a natural number, then it must show up on our list already---we have not added anything to our list.

So either we get a duplicate of something on our list, or something that doesn't make sense on our list. Hence in neither case does the diagonal argument allow us to conclude that the natural numbers are uncountable.