Originally Posted by
Plato There are many different proofs of this theorem.
Each depends upon what you have to work with.
If you know that there is a one-to-one correspondence between the prime integers and the positive integers. Suppose that $\displaystyle \Theta :Z^ + \mapsto P$ is that mapping. Now if $\displaystyle A=\left\{ {z_1 ,z_2 ,z_3 , \cdots ,z_j } \right\}$ is a finite subset of $\displaystyle Z^+$ then consider the function $\displaystyle \varphi \left( {\left\{ {z_1 ,z_2 ,z_3 , \cdots ,z_j } \right\}} \right) = \prod\limits_{k = 1}^j {\Theta \left( {z_k } \right)} $. Now if we use the unique factorization theorem then the function $\displaystyle \varphi $ is one-to-one. Thus the set of all finite subset of $\displaystyle Z^+$ maps injectively into $\displaystyle Z^ + $. Thus it is countable.