Proof that Cardinality of Primes is Cardinality of Natural Numbers

Question

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?

Answer 1

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.

Answer 2

I assume that when you say prime numbers, you mean positive prime numbers in $\Bbb Z$.

The set of prime numbers $\Bbb P$ is well ordered, because it is a subset of the set of natural numbers. That is, any non-empty subset of $\Bbb P$ has a minimum. Define $\Bbb P_0=\Bbb P$ and $$\Bbb P_{n+1}=\Bbb P_n-\{\min \Bbb P_n\}$$ Now define the $n+1$-th prime number as the minimum of $\Bbb P_{n}$.

Answer 3

The proof is complete and the term $n+1^{st}$ prime makes perfect sense because the set of primes is a totally ordered set in which the well-ordering principle works. Thus the proof does not need any alteration.

However, if you like to add comments to the proof to clarify the above mentioned points, you may do so.