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.

  • 2
    $\begingroup$ If you want to show that the set is infinte. Here's a hint. The difference between consecuitive squares is $2n+1$. $\endgroup$ – RougeSegwayUser May 3 '13 at 2:57
  • $\begingroup$ @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? $\endgroup$ – Benjamin Kovach May 3 '13 at 3:02
  • 1
    $\begingroup$ 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. $\endgroup$ – RougeSegwayUser May 3 '13 at 3:16
  • $\begingroup$ @ChrisDugale Well, if there are finitely many squares, then there will be infinitely many nonsquares by default. $\endgroup$ – Karl Kronenfeld May 3 '13 at 3:21
  • $\begingroup$ Well yeah.. But, the above argument is meant to mimic Euclid's proof of the infitude of primes :D $\endgroup$ – RougeSegwayUser 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.

  • $\begingroup$ 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. $\endgroup$ – Benjamin Kovach May 3 '13 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.