In many of the most interesting mathematical formulas some variables are universally quantified and others are existentially quantified. You should be very careful when this is the case; in particular, the order of the quantifiers is extremely important. The universe in the following examples is the set of real numbers, except as noted.
Example 1.4.1 Compare these two valid sentences: $$ \exists x\,\forall y \,(x+y=y),\quad\quad \forall y\,\exists x\,(x+y=0). $$ In the first we require that $x$ be a fixed value that satisfies the equation regardless of the value of $y$; clearly $x=0$ will do. In the second formula, however, $x$ depends on $y$; if $y=3$, $x=-3$, if $y=0$, $x=0$. $\square$
Example 1.4.2 Compare these two sentences: $$ \forall x\,\exists y\,(y^3=x), \quad\quad \exists y\,\forall x\ (xy^3=- x). $$ The first is valid because given any $x$ we can set $y$ equal to the cube root of $x$. So as $x$ varies, $y$ also varies, that is, $y$ depends upon $x$. The second is valid because there is a single fixed value $y=-1$ which makes the equation $xy^3=-x$ valid, regardless of the value of $x$. $\square$
Example 1.4.3 Compare these two sentences: $$ \forall x\,\exists y \,(x< y), \quad\quad \exists y\,\forall x\,(x< y). $$ The first sentence is true and states that given any number there is a strictly larger number, that is, there is no largest number. The second sentence is false; it says that there is a single number that is strictly larger than all real numbers. $\square$
In general, if you compare $\exists y\,\forall x\,P(x,y)$ with $\forall x\,\exists y\,P(x,y)$ it is clear that the first statement implies the second. If there is a fixed value $y_0$ which makes $P(x,y)$ true for all $x$, then no matter what $x$ we are given, we can find a $y$ (the fixed value $y_0$) which makes $P(x,y)$ true. So the first is a stronger statement. As in example 1.4.3, it is usually the case that this implication cannot be reversed.
We turn to some examples using more variables:
Example 1.4.4 The sentence "between any two numbers is another number'' can be written $$ \forall x\,\forall y\,\exists z\,((x< y)\implies (x< z< y)). $$ Observe that $z$ depends in an essential way on both variables "to its left,'' namely, $x$ and $y$. The sentence is true if $U=\R$, but neither of these is true for $\R$: $\forall x\,\exists z\,\forall y\,((x< y)\implies (x< z< y))$, $\exists z\,\forall x\,\forall y\,((x< y)\implies (x< z< y))$. $\square$
Example 1.4.5 Suppose the universe of discourse is the integers. These are valid sentences: $$ \forall x\,\exists y\,\exists z\,(x=7y+5z),\quad\quad \forall x\,\exists y\, \forall z\,(z>x\Leftrightarrow z\ge y). $$ Consider the first sentence. If we know the value of $x$, we can choose $y=-2x$ and $z=3x$, so $7y+5z=-14x+15x=x$. Notice that $y$ and $z$ depend on $x$ in an essential way. Turning to the second, if we know $x$, we can choose $y$ to be the next integer, $x+1$. Any $z$ is strictly larger than $x$ if and only if it is at least as large as $y$. $\square$
We often need to form denials of sentences with mixed quantifiers. These are handled with De Morgan's laws, just as in section 1.3.
Example 1.4.6 The sentence $\exists x\,\forall y\,(x+y\ne 1)$ is false because its denial, $\forall x\,\exists y\,(x+y=1)$, is valid. (For any number $x$, let $y=1-x$.) $\square$
Example 1.4.7 The sentence $\forall y\,\exists x\,(x^2=y)$ is false because the denial of the sentence, $\exists y\,\forall x\,(x^2\ne y)$, is valid. (Let $y=-1$.) $\square$
Example 1.4.8 If the universe is the integers, the sentence $\forall x\,\exists y\,\exists z\,(x=4y+6z)$ is false. Its denial is $\exists x\,\forall y\,\forall z\,(x\ne 4y+6z)$. To see that this is valid, suppose $x$ is any odd number. For any values of $y$ and $z$, $4y+6z$ is even, so it does not equal $x$. $\square$
Exercises 1.4
Ex 1.4.1 Using the real numbers as the universe of discourse, describe why the following are valid:
a) $\exists x\,\forall y\,(xy=x^2)$
b) $\forall x\,\exists y\,(x^2+6xy+9y^2=0)$
c) $\exists y\,\forall x\,(x+y>xy)$
d) $\forall y\,\exists x\,(y-x=xy^2+1)$
Ex 1.4.2 Using the integers as the universe of discourse, describe why the following are valid:
a) $\forall x\,\exists y\,\forall z\,(z< x\iff z\le y)$
b) $\forall x\,\exists y\,\exists z\,(x= 8y+3z)$
c) $\exists x\,\forall y\,\forall z\,(x=yz\implies y=-z)$
d) $\exists x>1\,\forall y\,\exists z\,((y=xz) \lor (y=xz+1))$
Ex 1.4.3 Form the denials of the following and simplify using De Morgan's laws.
a) $\forall x\,\exists y\,((x+y=1)\land (xy\ne 0))$
b) $\exists y\,\forall x\,((x^2\ne y)\lor (x=y+1))$
c) $\forall x\,\exists y\,\forall z\,(x^2+y=0 \implies x< z^2)$
d) $\exists x\,\forall y\,\exists z\,(((x+y=z)\land (x< y))\implies ((x>z) \lor (y^2=z)))$
Ex 1.4.4 Explain why the two sentences at the end of example 1.4.4 are false.
Ex 1.4.5 Why is the following valid (where $U$ is the reals)? $$ \forall \epsilon{>}0\>\exists N{>}0\>\forall n\,(N< n\implies 1/n< \epsilon) $$
Ex 1.4.6 Using quantifiers, define what it means for $f\colon\R\to \R$ to be periodic (e.g., $\sin (x)$ is periodic). What does it mean for $f$ to fail to be periodic? ($\R$ denotes the real numbers.)
Ex 1.4.7 Recall the famous quote by Abraham Lincoln:
It is true that you may fool all the people some of the time; you can even fool some of the people all the time; but you can't fool all of the people all the time.
Let $F(x,y,z)$ mean "$x$ can fool $y$ at time $z$.'' Write Lincoln's statement symbolically. Identify some ambiguities in Lincoln's statement.