Clarification on set definitions from How to Prove it (Velleman) Chapter 2.3

166 Views Asked by At

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.

  1. list elements in brackets $$\{1, 2, 3, 4\}$$
  2. 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.

1

There are 1 best solutions below

0
On

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").