# How to prove this set is denumerable?

I'm studying for an exam tomorrow and I've encountered a practice question that asks for me to explain why the set $$\mathbb{N} - \left\{n^2 \:|\: n \in \mathbb{N} \right\}$$ is denumerable. I understand that I'm supposed to find a surjective function from $\mathbb{N}$ to this set, but I can't think of what it would be.

Any help or hints would be appreciated. Thank you!

Edit: I also realize that since $\mathbb{N}$ is countably infinite and $\left\{n^2 \:|\: n \in \mathbb{N} \right\}$ is countably infinite, their difference should be countable -- however, I'm still not sure how to show that it's infinite.

-
If you want to show that the set is infinte. Here's a hint. The difference between consecuitive squares is $2n+1$. – Chris Dugale May 3 '13 at 2:57
@ChrisDugale So the difference between squares is at least 3, and since there are infinitely many squares, there are at least 3 times as many non-squares? And since the set of squares is infinite, then surely a set at least three times that size is infinite? Something like that? – Benjamin Kovach May 3 '13 at 3:02
Well, you can't say 'there are at least three times more' in the case where you're dealing with infinite sets. What you could do, however, is pick one member from each gap. In so doing, you've mapped the natural numbers injectively to the set you're interesed in--proving that that set is infinite. IF you're worried that there may be only finitely many squares, you can easially prove that tehre are infinitely many... Suppose that $a_1,...,a_n$ are all of the squares. Then consider $a_1*...*a_n$. So there are infinitely many 'gaps' as well. – Chris Dugale May 3 '13 at 3:16
@ChrisDugale Well, if there are finitely many squares, then there will be infinitely many nonsquares by default. – Karl Kronenfeld May 3 '13 at 3:21
Well yeah.. But, the above argument is meant to mimic Euclid's proof of the infitude of primes :D – Chris Dugale May 3 '13 at 5:18

Consider the set $\mathbb{N}_p = \{p\in\mathbb{N}: p\ is\ prime\}$. We know that $\mathbb{N}_p$ is countably infinite. So, we now notice that $x \in \{ n^2 : n \in\mathbb{N}\} \implies x \not\in \mathbb{N}_p$.
Hence, $\mathbb{N}_p \subset \mathbb{N} \setminus \{ n^2 : n \in \mathbb{N}\}$. So, we must conclude our set has infinite cardinality.
Here's a simple choice: $$f : \mathbb{N} \to \mathbb{N} \setminus \{n^2 : n \in \mathbb{N} \}$$ $$f(x) = \begin{cases} x^2+1 \qquad &x>0 \\ 3 \qquad &x=0 \end{cases}$$
After $0$ and $1$, the consecutive squares are always separated by at least 3, so we are sure that this function actually maps to non-squares.
We're not including $0$ in $\mathbb{N}$ in this class, so actually the function $f(x) = x^2 + 1$ works fine in my case. I was thinking of a way to build $\mathbb{N} - \left\{n^2 \: | \: n \in \mathbb{N} \right\}$ instead of a subset of it, which was the problem. Seeing subsets makes a lot more sense. Thanks for the reply. – Benjamin Kovach May 3 '13 at 3:16