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?

  • $\begingroup$ please check my edit. You speak of 'measurable'. Don't you mean 'countable'? $\endgroup$ – drhab Sep 28 '14 at 11:34
  • $\begingroup$ Sorry, yes i do! $\endgroup$ – mathstudent Sep 28 '14 at 12:03
  • $\begingroup$ Well, edit and repair then. Is my edit okay? $\endgroup$ – drhab Sep 28 '14 at 12:05
  • $\begingroup$ Yes, thank you. $\endgroup$ – 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.

  • $\begingroup$ What du mean with prescribe? $\endgroup$ – mathstudent Sep 28 '14 at 12:13
  • $\begingroup$ 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$. $\endgroup$ – drhab Sep 28 '14 at 12:15
  • $\begingroup$ @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$. $\endgroup$ – layman Sep 28 '14 at 12:19
  • $\begingroup$ You are welcome. I am glad to help. $\endgroup$ – 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$.

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

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.