1

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?

21rw
  • 281
  • 1
    Actually your function is already onto. Arrange all primes in increasing order, then every prime has a unique position which can be identified by a natural number. But your function, sort of already assumes that $\Bbb{P}$ is countable so it appears a bit cyclical argument. – Anurag A Nov 14 '18 at 02:01

1 Answers1

4

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.

Ekesh Kumar
  • 3,500