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$.

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$.

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.

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

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$.

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

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

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$.

## 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.