Proving a set to be countable

Note that $x^2=\frac1{n^2}-y^2$ and $y^2=\frac1{n^2}-x^2$. So if $y$ is rational, then $x^2$ is rational as well, and likewise for $y^2$ if $x$ is rational.

Therefore you can define a surjection from the collection of all roots of rational numbers (which also includes all the rationals). So now comes the question, can you prove that this set is countable?


If you index on $x$ and $n$, you can do the following. Let $$ E_n=\mathbb Q\cap \left[-\tfrac1{n^2},\tfrac1{n^2}\right]. $$ This sets $E_n$ are countable, because they are subsets of $\mathbb Q$. Then $S=S_1\cup S_2$, where $$ S_1=\bigcup_{n\in\mathbb N}\bigcup_{x\in E_n}\left\{\left(x,\sqrt{\tfrac1{n^2}-x^2}\right)\right\}\cup\left\{\left(x,-\sqrt{\tfrac1{n^2}-x^2}\right)\right\} $$ $$ S_2=\bigcup_{n\in\mathbb N}\bigcup_{y\in E_n}\left\{\left(\sqrt{\tfrac1{n^2}-y^2},y\right)\right\}\cup\left\{\left(-\sqrt{\tfrac1{n^2}-y^2},y\right)\right\} $$ We can map this to a subset of $(\mathbb N\times\mathbb Q\times\{1,2\})^2$. And this last set is countable, so $S$ is countable.

The key fact is that subsets of countable sets are countable, and that finite cartesian products of countable sets are countable.