Proof | Random Walks

I made the claim in a post last week that the set of irrationals of the form $a+b\sqrt{c}$ is countable. I said that pretty quickly, without justification. I’ve never proved statements like this before, but here I’m going to try.

Theorem. The set of irrationals of the form $a+b\sqrt{c}$ , with $a,b \neq 0,c>0\in\mathbb{Q}$ , is countable.

Proof. Consider the set of irrationals of the form $a+b\sqrt{c}$ , with $a,b \neq 0,c >0\in\mathbb{Q}$ . More formally, define

$\mathbb{I}=\left\{a+b\sqrt{c}\in\mathbb{R}: a,b \neq 0,c>0\in\mathbb{Q}\right\}$

And also require that $c$ is ‘square free’–that is, we require that neither the numerator or denominator of $c$ contain factors that are perfect squares. So $a+b\sqrt{c}$ is in ‘simplest’ form. We aim to show that $\mathbb{I}$ is countable.

Now, consider the function

$\mathbb{I} \overset{f}{\rightarrow} \mathbb{Q}^3$

defined

$f(a+b\sqrt{c})=(a,b,c)$

This function is one-to-one since we require $c$ to be in simplest form–that is, the image of any number $a+b \sqrt{c}$ under $f$ is unique. So $f$ is an injection from $\mathbb{I}$ into $\mathbb{Q}^3$ .

We know that $\mathbb{Q}$ is countable. Since a finite Cartesian product of countable sets is countable, $\mathbb{Q}^3$ must also be countable. And we have constructed a function $f$ which is an injection from $\mathbb{I}$ into $\mathbb{Q}^3$ . So the cardinality of $\mathbb{I}$ must be no greater than the cardinality of $\mathbb{Q}^3$ . Thus $\mathbb{I}$ must also be countable, as desired.