Countability (show set is countable) Show that the set $\mathbb{Z}_+\times\mathbb{Z}_+$ is countable.?
To solve this you have to show a one to one correspondence.
$\mathbb{Z}_+\times\mathbb{Z}_+\to\mathbb{Z}_+$ Then my book recommends using $f(m,n) = 2^m\times3^n$ (or any other primes) to show it is one to one. 
Where do these numbers come from, how do you know to use primes? Where is the thinking behind this? 
 A: Supose $f(m,n)=f(p,q)$, then $2^m3^n=2^p3^q$. Note that $2$ and $3$ are different primes, if $p\neq m$ or $q\neq n$ then $2^m3^n\neq2^p3^q$, because of the Fundamental Theorem of Arithmetic, therefore it is necessary that $(p,q)=(m,n)$. We conclude that $f$ is injective.
A: It isn't important that you use the primes 2 or 3. The fact that there is a one to one correspondence between $\mathbb{Z}_+ \times \mathbb{Z}_+$ and $f(\mathbb{Z}_+,\mathbb{Z}_+)$ is a consequence of the unique factorization in $\mathbb{Z}$. The map
$$f: \mathbb{Z}_+ \times \mathbb{Z}_+ \to f(\mathbb{Z}_+,\mathbb{Z}_+) $$
is clearly surjective. It is also injective because $2^{n_1}3^{m_1}$ can only be equal to $2^{n_2}3^{m_2}$ when $n_1=n_2$ and $m_1=m_2$ because of unique factorization. Therefor there is a bijective correspondence between $\mathbb{Z}_+ \times \mathbb{Z}_+$ and $f(\mathbb{Z}_+,\mathbb{Z}_+)$. That last one is countable as a subset of the countable set $\mathbb{Z}_+$ and therefor also $\mathbb{Z}_+ \times \mathbb{Z}_+$ is countable.
