1
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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 \} $$

$\endgroup$
5
  • $\begingroup$ 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. ) $\endgroup$ Commented Mar 6, 2017 at 12:41
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Mar 6, 2017 at 13:33
  • $\begingroup$ 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$ $\endgroup$ Commented Mar 6, 2017 at 13:57
  • 1
    $\begingroup$ @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$. $\endgroup$ Commented Mar 6, 2017 at 14:00
  • 1
    $\begingroup$ 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). $\endgroup$ Commented Mar 6, 2017 at 14:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.