I need to prove that the cardinality of the set of prime numbers is the same as the cardinality of the set of natural numbers. This is the proof I came up with:
$\mathbb{P}\subseteq \mathbb{N}\Rightarrow |\mathbb{P}|\le |\mathbb{N}|\Rightarrow\exists f:\mathbb{P}\to \mathbb{N}$ such that $f(x)=x\Rightarrow f$ is an injection.
Since $\mathbb{P}\subseteq \mathbb{N}$, then $\exists g:\mathbb{P}\to \mathbb{N}$ such that $g(n)$ gives the $n+1^{th}$ prime. Hence $g$ is an injection. By the Schroeder-Bernstein Theorem, then $|\mathbb{P}|=|\mathbb{N}|$
However, I think there's a problem; simply knowing that there isn't a finite number of primes isn't good enough to know that the phrase "$n+1^{th}$ prime" makes any sense.
How can I correct this proof? Do I need a new function, $g$, or can it be worded more carefully to avoid this problem? If I can still use $g$, what else do I need to show?
Best Answer
All you need is to use two simple facts: one is that there are infinitely many primes, and the second fact is that every nonempty set of natural numbers has a minimum. So look at the set of prime numbers $\mathbb{P}$. It is a nonempty subset of $\mathbb{N}$, so it has a minimum. Name the minimal element $p_1$. Now look at $\mathbb{P}\setminus \{p_1\}$. It is still a nonempty subset of $\mathbb{N}$ (if it was empty then we would get there is only one prime which is a contradiction) so it has a minimum, call it $p_2$. Now look at $\mathbb{P}\setminus\{p_1,p_2\}$. Still a nonempty subset of $\mathbb{N}$ so it has a minimum, call it $p_3$. Continue that way and you will prove by induction that the phrase "$n+1$th prime" actually makes sense for all $n\in\mathbb{N}$. And then just define the same function $g$ like before.