2

This is more of a "How to write" question than a "help me solve" one, sorry if these are unaccepted/closed, let me know and I won't open anymore like this.

I need to prove that $A:=\{x\in \mathbb{N}|$ exists $n\in\mathbb{N}$ such that $x=n^2 \}$ is countable. This obviously requires me to prove that exists a bijective function from N to it. Which sounds very simple, but I don't really know how to write it.

Edit: Well, this is what I had written before asking:
Proof. We'll notice that this set is equal to $\left\{ n^{2}|n\in\mathbb{N}\right\}$ , since for each n we can find $n^{2}$ and say it's equal to $x$ .

In order to prove that a set is countable we need to find a bijective function from $\mathbb{N}$ to it. We'll look at:

$$f:\mathbb{N}\to \mathbb{N}^{2},f\left(n\right)=n^{2}$$

Since multiplication is well defined we can say this function is injective. Now how do I explain surjective?

amWhy
  • 209,954
Nescio
  • 2,426

2 Answers2

3

Note that in fact your set is

$$A:=\{n^2\;\;;\;\;n\in\Bbb N\}$$

so what about

$$f:\Bbb N\to A\;\;,\;\;f(n):=n^2\,\,?$$

Please pay attention to the fact that if instead $\,\Bbb N\,$ we'd have $\,\Bbb Z\,$ , the above function would not be $\,1-1\,$ ...

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • how do I explain this function is infact bijective? – Nescio Nov 04 '12 at 13:17
  • Did you get the hint why it is injective? Well, there you go! As for surjective: it follows in a straightforward way from the re-writing your set A as I did in my answer! If you're still having doubts, tell me where exactly, after you've done some self work. – DonAntonio Nov 04 '12 at 13:21
  • If you'll look at the edit you'll see that's exactly where I was when asking in the first place. Well, it's my fault for trying to post questions while on a bus. I got my answer I think , ty... – Nescio Nov 04 '12 at 13:28
2

Given $$A = \{ x \in \mathbb N \,|\, \exists n \in \mathbb N,\,\, x = n^2 \}$$ then the function $n \mapsto n^2$ is a bijection between $\mathbb N$ and $A$.

  • Injective: natural numbers are positive.
  • Surjective: given $x \in A$, there exists by definition of A some $n$ such that $n^2 = x$.
sperners lemma
  • 2,219