2
$\begingroup$

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?

  • 0
    How about sending n to x?2012-11-04

2 Answers 2

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

  • 0
    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...2019-03-12
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$.