# Cantor diagonalization and fundamental theorem

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!

• It seems that your construction gives a positive power to an infinite number of primes, which does not result in an integer. Since you have not shown that your construction produces a natural number, it does not show "this number cannot be in the list". Commented Jul 25, 2014 at 18:18
• I guess, some of your elements in your list are equivalent (as natural numbers). However, to state it precisely I need to know what is $D_{ij}$, that is what is $D_{11},D_{12}$ etc. From your current setting this is not clear.
– SBF
Commented Jul 25, 2014 at 18:18
• I wonder if it'd make more sense in a $p$-adic context? (Which would fit with Cantor's diagonal argument being used to prove uncountability) Commented Jul 25, 2014 at 18:21
• with real numbers, Dij would be any number from 0 to 9, in this case Dij is 1 or any prime number. Of course as in case with real numbers, the same prime could be repeated in one sequence up to infinity. Commented Jul 25, 2014 at 18:24
• Related: a different approach (setting infinitely many bits in an integer) to the same end: Why doesn't Cantor's diagonal argument also apply to natural numbers?. Commented Jul 25, 2014 at 18:27

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.

• Note that only one of the two cases in fact applies to the natural numbers. I imagine it's the latter, but I don't actually know and so structured my argument around this gap in my knowledge. Commented Jul 25, 2014 at 18:56
• I am not sure I understand, "won't represent a natural number, since this would be infinitely large!". There is an infinity of primes, is there then an infinitely large set of infinitely large primes or one infinitely large prime? Commented Jul 25, 2014 at 20:31
• That's not quite what I mean, so let me put it another way. Suppose I tell you to divide 1 by 2 an infinite number of times. You could, not unreasonably, conclude that you end up with 0 (which is a natural number.) But if you multiply by 2 an infinite number of times, you won't ever end up at a natural number (you'll hit many of them, but you'll never end up anywhere). @paradox Commented Jul 25, 2014 at 20:34
• Now, one could define there to be a number that is a product of an infinite number of primes. (In fact, people have done studied things like this.) But at that point you're studying something quite different than the natural numbers. Commented Jul 25, 2014 at 20:36
• wondering if there is a name of this "something quite different" at all. Could it be p-adic integers as you mentioned in your earlier comment. It seems like a very interesting idea. Thanks! Commented Jul 25, 2014 at 20:49

Product of infinitely many primes is not a natural number.

• I agree, but in my question, it is product of primers and 1. Commented Jul 25, 2014 at 18:29
• Then either your question is very unclear, or that it can ultimately be reduced to this issue. Commented Jul 25, 2014 at 18:54