I am reading the first two paragraphs of Chapter 2.3 in How to Prove It (Velleman) and I am unclear about why $x \in \{n^2 | n \in \Bbb{N}\}$ is the same as $\exists n \in \Bbb{N}(x = n^2)$
I will lay out Velleman's explanation and my understanding of it, I would love some feedback on if I'm thinking about this correctly.
For the reader, up until this point in the book, we know two ways to define sets.
- list elements in brackets $$\{1, 2, 3, 4\}$$
- use elementhood notation $$\{x \ |\ P(x)\}$$
Velleman suggests that it is common to replace the $x$ in front of the vertical line with a more complex expression. He uses the example of $S$, the set of perfect squares
$$S = \{n^2\ |\ n \in \Bbb{N}\}\tag{1}$$
He claims that (1) can be written as
$$S = \{x \ |\ \exists n \in \Bbb{N}(x=n^2)\}\tag{2}$$
Thus
$$S = \{n^2\ |\ n \in \Bbb{N}\} = \{x \ |\ \exists n \in \Bbb{N}(x=n^2)\}$$
At this point I'm still with Velleman. Replacing x before the vertical line with a more complex expression is intuitive. Putting the statement "x is a perfect square" into the form $\exists n \in \Bbb{N}(x=n^2)$ and defining the set S using that logical statement as an elementhood test - $S = \{x\ |\ \exists n \in \Bbb{N}(x=n^2)\}$ - makes sense (this question is a good discussion. on eq 2)
Velleman continues
and therefore $x \in \{n^2\ |\ n \in \Bbb{N}\}$ means the same thing as $\exists n \in \Bbb{N}(x = n^2)$
I am missing the jump to this final conclusion, here are my thoughts so far.
First thought
Perhaps a step Velleman is taking (and assumes reader will make) is that $x \in \{n^2\ |\ n \in \Bbb{N}\}$ is the same as $x \in \{x\ |\ \exists n \in \Bbb{N}(x = n^2)\}$. And then, using the following from Chapter 1.3,
in general, the statement $y \in \{x\ |\ P(x)\}$ means the same thing as P(y)...a statement about y but not x.
from this, we can see that $x \in \{x\ |\ \exists n \in \Bbb{N}(x = n^2)\}$ means the same thing as $\exists n \in \Bbb{N}(x = n^2)$, and then arrive at the conclusion.
Second thought (not entirely unrelated way of thinking about it)
$\exists n \in \Bbb{N}(x = n^2)$ and $x \in \{n^2\ |\ n \in \Bbb{N}\}$ are both statements about x, where x is a free variable. These statement can be evaluated to true or false, but that will depend on the value of x that is used. They will always evaluate to the same truth/false value, therefore they mean the same thing.
This is an intuitive explanation. Explicitly $\{n^2 | n \in \Bbb{N}\}$ is the set of all squares $\{0,1,2^2,3^2,4^2,\ldots\}$. If $x \in \{n^2 | n \in \Bbb{N}\}$ then that means $x$ is one of the squares, it can be $0$ or $1$ or $2^2$ or $3^2,4^2,\ldots$ We don't know exactly which one of them but we know at least the shape that $x$ must have. $x$ must be the square of something. That's what we formalize as $\exists n\in \mathbb{N}$ such that $x=n^2$.
Conversely if an element is of the form $x=n^2$ i.e. $\exists n\in\mathbb{N}$ such that $x=n^2$ ($n$ can be $0,1,2,3,\ldots$) then $x \in \{n^2 | n \in \Bbb{N}\}$.
Thus $x \in \{n^2 | n \in \Bbb{N}\}$ is the same as $\exists n\in \mathbb{N} (x=n^2)$ (the parenthesis here reads "such that").