# Natural numbers sorted uncountable?

$|\mathbb{N}|$ by definition is countable infinite. Going to sets of elements indexed by a finite number of indices labelling countable components yields again countably infinite sets (like when counting the rationals using two indices (dimensions)).

Intuitively I would say that whenever a at least countably infinite number of indices (dimensions) is required the set will not be countable any more.

Is this correct?

If that would be so, then representing the natural numbers via powers of primes and using the primes as indices (dimensions) and the powers as natural number valued components it would actually follow that the natural numbers are not countable, which is of course wrong. But is this due to a wrong premise or are there any other problems with this argument?

• You can show the set $S$ of all sequences of natural numbers is uncountable with Cantor's diagonal method: Suppose $C=(d_n)_{n\in N}$ is a sequence of members of $S.$ Let $f(n)$ be the nth member of the sequence $d_n.$ Then the sequence $(1+f(n))_{n \in N}$ belongs to $S$ but not to $C.$ – DanielWainfleet Apr 15 '16 at 17:52

There are two different ways to imagine an infinite dimensional array:

• The direct product. $\prod_{i\in I}A_i$ is the set of all sequences $\langle x_i\rangle_{i\in I}$, where $x_i\in A_i$. So, for example, $\prod_{i\in\mathbb{N}}\mathbb{N}$ is the set of all infinite sequences of natural numbers. It is true that if each $A_i$ has more than one element, and $I$ is infinite, then $\prod_{i\in I}A_i$ is uncountable.

• The direct sum. Same idea, only this time each $A_i$ has a distinguished element (usually denoted "0"), and we're only looking at sequences with only finitely many nonzero terms. So, for instance, the direct sum of countably infinitely many copies of $\mathbb{N}$ is the set of all infinite sequences of natural numbers, which only use finitely many non-zero numbers. (I'm being slightly sloppy here, but oh well.)

The direct sum of countably many countable sets is countable. The indexing idea you've described, using primes, is a direct sum, not product, since each natural number only has finitely many prime factors.

• Makes perfect sense! – Rudi_Birnbaum Apr 15 '16 at 17:23
• To elaborate a little, there is a concept of p-adic numbers (think of an extension of the natural numbers, only you are allowed to multiply an infinite number of primes, thereby turning the direct sum into a direct product). And they are indeed uncountable. See: en.wikipedia.org/wiki/P-adic_order and en.wikipedia.org/wiki/P-adic_number – Alon Navon Apr 15 '16 at 17:26

The problem is that if you use the primes as indices and the powers as natural number valued component, you'll have only a finite number of components not equal to 0.

In other words, you can code finite sequences of natural numbers of arbitrary length, but not infinite sequences