Square of Natural numbers is countable
Andrew Henderson 
Determine whether or not the below set
$A=\{a^2|a \in \mathbb{N}\}$ is countable.
I think the set of squares of natural numbers is countable and I can use the below mapping
$f(N)=N^2$
$1\mapsto1\\2\mapsto4\\3\mapsto9\\4\mapsto16\\.\\.\\.$
Am I correct in my approach?
$\endgroup$ 32 Answers
$\begingroup$Firstly, formally define $f$, as follows; $f:\mathbb{N}\to A$ is defined by $f(n)=n^2$, for all $n\in\mathbb{N}$. Now, you just have to prove $f$ is a bijection from $\mathbb{N}$ to $A$. To do so, show it's injective and surjective; that is, show that if $f(a)=f(b)$ then $a=b$ and for every $c\in A$ there's some $d\in\mathbb{N}$ such that $f(d)=c$.
Now that you've found a bijection from $\mathbb{N}$ to $A$, you can conclude $A$ is countable.
$\endgroup$ 2 $\begingroup$You are right. A set $X$ is countable if, and only if, there exists a mapping between the set of natural numbers and $X$. You've done exactly that!
Now, as Yuval Gat has said, you need to prove that your function $f$ is indeed bijective:
- It is injective, because if there are $a$ and $b$ such that $f(a)=f(b)$, then $a^2=b^2$, so $a= \pm b$, but $a$ and $b$ are both naturals, so the only possibility is $a=b$
- It is surjective, because if $y \in A$, then $\exists x \in \mathbb{N}$ such that $x^2=y$. Therefore $y = f(x)$, in other words, $f \in Im(f)$
Of course there are simpler arguments (for instance, every subset of a countable set is countable), but of course this depends on what previous results you're "allowed" to use
$\endgroup$
