# Show that a set is countable

I have to show that the set $B=\{n^2 + m^2 : n, m \in\mathbb N\}$ is countable. I know that i need to find a injection or a bijection from the set $B$ to the natural numbers, but i don't know how. $n^2+m^2$ is again a natural number, but this function is not injective, because for example $1^2+2^2=2^2+1^2$. So we have a problem when $m$ differs from $n$. Can anyone help me with this?

• please check my edit. You speak of 'measurable'. Don't you mean 'countable'? – drhab Sep 28 '14 at 11:34
• Sorry, yes i do! – mathstudent Sep 28 '14 at 12:03
• Well, edit and repair then. Is my edit okay? – drhab Sep 28 '14 at 12:05
• Yes, thank you. – mathstudent Sep 28 '14 at 12:14

You want an injection $B\rightarrow\mathbb N$, right?

Well, note that $B\subset\mathbb N$.

Then prescribe $\iota:B\rightarrow\mathbb N$ by $k\mapsto k$ (the inclusion).

It is evident that $\iota$ is injective.

• What du mean with prescribe? – mathstudent Sep 28 '14 at 12:13
• The rule for $\iota$ is that it 'sends' element $k\in B$ to element $k\in\mathbb N$. In other notation: $\iota(k)=k$ for each $k\in B$. – drhab Sep 28 '14 at 12:15
• @mamo By prescribe, he just means "Let's define the inclusion map frop $B \to \mathbb{N}$". And this is injective because we have $\iota(x) = \iota(y) \implies x = y$ because $\iota(x) = x$ for all $x \in B$. – layman Sep 28 '14 at 12:19
• You are welcome. I am glad to help. – drhab Sep 28 '14 at 12:28

There is an injection of $N$ into $B$ ($n \mapsto n^2+1$) and an injection of $B$ into $N$ (the identity). Intuitively, that means that $B$ is both larger than $N$ and smaller than $N$. Finish off with Bernstein's theorem (http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theorem) to conclude that $B$ and $N$ are equipollent.

Without going to these lengths, any infinite subset of $N$ is bijective with $N$. The proof is easy and constructive, so you could even transpose it to your set $B$ :

let $x_0 = \min B$

then $x_1 = \min B - \{x_0\}$

... $x_n = \min B - \{x_0,...,x_{n-1}\}$

Every $x_k$'s existence is due to the fact that $B$ is not finite and that every subset of $N$ has a unique min.

And of course $n \mapsto x_n$ is a bijection between $B$ and $N$.

• What do you mean with an injection of B into N? – mathstudent Sep 28 '14 at 12:15
• $b \mapsto b$ is an injection from $B$ to $N$. – Alexandre Halm Sep 28 '14 at 12:17