# proving a simple function is bijective

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.

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?

-
How about sending n to x? – Espen Nielsen Nov 4 '12 at 13:03

Note that in fact your set is

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

$$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\,$ ...

-
how do I explain this function is infact bijective? – Nescio Nov 4 '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 4 '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 4 '12 at 13:28

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