1
$\begingroup$

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

  1. $\mathbb{N}$ is countable
  2. My set can be written as $\mathbb{N} + \sqrt{2\mathbb{N}}$
  3. 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?

$\endgroup$
6
  • 1
    $\begingroup$ If $(a,b)=(3,2)$ and $(c,d)=(1,8)$, you have $5=a+\sqrt{2b}=c+\sqrt{2d}$. So your application $\varphi$ is not defined. $\endgroup$
    – Kelenner
    Mar 15, 2017 at 13:19
  • $\begingroup$ @Kelenner so is the set not countable? Or is there an alternative method I should use to prove it is countable? $\endgroup$
    – m0meni
    Mar 15, 2017 at 13:20
  • $\begingroup$ Let $A$ be your set. You can define a surjection $f$ from $B=\mathbb{N}\times\mathbb{N}$ to $A$ by putting $f(a,b)=a+\sqrt{2b}$. As an image of a countable set is (at most) countable, you are done. $\endgroup$
    – Kelenner
    Mar 15, 2017 at 13:27
  • 1
    $\begingroup$ Suppose you have a surjection $f$ from a countable set $B$ to a set $A$. For each $a\in A$, you can choose a $b_a\in B$ such that $f(b_a)=a$(because $f$ is surjective). Note $C$ the union of all $b_a, a\in A$. Then the restriction $g$ of $f$ to $C$ is a bijection of $C$ on $A$. As $C$ is a part of $B$, hence (at most) countable, you have your bijection. $\endgroup$
    – Kelenner
    Mar 15, 2017 at 13:34
  • 1
    $\begingroup$ In the problem description you say 'I have to prove that the following set is countable' but in the title you say 'Find a bijection $\varphi(a+\sqrt{2b})=(a,b)$ t0 prove set countable'. That's not the same. You can prove countability by proving the bijection exists but not necessarily by finding it explicitly. And as @Kelenner shows, a function (let alone a bijection) in the given form can not exist. $\endgroup$
    – CiaPan
    Mar 15, 2017 at 13:39

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
5
  • $\begingroup$ Seems like the map isn't injective if you look to the comment on the question itself...is there an alternative answer? $\endgroup$
    – m0meni
    Mar 15, 2017 at 13:23
  • $\begingroup$ No, this is just the wrong map. Look at the map given at your linked question. (I suppose the root sign got too long, is this possible?) $\endgroup$ Mar 15, 2017 at 13:35
  • $\begingroup$ Ah I see where there was confusion...I was wondering how to apply the solution to the linked question to my own question, but it seems that's not possible. My real question is proving that the set I provided in my question is countable regardless of whether or not it uses the same methodologies of the answer to the linked question. $\endgroup$
    – m0meni
    Mar 15, 2017 at 13:37
  • 2
    $\begingroup$ I still have doubts. Why should you need to prove this? The set $\{ a+b\sqrt{2}\}$ is much more natural than the set $\{ a+\sqrt{2b}\}$. Is it possible, that there is a typo, $\sqrt{2b}$meaning $\sqrt{2}b$? $\endgroup$ Mar 15, 2017 at 13:38
  • $\begingroup$ ...yes...I completely misread it. Good catch. In which case this is a duplicate, and I'm not confused anymore. I'm not used to $n\sqrt{2}$ being written $\sqrt{2}n$. $\endgroup$
    – m0meni
    Mar 15, 2017 at 13:41
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .