1.2 Quantifiers

Recall that a formula is a statement whose truth value may depend on the values of some variables. For example,

"$x\le 5 \land x> 3$''

is true for $x= 4$ and false for $x= 6$. Compare this with the statement

"For every $x$, $x\le 5 \land x>3$,''

which is definitely false and the statement

"There exists an $x$ such that $x\le 5 \land x>3$,''

which is definitely true. The phrase "for every $x$'' (sometimes "for all $x$'') is called a universal quantifier and is denoted by $\forall x$. The phrase "there exists an $x$ such that'' is called an existential quantifier and is denoted by $\exists x$. A formula that contains variables is not simply true or false unless each of these variables is bound by a quantifier. If a variable is not bound the truth of the formula is contingent on the value assigned to the variable from the universe of discourse.

We were careful in section 1.1 to define the truth values of compound statements precisely. We do the same for $\forall x\,P(x)$ and $\exists x\,P(x)$, though the intended meanings of these are clear.

The Universal Quantifier

A sentence $\forall x\,P(x)$ is true if and only if $P(x)$ is true no matter what value (from the universe of discourse) is substituted for $x$.

Example 1.2.1

$\bullet$ $\forall x (x^2\ge 0)$, i.e., "the square of any number is not negative.''

$\bullet$ $\forall x\,\forall y (x+y=y+x)$, i.e., the commutative law of addition.

$\bullet$ $\forall x\,\forall y\,\forall z ((x+y)+z=x+(y+z))$, i.e., the associative law of addition.

$\square$

The "all'' form. The universal quantifier is frequently encountered in the following context: $$\forall x (P(x)\implies Q(x)),$$ which may be read, "All $x$ satisfying $P(x)$ also satisfy $Q(x)$.'' Parentheses are crucial here; be sure you understand the difference between the "all'' form and $\forall x\,P(x)\implies \forall x\,Q(x)$ and $(\forall x\,P(x))\implies Q(x)$.

The latter formula might also be written as $\forall x\,P(x)\implies Q(x)$, which is to say that the universal quantifier has higher precedence than the conditional; to avoid misunderstanding, it is best to include the parentheses. The meaning of this formula might not be clear at first. The $x$ in $P(x)$ is bound by the universal quantifier, but the $x$ in $Q(x)$ is not. The formula $(\forall x\,P(x))\implies Q(x)$ has the same meaning as $(\forall x\,P(x))\implies Q(y)$, and its truth depends on the value assigned to the variable in $Q(\cdot)$.

Example 1.2.2

$\bullet$ $\forall x$ ($x$ is a square $\implies$ $x$ is a rectangle), i.e., "all squares are rectangles.''

$\bullet$ $\forall x$ ($x$ lives in Walla Walla $\implies$ $x$ lives in Washington), i.e., "every person who lives in Walla Walla lives in Washington.''

$\square$

This construction sometimes is used to express a mathematical sentence of the form "if this, then that,'' with an "understood'' quantifier.

Example 1.2.3

$\bullet$ If we say, "if $x$ is negative, so is its cube,'' we usually mean "every negative $x$ has a negative cube.'' This should be written symbolically as $\forall x ((x< 0)\implies (x^3< 0))$.

$\bullet$ "If two numbers have the same square, then they have the same absolute value'' should be written as $\forall x\,\forall y ((x^2=y^2)\implies (\vert x\vert = \vert y\vert))$.

$\bullet$ "If $x=y$, then $x+z=y+z$'' should be written as $\forall x\,\forall y\,\forall z ((x=y)\implies (x+z=y+z))$.

$\square$

If $S$ is a set, the sentence "every $x$ in $S$ satisfies $P(x)$'' is written formally as $$\forall x ((x\in S)\implies P(x))$$ For clarity and brevity, this is usually written $\forall x\,{\in}\, S\,(P(x))$. To understand and manipulate the formula $\forall x\,{\in}\,S\, (P(x))$ properly, you will sometimes need to "unabbreviate'' it, rewriting it as $\forall x ((x\in S)\implies P(x))$.

Example 1.2.4

$\bullet$ $\forall x\in [0,1] (\sqrt x\ge x)$ stands for $\forall x (x\in [0,1]\implies \sqrt x\ge x).$

$\bullet$ $\forall x< 0 (\vert x\vert =-x)$ stands for $\forall x (x< 0\implies \vert x\vert = -x).$

$\square$

The Existential Quantifier

A sentence $\exists x\,P(x)$ is true if and only if there is at least one value of $x$ (from the universe of discourse) that makes $P(x)$ true.

Example 1.2.5

$\bullet$ $\exists x (x \ge x^2)$ is true since $x=0$ is a solution. There are many others.

$\bullet$ $\exists x\,\exists y (x^2+y^2=2xy)$ is true since $x=y=1$ is one of many solutions.

$\square$

The "some'' form. The existential quantifier is frequently encountered in the following context: $$\exists x\ (P(x)\land Q(x)),$$ which may be read, "Some $x$ satisfying $P(x)$ also satisfies $Q(x)$.''

Example 1.2.6

$\bullet$ $\exists x\, \hbox{($x$ is a professor $\land$ $x$ is a republican)}$, i.e., "some professor is a republican.''

$\bullet$ $\exists x\, \hbox{($x$ is a prime number $\land$ $x$ is even)}$, i.e., "some prime number is even.''

$\square$

It may at first seem that "Some $x$ satisfying $P(x)$ satisfies $Q(x)$'' should be translated as $$\exists x (P(x)\implies Q(x)), $$ like the universal quantifier. To see why this does not work, suppose $P(x)=\hbox{"$x$ is an apple''}$ and $Q(x)=\hbox{"$x$ is an orange.''}$ The sentence "some apples are oranges'' is certainly false, but $$\exists x (P(x)\implies Q(x)) $$ is true. To see this suppose $x_0$ is some particular orange. Then $P(x_0)\implies Q(x_0)$ evaluates to $\hbox{F}\implies \hbox{T}$, which is T, and the existential quantifier is satisfied.

We use abbreviations of the "some'' form much like those for the "all'' form.

Example 1.2.7

$\bullet$ $\exists x< 0 (x^2=1)$ stands for $\exists x ((x< 0) \land (x^2=1))$

$\bullet$ $ \exists x\in [0,1] (2x^2+x =1)$ stands for $ \exists x ((x\in [0,1])\land (2x^2+x=1))$ $\square$

If $\forall$ corresponds to "all'' and $\exists$ corresponds to "some'' do we need a third quantifier to correspond to "none''? As the following shows, this is not necessary:

Example 1.2.8

$\bullet$ "No democrats are republicans,'' can be written $\forall x$ ($x$ is a democrat $\implies$ $x$ is not a republican).

$\bullet$ "No triangles are rectangles,'' can be written $\forall x$ ($x$ is a triangle $\implies$ $x$ is not a rectangle).

$\square$

In general, the statement "no $x$ satisfying $P(x)$ satisfies $Q(x)$'' can be written $$\forall x (P(x)\implies \lnot Q(x)).$$ (You may wonder why we do not use $\lnot \exists x\,(P(x)\land Q(x))$. In fact, we could—it is equivalent to $\forall x (P(x)\implies \lnot Q(x))$.)

Exercises 1.2

In these problems, assume the universe of discourse is the real numbers.

Ex 1.2.1 Express the following as formulas involving quantifiers:

a) Any number raised to the fourth power is non-negative.

b) Some number raised to the third power is negative.

c) The sine of an angle is always between $+1$ and $-1$.

d) The secant of an angle is never strictly between $+1$ and $-1$.

Ex 1.2.2 Suppose $X$ and $Y$ are sets. Express the following as formulas involving quantifiers.

a) Every element of $X$ is an element of $Y$.

b) Some element of $X$ is an element of $Y$.

c) Some element of $X$ is not an element of $Y$.

d) No element of $X$ is an element of $Y$.

Ex 1.2.3 Recall (from calculus) that a function $f$ is increasing if $$ \forall a \forall b (a< b\implies f(a)< f(b)) $$ Express the following definitions as formulas involving quantifiers:

a) $f$ is decreasing.

b) $f$ is constant.

c) $f$ has a zero.

Ex 1.2.4 Express the following laws symbolically:

a) the commutative law of multiplication

b) the associative law of multiplication

c) the distributive law

Ex 1.2.5 Are the following sentences true or false?

a) $\forall x \forall y (x< y\implies x^2< y^2)$

b) $\forall x \forall y \forall z\ne 0 (xz=yz\implies x=y)$

c) $\exists x< 0 \exists y< 0 (x^2+xy+y^2=3)$

d) $\exists x \exists y \exists z (x^2+y^2+z^2=2xy-2+2z)$

Ex 1.2.6 Suppose $P(x)$ and $Q(y)$ are formulas.

a) Is $\forall x \forall y (P(x)\implies Q(y))$ equivalent to $\forall x(P(x)) \implies \forall y(Q(y))$?

b) Is $\exists x \exists y (P(x)\land Q(y))$ equivalent to $\exists x(P(x)) \land \exists y(Q(y))$?