Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question

2 Answers 2

Can a natural number be the product of infinitely many primes?

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

share|improve this answer

The proof shows that the finite, or eventually zero, sequences are countable.

However if you have a sequence which is infinitely often non-zero then the product of infinitely many prime numbers is not a natural number anymore. Therefore the function is ill-defined.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.