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?


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.

  • $\begingroup$ 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? $\endgroup$ – Aniruddha Deshmukh Dec 14 '18 at 4:52
  • $\begingroup$ 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. $\endgroup$ – Aniruddha Deshmukh Dec 14 '18 at 4:53
  • $\begingroup$ Yes, you are right. I needed to duplicate the sets. It's done now. $\endgroup$ – Martin Argerami Dec 14 '18 at 4:58
  • $\begingroup$ 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. $\endgroup$ – Aniruddha Deshmukh Dec 14 '18 at 5:00
  • $\begingroup$ 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. $\endgroup$ – 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?


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.