# Is the set of all prime numbers countable?

Define $A=\{n|n\text{ is prime number}\}.$ Then I wish to know whether the set is countable or not. Recall that a set $A$ is countable if $\mathbb{N}$ has the same cardinality as $A$. Now in order to show that both the sets $\mathbb{N}$ and $A$ have the same cardinality we must be able to construct a function $f:\mathbb{N}\to A$ such that $f$ is both $1-1$ and onto. I tried to think of some functions but couldn't come up with anything. Any ideas regarding this problem will be much appreciated.

• There are unlikely to be more prime numbers than natural numbers – Henry Nov 5 '16 at 18:20
• Oh! what a fool I am. We could simply use a theorem that states: if $A\subseteq\mathbb{N}$ then $A$ is either finite, empty or countable. Since $A$ is infinite (due to Euclid), non-empty we therefore, conclude that $A$ is a countable set. – nls Nov 5 '16 at 18:25
• Nevertheless, I would like to see a bijective function. – nls Nov 5 '16 at 18:28
• In one direction the function is the $n$th prime and in the other the prime counting function. There is a reason there are not useful closed forms – Henry Nov 5 '16 at 18:33
• Any infinite subset of $\mathbb{N}$ is countable, since every non-empty subset of $\mathbb{N}$ has a minimum. Or, simply, the map sending $n$ to $p_n$ (the $n$-th prime number) is clearly injective. – Jack D'Aurizio Nov 5 '16 at 19:10

HINT: Think about the map sending $n$ to the $n$th prime . . .
In general, you can prove that any infinite subset of $\mathbb{N}$ is countable by using the idea above. Suppose $A\subseteq\mathbb{N}$ is infinite. I want to argue that for every $n\in\mathbb{N}$, "the $n$th element of $A$" is something that makes sense. This is a proof by induction on $n$: show that for every $n\in \mathbb{N}$, there is exactly one element $a\in A$ such that $\vert \{b\in A: b<a\}\vert=n$. (I'm assuming "$0\in\mathbb{N}$" here; otherwise, replace "$<$" with "$\le$".)
Also, note that the definition of "countable" you give is not universally accepted: many texts (the majority, as far as I'm aware) define countable as "in bijection with some subset of $\mathbb{N}$," so that finite sets are countable.