How do I prove the set of the equivalence classes of $R$ has the same cardinality as the set of all finite sets of primes? I have been stuck on this for a while now.
Given the equivalence relation $R$ over $\mathbb{Z^+}: aRb \leftrightarrow \exists q \in \mathbb{Q}(\frac{a}{b} = q^2) $ how does one prove that the set of its equivalence classes $B$ has the same cardinality as the set of all finite sets of primes $C$.
What I am looking for, is some kind of proof that $B$ is a countable set.
I tried to come up with a mapping function between the two, compare them both to something else but everything was without any meaningful result. Any help is greatly appretiated.
 A: Let $m$ and $n$ be two positive square-free integers (i.e., $p^2$ doesn't divide $n$ or $m$, for any prime $p$), and suppose that $mRn$.
If $mRn$, then there exists a rational $q$ such that $\frac{m}{n}=q^2$.
Now, we may assume $q>0$, and this rational number can be written as $q = \frac{r}{s}$, where $r,s$ are positive integers and $\gcd(r,s)=1$.
So we have
$$
r = p_1^{\alpha_1}\cdots p_k^{\alpha_k}
\quad\text{and}\quad
s = p_1^{\beta_1}\cdots p_k^{\beta_k},
$$
where $\alpha_i\beta_i=0$, that is, for each $I$, we can't have both $\alpha_i\neq0$ and $\beta_i\neq0$.
It follows that
$$ms^2=nr^2,$$
and so $r^2|m$ and $s^2|n$ (because $\gcd(r,s)=1$).
But then $p_i^{2\alpha_i}|m$ and $p_i^{2\beta_i}|n$.
Since $m$ and $n$ are square-free, it must be $\alpha_i = \beta_i =0$, for all $i$.
But that means $q=r=s=1$ and $m=n$.
So, if $m \neq n$ then they represent different classes.
Given that they are square-free, each number if fully determined by the (finite) set of primes that divide it.

Edit.
The reasoning above shows that each square-free positive integer is in a different class.
To finish the desired correspondence, one still has to prove that there are no other classes, i.e., that every $n \in \mathbb Z^+$ is related to some square-free one.
This follows from the fact that $nRnp^2$, for every prime $p$ and integer $n$.
Indeed, there exists $q \in \mathbb Q$ such that $\frac{np^2}{n}=q^2$: just take $q=p$.
