Let P be the set of all prime numbers. Prove that $| \mathbb{P}| = |\mathbb{N}|$

Question

I am trying to prove a bijection between the two. I know it is one to one, since if

$f: \mathbb{N}\to \mathbb{P}$

$f(n)$ = nth number prime

How do you prove it is onto?

Answer 1

You do not need to prove that it is onto.

By the Schröder–Bernstein Theorem, if you find an injection $f : \mathbb{N} \rightarrow \mathbb{P}$ and another injection $g : \mathbb{P} \rightarrow \mathbb{N}$, your result will follow.

Define $f(n) = \text{the } n^{\text{th}} \text{ prime number}$

Define $g(n) = \text{the } n^{\text{th}} \text{ number}$.

Since $f$ and $g$ are injective, $|\mathbb{N}| = |\mathbb{P}|$, we are done.