# Free Variables in Set Builder Notation

My math textbooks says the following set can not exist:

$$\{\text{ y : y = 2x for each x }\in \mathbb{N} \}$$

Because $y = 2 \cdot 1 = 2$ and $4 = 2 \cdot 2 = 4$.

My understanding of this argument is that, for their reading of set builder notation, y is not a free variable. That is to say, the set builder notation claims that there is one y for every x in the natural numbers.

In other words:

$$(\ \forall x \in \mathbb{N} )\ (\ !\exists y\ )\ (\ y = 2x\ )$$

where $!\exists$ is read "there exists exactly one". Which seems strange to me, because--isn't $\{\ y : definition\ \}$ meant to both create a set of objects and a free variable that can range over the entire set? ( In other words, y is by definition not fixed. )

Is my understanding of their reading of the set builder notation correct? Is their reading of set builder notation standard across mathematics?

The set builder notation you're using here works like $$\{ y \mid \text{some property of }y \}$$ In order to find out what the elements of your set is, you take (in principle) each possible $y$ one by one and ask whether that particular $y$ has the $\text{some property}$.

In this case the property is (presumably; writing "for all" after the formula it applies to is not good logic syntax and invites mistakes): $$(\forall x\in\mathbb N)\; y=2x$$ This property has $y$ as a free variable -- as it well should; every nontrivial property of an $y$ must be denoted by a formula where $y$ is free. The set builder notation binds the $y$, but when you're just looking at the subformula $(\forall x\in \mathbb N)\; y=2x$, then $y$ is free there.

(A variable is not "free" or "bound" in a vacuum; it always depends on which context you're considering it in. Taking a larger context -- such as the entire set builder rather than just the condition itself -- can cause the variable to be bound where it was free).

For the above property, no matter which particular $y$ we try with, the property is not true -- $y$ cannot equal all of $0, 2, -2, 4,$ etc. at once.

Your textbook is wrong, however, when it claims that the set "cannot exist" -- it exists perfectly well; it just happens to be the empty set.

The set you're thinking about would be written $$\{ y\mid (\exists x\in \mathbb N)\;y=2x \}$$ or (appealing to the axiom of replacement instead of selection) $$\{ 2x \mid x\in \mathbb N \}$$

• Thank you for taking the time to write such a well worded response! Out of curiosity, using notation such as $(\forall x \in \mathbb{N}) y = 2x$, how does one distinguish between the statements "For all x in the natural numbers, there exists a single y for which y = 2x is true" and "Each x in the natural numbers has a corresponding y such that y = 2x is true"? I can write this up in a separate post, if that's appropriate. (I'll search for an answer, as well. ) – StudentsTea Mar 6 '17 at 12:41
• @StudentsTea: I think the distinction you're thinking about is between $(\forall x\in\mathbb N)(\exists y\in\mathbb N)y=2x$ (which is true) and $(\exists y\in\mathbb N)(\forall x\in\mathbb N)y=2x$ (which is false). But the two English sentences in your comment both mean the first of these; the second would be "There exists a single $y$ such that for each $x$, $y=2x$ is true". The order of the quantifiers matter -- a variable bound with $\exists y$ can depend on everything that is quantified to the left of $\exists y$, but must be the same for all choices to the right of it. – Henning Makholm Mar 6 '17 at 13:33
• Thank you again for such a well worded response. How would the statement "There exists a single $y$ such that for each $x$, $y=2x$ is true" be properly written? $(\ ! \exists y \in \mathbb{N} \ )(\ \forall x \in \mathbb{N} \ ) y = 2x$ – StudentsTea Mar 6 '17 at 13:57
• @StudentsTea: Sorry, I missed the implications of "single" in your sentence. We represent "there exists at least one $y$ such that ..." as $\exists y$ and "there exists one -- but only one -- $y$ such that ..." as $\exists! y$. – Henning Makholm Mar 6 '17 at 14:00
• When I used "single" in my first comment, I just intended it to mean "and this $y$ works for all $x$" -- not that there couldn't be other $y$s with this property. (In the actual example the difference doesn't matter, because there are in fact no $y$s that qualify). – Henning Makholm Mar 6 '17 at 14:02