# Proving a set to be countable

A set $$S = \left\lbrace \left( x, y \right) \vert x^2 + y^2 = \dfrac{1}{n^2}, \text{ where } n \in \mathbb{N} \text{ and either } x \in \mathbb{Q} \text{ or } y \in \mathbb{Q} \right\rbrace$$ is given. I need to prove that this is countable.

I have tried looking for a bijection $$f: \mathbb{Q} \rightarrow S$$ as $$f \left( x \right) = \left( x, y \right)$$ where $$y$$ is a fixed real number such that the property of the set is satisfied.

Clearly, this function is not even a surjection.

How should we define our bijection so that we prove $$S$$ is countable?

## 2 Answers

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.

• The way you have written the union for $S$, only takes into consideration when $x$ is rational and $y$ can be anything. What if it goes the other way round? – Aniruddha Deshmukh Dec 14 '18 at 4:52
• Or do you want to say that the final mapping would be $\left( x, y \right) \mapsto \left( n, x, 1 \right)$ if $x$ is rational and $\left( x, y \right) \mapsto \left( n, y, 2 \right)$ if $y$ is rational but $x$ is not. – Aniruddha Deshmukh Dec 14 '18 at 4:53
• Yes, you are right. I needed to duplicate the sets. It's done now. – Martin Argerami Dec 14 '18 at 4:58
• Why are we mapping it to $\left( \mathbb{N} \times \mathbb{Q} \times \left\lbrace 1, 2 \right\rbrace \right)^2$? I think $\left( \mathbb{N} \times \mathbb{Q} \times \left\lbrace 1, 2 \right\rbrace \right)$ should work with the mapping I defined in the comment. – Aniruddha Deshmukh Dec 14 '18 at 5:00
• I'm using the 1 and 2 to count the positive and negative roots. There is some overlapping, but it's not a big deal. The maps as you say also work, I think. – Martin Argerami Dec 14 '18 at 5:04

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?