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:

Ex 1.4.2 Using the integers as the universe of discourse, describe why the following are valid:

Ex 1.4.3 Form the denials of the following and simplify using De Morgan's laws.

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.