Proving Prime Integers are countably infinite I've been doing some work with cardinality of sets, and ran into an example I thought was interesting. In proving that the set of prime numbers is a countably infinite set, I've started that showing that the set of prime numbers (integers) $\mathbb{P}$ is a subset of $\mathbb{N}$. Obviously the natural numbers $\mathbb{N}$ can be mapped one-to-one to itself ($1$ to $1$, $2$ to $2$, etc.), so it is a countably infinite set. Following from this, since $\mathbb{P}$ is a subset of a countably infinite set $\mathbb{N}$, then $\mathbb{P}$ must be a countably infinite set as well.

Is this enough information to show $\mathbb{P}$ is a countably infinite set, or must I show a concrete mapping for $\mathbb{P}$?
One way of proving that a subset of $A \subset \Bbb N$ is countably infinite is by demonstrating that it satisfies the following property,

$\tag 1 (\forall F \subset A) \, \bigr[ \, \text{IF } F \text{ if finite THEN } (\exists x \in \Bbb N) \, [x \notin F \text{ and } x \in A] \, \bigr ]$

See also

$\quad$ Subset of a countable set is itself countable

Now let $\mathbb{P}$ denote the set of prime numbers and let $F$ be any finite subset of $\mathbb{P}$.

If $|F| = 0$ then $2 \notin F$ but $2 \in \Bbb P$. 

if $|F| = n \gt 0$ then $F = \{p_1,p_2,\dots\,p_n\}$. Set

$\quad \displaystyle {a = (\prod_{1 \le i \le n} p_i) + 1} $

Using Euclidean division one readily shows that $p_i \nmid a$ for any subscript $i$. So if $q$ is any prime factor of $a$ then $q \ne p_i$ for any subscript $i$. So $q \notin F$ but $q \in \Bbb P$.



The above proof 'gears' Euclid's (direct) proof to the OP's requested set theoretic setting.
One way of proving that a subset of $A \subset \Bbb N$ is countably infinite is by demonstrating that it satisfies the following property,

$\tag 1 (\forall F \subset A) \, \bigr[ \, \text{IF } F \text{ if finite THEN } (\exists x \in \Bbb N) \, [x \notin F \text{ and } x \in A] \, \bigr ]$

See also

$\quad$ Subset of a countable set is itself countable

Now let $\mathbb{P}$ denote the set of prime numbers and let $F$ be any finite subset of $\mathbb{P}$.

If $|F| = 0$ then $2 \notin F$ but $2 \in \Bbb P$. 

if $|F| = n \gt 0$ then $F = \{p_1,p_2,\dots\,p_n\}$. Set

$\quad \displaystyle {a = (\prod_{1 \le i \le n} p_i) + 1} $

Using Euclidean division one readily shows that $p_i \nmid a$ for any subscript $i$. So if $q$ is any prime factor of $a$ then $q \ne p_i$ for any subscript $i$. So $q \notin F$ but $q \in \Bbb P$.



The above proof 'gears' Euclid's (direct) proof to the OP's requested set theoretic setting.