Prove $\{m + \sqrt{2n} : m,n \in \mathbb{N}\}$ is countable I have to prove that the following set is countable $\{m + \sqrt{2n} : m,n \in \mathbb{N}\}$.
I did some searching and found a similar question here: Show that the set $A=\{ n+m\sqrt{2}:n,m\in\mathbb{Z} \}$ is countable, which gave me the following process to solve my own question


*

*$\mathbb{N}$ is countable

*My set can be written as $\mathbb{N} + \sqrt{2\mathbb{N}}$

*If I find a mapping $\mathbb{N} + \sqrt{2\mathbb{N}} \rightarrow \mathbb{N} \times \mathbb{N}$, I can prove my set is countable because the cartesian product of a countable set with itself is countable.


The only part I had difficulty understanding in that question is the following

a bijection $\varphi(a+b\sqrt{2})=(a,b)$ is simple to prove

In my case it'd be $\varphi(a+\sqrt{2b})=(a,b)$, but I'm not so sure what the "simple" proof for that bijection is. Could someone point me in the right direction?
 A: For $S=\{m + \sqrt{2n} : m,n \in \mathbb{N}\}$ there exists an injection $\mathbb N \to S$:
$$\mathbb N\ni m\mapsto m+2 = m+\sqrt{2\cdot 2}\in S$$
so $|\mathbb N| \le |S|$.
There exists also an injection $S\to\mathbb N$: for each number in $S$ choose the smallest possible $n$, then
$$S\ni m+\sqrt{2n}\mapsto 2^m3^n\in\mathbb N$$
so $|S| \le |\mathbb N|$.
Together they make $|\mathbb N| \le |S| \le |\mathbb N|$, so: $$|S| = |\mathbb N|$$
Compare Schröder–Bernstein theorem.
A: On should consider the map $\varphi (a+b\sqrt{2})=(a,b)$ of your link, and not $a+\sqrt{2b}$. This map
is obviously surjective, because $a+n\sqrt{2}$ is a preimage for $(a,b)$. The map is also injective, because $\varphi(a+b\sqrt{2})=\varphi(c+d\sqrt{2})$ implies that $(a,b)=(c,d)$, which gives $a+b\sqrt{2}=c+d\sqrt{2}$.
A: In fact to proove the set $S$ is countable you only need an injection of $S$ into $\mathbb N$ (or $\mathbb N^k$ or $\mathbb Z^k$ since all these are equinumerous).
The surjection is not necessary, it is only needed to prove that your set is actually not finite (to distinguish countable in a strict sense from finite), but generally proving that $S$ is infinite can be done by other means.

Also when you define your set by $S=\{ \text{1 element}=F(a_1,a_2,..,a_k) \mid (a_1,a_2,...,a_k)\in \mathbb N^k\}$ 
it doesn't matter how the actual element is built from these $(a_i)_i$, the sole fact that you use a schema of replacement gives you an injection $S\hookrightarrow\mathbb N^k$ thus the set $S$ is countable.
this is what Kelenner said too with other words : "an image of a countable set (by a function) is countable"

In fact when you define $T=\{m+\sqrt{2n}\mid (m,n)\in\mathbb N^2\}$, saying that for each couple $(m,n)$ you have exactly one element of $T$ is the injection in $\mathbb N^2$ you need so there is absolutely no more work to do.
If you really want to show that it is infinite, just notice that the trivial injection (i.e. identity) $\mathbb N\hookrightarrow T$ defines elements of $T$.
Note: in case of $T$ the reciprocal of the natural injection is not injective because $(m,n=2k^2)$ and $(m+2k,n=0)$ give the same $m+\sqrt{2n}$, it would be difficult to find a practical injection, and we don't need to, because we have proved non-finitude by a another way already.
