# What's wrong with this proof about the cardinality of N^N?

Cantor's diagonalisation argument shows that $|N^N| = |R|$ so obviously $|N^N| > |N|$.

• $N^N$ is $N$ times itself, $N$ times. This is the set of $N$-tuples with elements in $N$.
• To prove that $|N^N| = |N|$ we need to find a bijection between $N$ and $N^N$, a function mapping an element of $N^N$ to an element of $N$.
• Elements $x$ of $N^N$ are of the form $x=(a_1, a_2, ..., a_i, ...)$ where the $a_i$s are elements of $N$.
• Consider the function $f(a_1, a_2,...a_i,...) = 2^{a_1}3^{a_2}...{p_i}^{a_i}...$ where $p_i$s are primes.
• This function is surjective because every natural number has a prime factorisation therefore every element in the range ($N$) is the image of at least one element in the domain ($N^N$)
• This function is injective because prime factorisation is unique so no natural number has two different prime factorisations. So $f(x_1) = f(x_2)$ only when $x_1=x_2$
• This function is injective and surjective therefore it is a bijection
• This proves that $|N^N| = |N|$
• But this is obviously wrong! What mistake have I made in this proof?
-

For example $(1,1,1,\cdots)\mapsto2\cdot3\cdot5\cdots$ doesn't define a natural.