# Definition using elementhood test $\{1,4,9,16, \ldots \}$ Best way?

I am working through "How to prove it: a structured approach".

4.Write definitions using elementhood tests for the following sets:

a) $$\{ 1,4,9,16,25,36,49,\ldots \}$$

For a. my first intuition was $$\{x ∈ \Bbb{N}\ |\ x^2\}$$ but then I realized it would not constitute a "test". So my question is what is the best way to express such a thing mathematically? My best attempt so far is $$\{x | \sqrt{x} ∈ \text{positive integers}\}.$$

Second point of confusion is on some website I found this answer which seems to introduce free variable $$y$$ making it true or false depending which $$y$$ is chosen. Basically if this following answer is correct, then I am REALLY confused. $$\{x ∈ \Bbb{R}\ |\ x = y^2 \text{ for some } y ∈ \Bbb N\}.$$

• $y$ is not a free variable. Yes, it is free in the equation "$x = y^2$", but in the larger context it is bound by the "for some $y \in \mathbb N$" that follows. So the statement "$x=y^2$ for some $y\in\mathbb N$" is not true or false depending on which $y$ is chosen, it is true if it is at all possible to choose a $y$ such that $x=y^2$.
– user856
Jul 29, 2012 at 2:24

You have it backwards. It's $\{n^2 \mid n\in\mathbb{N}\}$.

The notation $\{ A\mid B\}$ means the set of all things $A$ such that $B$ is true.

$\{x ∈ R \mid x = y^2\text{ for some }y ∈ \mathbb{N}\}$ is also OK. One can say, for example, that $9=y^2$ for some $y\in\mathbb{N}$ because $9=3^2$. Likewise $16=y^2$ for some $y\in \mathbb{N}$ because $16=4^2$, etc.

There's more than one way to specify your set - as such there's no single correct answer.

ncmathsadists's answer ($\{n^2|n\in\mathbb{N}\}$) shows the most common and useful notation, but I'm unsure whether it constitutes a test in the sense of your book.

Your answer involving the square root is fine as well, but as you will have noticed, it's not a great way to express the set as it obscures it rather than illustrating it.

The introduction of the free variable as in the second part in your is not necessary in everyday writing, but it comes in handy sometimes. Not everything imaginable that you can write between curly brackets makes sense as a set, see Russell's paradox. Mathematicians have studied these issues and came up with axioms for set theory. If you write your set like $\{x\in\mathbb{N}\ |\ \exists y\in\mathbb{N}: y^2=x\}$, it becomes immediately apparent that it is constructed by taking a set that you already know ($\mathbb{N}$) and sieving through it by a simple condition (your square roots are more complicated because they involve things outside the natural numbers, i.e. $\{x\in\mathbb{R^+}\ |\ \sqrt{x}\in\mathbb{N}\}$). Constructions like these are guaranteed to be sensible sets by the axiom scheme of separation.

The paragraph above may be a little beyond the scope of the material you're learning right now, but hopefully it convinces you that there is a point in rigorous notation.

This should do the job, $$\{n\cdot n| n\in\mathbb{N}\}.$$

• Cool, this is elegant. Could you also help with second part of my question? Jul 29, 2012 at 0:38
• @Eugene the second part is saying this: "sweep $x$ over $\mathbb{R}$. If $x$ is ever the square of some natural number $y$, add it to the set". It's really redundant, but it does work. Jul 29, 2012 at 0:43
• You can also write $\{x \in \mathbb{N}|\exists y \in \mathbb{N} {\rm s.t.} x = y^2\}$ Jul 29, 2012 at 0:43
• Hmm thanks. Is there any problem with { x | sqr(x) ∈ N } ? Jul 29, 2012 at 0:48
• that works too. Jul 29, 2012 at 0:48