Quantifiers

Here is a (true) statement about real numbers:

Every real number is either rational or irrational.

I could try to translate the statement as follows: Let

P = "x is a real number"

Q = "x is rational"

R = "x is irrational"

The statement can be expressed as the implication $P \ifthen (Q \lor R)$ .

The simple statements contain a variable x, and you might find it difficult to translate these statements without using a variable (or, what is the same thing, a pronoun). The reason is that the original statement is meant to apply to every element of a set --- in this case, every element of the set of real numbers.

You can see that I'm cheating in making my translation: "x is a real number" is not a single statement about a uniquely specified object "x". It is a different kind of statement than "$\pi$ is a real number", which talks about a specific real number $\pi$ .

I can use quantifiers to translate statements like these so as to capture this meaning. Mathematicians use two quantifiers:

Here are some examples which show how they're used.

Example. Let $P(x)$ mean "x likes pizza". Then:

$\forall x(P(x))$ means "Everyone likes pizza".

$\exists x(P(x))$ means "Someone likes pizza".

Note that if "Someone likes pizza" is true, it may be true that "Everyone likes pizza". On the other hand, if "Everyone likes pizza" --- and assuming that the set of people is nonempty --- it must be true that "Someone likes pizza".

$\lnot \forall x(P(x))$ means "Not everyone likes pizza".

$\lnot \exists x(P(x))$ means "No one likes pizza".

Again, if "Not everyone likes pizza", it may be true that "No one likes pizza". On the other hand, if "No one likes pizza", it {\it must} be true that "Not everyone likes pizza".

Note also that if `Not everyone likes pizza", it may be true that "Someone likes pizza".

Example. Translate each statement using universal or existential quantifiers. Then determine whether the statement is true or false.

(a) Every real number is either rational or irrational.

Let

R(x) = "x is rational"

I(x) = "x is irrational"

The statement may be translated as $\forall x(R(x) \lor I(x))$ . (Some people prefer to write the initial x as a subscript: $\forall_x(R(x) \lor I(x))$ . Use whichever form you prefer.) Here are the details.

First, when you use a quantifier you do so within the context of some universe of applicable objects. For this statement, the universe would be the set of real numbers. (It would be of little use to let x be a car, or an orange, or the right to freedom of speech.)

How do you know what the universe is for a given quantified statement? Sometimes, it is apparent from the context: In a mathematical discussion, it would probably be clear that the statement above was intended to apply to real numbers. In any case where confusion might arise, you should name the universe for quantification explicitly. In this case, the first part of the statement ("Every real number") makes it clear that the universe is the set of real numbers.

Notice that there is no conditional ("$\ifthen$ ") in the quantified translation.

The statements $R(x)$ and $I(x)$ depend on the variable x. That is, $R(2)$ would mean "2 is rational", $R(\sqrt{5})$ would mean "$\sqrt{5}$ is rational" and so on. $R(x)$ and $I(x)$ are called one-place predicates or single variable predicates.

Finally, note that while this statement happens to be true, truth value is distinct from how you translate the statement.

(b) There is a real number in the interval $[0,1]$ which is a root of the equation $x^7 + x - 1 = 0$ .

In this case, the universe would be the set of real numbers. I'll use the following predicates:

P(x) = "$0 \le x \le 1$ "

Q(x) = "$x^7 + x - 1 = 0$ "

The translation is $\exists x(P(x) \land Q(x))$ .

If $f(x) = x^7 + x - 1$ , then $f(0) = -1$ and $f(1) = 1$ . f is continuous, so the statement is true, by the Intermediate Value Theorem. Note that:

(c) Every real number is smaller than another real number.

The universe is the set of real numbers. The translation is $\forall x \exists y(x < y)$ .

$x < y$ is an example of a two-place or two-variable predicate, since it involves the variables x and y.

(d) For every real number, there is a smaller real number.

The universe is the set of real numbers. The translation is $\forall x \exists y(y < x)$ .

Example. Let $P(x)$ mean "x likes pepperoni", $O(x)$ mean "x likes onions", $NA(x)$ mean "x does not want anchovies", $A(x,y)$ mean "x is afraid of y", and let c stand for Calvin Butterball. Translate each statement into English.

(a) $\forall x (P(x) \ifthen \lnot NA(x))$

$\forall x (P(x) \ifthen \lnot NA(x))$ means "Everyone who likes pepperoni wants anchovies".

(b) $\exists x(P(x) \land NA(x))$

$\exists x(P(x) \land NA(x))$ means "Someone who likes pepperoni does not want anchovies".

(c) $\forall x \exists y(P(x) \land A(x,y))$

$\forall x \exists y(P(x) \land A(x,y))$ means "Everyone likes pepperoni and is afraid of someone".

(d) $\lnot \exists x[\forall y(O(x) \land NA(y) \land A(x,y))]$

$\lnot \exists x[\forall y(O(x) \land NA(y) \land A(x,y))]$ means "no one who likes onions is afraid of everyone who doesn't want anchovies".

Example. Let $P(x)$ mean "x likes pepperoni", $O(x)$ mean "x likes onions", $NA(x)$ mean "x does not want anchovies", $A(x,y)$ mean "x is afraid of y", and let c stand for Calvin Butterball. Translate each statement into logical symbols.

(a) "Some people don't like pepperoni."

The statement is that there are people who don't like pepperoni. In logical symbols, this is $\exists x \lnot P(x)$ .

(b) "Everyone who likes pepperoni likes onions."

The statement means that if someone likes pepperoni, then the person likes onions. In logical symbols, this is $\forall x (P(x) \ifthen O(x)$ .

(c) "Everyone likes pepperoni and onions."

The statement means that everybody likes both pepperoni {\it and} onions. In logical symbols, this is $\forall x (P(x) \land O(x))$ .

Do you understand the difference between the statements in (b) and (c)? In (b), you know that if there is a person who likes pepperoni, then the person likes onions. But there might not be anyone who likes pepperoni! In (c), everyone likes both pepperoni and onions, so in particular, there are certainly many people who like pepperoni.

What is the negation of

"Everyone likes pizza"?

Let $P(x)$ mean "x likes pizza". The statement may be written in quantified form as $\forall x(P(x))$ . The negation is (literally) $\lnot\forall x(P(x))$ : "It is not the case that everyone likes pizza". What does this mean?

A common mistake is to think that this means "No one likes pizza". However, ask yourself what it would take to show that the original statement was false. If I knew, for instance, that Calvin Butterball doesn't like pizza, that's enough to prove that "Everyone likes pizza" is false.

In other words, for "Everyone likes pizza" to be false --- or equivalently, for "It is not the case that everyone likes pizza" to be true --- it's enough if I find someone who doesn't like pizza. So the negation actually means "There exists someone who doesn't like pizza" --- in symbols, $\exists x(\lnot P(x))$ .

Let $Q(x)$ mean "x likes lasagne". What is the negation of "Someone likes lasagne"?

In symbols, "Someone likes lasagne" becomes $\exists x(Q(x))$ . The negation is $\lnot\exists x(Q(x))$ . In words, this is: "It is not the case that someone likes lasagne". This is the same as "No one likes lasagne", which is $\forall x(\lnot Q(x))$ .

To summarize:

$\left[\lnot\forall x(P(x))\right] \iff \left[\exists x(\lnot P(x))\right]$

$\left[\lnot\exists x(P(x))\right] \iff \left[\forall x(\lnot P(x))\right]$

In other words, to negate a quantified statement, change the quantifier to the "other" quantifier --- $\forall$ to $\exists$ and $\exists$ to $\forall$ --- and negate the "stuff inside".

Example. Negate the following quantified statements. Simplify your answers so that only simple statements are negated.

(a) $\forall x(P(x) \ifthen Q(x))$

$$\matrix{\lnot\left[\forall x(P(x) \ifthen Q(x))\right] & \iff & \exists \lnot\left[P(x) \ifthen Q(x)\right] & \hbox{(Negate a quantifier)} \cr & \iff & \exists \lnot\left[\lnot P(x) \lor Q(x)\right] & \hbox{(Conditional disjunction)} \cr & \iff & \exists \left[\lnot\lnot P(x) \land \lnot Q(x)\right] & \hbox{(DeMorgan)} \cr & \iff & \exists \left[P(x) \land \lnot Q(x)\right] & \hbox{(Double negation)} \cr}$$

Suppose $P(x)$ means "x is a dog" and $Q(x)$ means "x has four legs". Then $\forall x(P(x) \ifthen Q(x))$ means "All dogs have four legs".

The literal negation is "It is not the case that all dogs have four legs". What would you need to do to show that this statement is true? You'd need to produce a dog that does not have four legs: That is, there exists a dog that does not have four legs. In symbols, this is $\exists x(P(x) \land \lnot Q(x))$ .

(b) $\forall x\forall y\left[x < y \ifthen \left(\exists z(x < z < y)\right)\right]$

$$\matrix{\lnot\left(\forall x\forall y\left[x < y \ifthen \left(\exists z(x < z < y)\right)\right]\right) & \iff & \exists x\exists y \lnot\left[x < y \ifthen \left(\exists z(x < z < y)\right)\right] & \hbox{(Negate quantifiers)} \cr & \iff & \exists x\exists y \lnot\left[x \ge y \lor \left(\exists z(x < z < y)\right)\right] & \hbox{(Conditional disjunction)} \cr & \iff & \exists x\exists y \left[x < y \land \lnot\left(\exists z(x < z < y)\right)\right] & \hbox{(DeMorgan)} \cr & \iff & \exists x\exists y \left[x < y \land \left(\forall z[\lnot(x < z < y)]\right)\right] & \hbox{(Negate a quantifier)} \cr}$$

In a couple of the steps, I used the fact that the negation of $x < y$ is $x \ge y$ , and vice versa.

Example. Negate the following quantified statements. Simplify your answers so that only simple statements are negated.

(a) Every student sleeps late on Saturdays.

The negation is "Some students do not sleep late on Saturdays".

To see this symbolically, let $S(x)$ mean "x is a student" and let $L(x)$ mean "x sleeps late on Saturdays". The given statement is $\forall x[S(x) \ifthen L(x)]$ . Negate it:

$$\matrix{\lnot\left(\forall x[S(x) \ifthen L(x)]\right) & \iff & \exists x\lnot[S(x) \ifthen L(x)] & \hbox{(Negate a quantifier)} \cr & \iff & \exists x\lnot[\lnot S(x) \lor L(x)] & \hbox{(Conditional disjunction)} \cr & \iff & \exists x[S(x) \land \lnot L(x)] & \hbox{(DeMorgan)} \cr}$$

(I omitted a double negation step, and will often do this in the future.) In words, this says "There is a student who does not sleep late on Saturdays".

(b) There is a professor who is afraid of the ducks.

Let $P(x)$ mean "x is a professor" and let $D(x)$ mean "x is afraid of the ducks". The given statement is $\exists x(P(x) \land D(x))$ . Negate it:

$$\matrix{\lnot\left(\exists x(P(x) \land D(x))\right) & \iff & \forall x \lnot(P(x) \land D(x)) & \hbox{(Negate a quantifier)} \cr & \iff & \forall x (\lnot P(x) \lor \lnot D(x)) & \hbox{(DeMorgan)} \cr}$$

The last statement is correct --- only simple statements are negated --- but clumsy to read in words. It would say "Every person is either not a professor or not afraid of the ducks". I could make this a little better by using conditional disjunction:

$$\matrix{\forall x (\lnot P(x) \lor \lnot D(x)) & \iff & & \forall x (P(x) \ifthen \lnot D(x)) & \hbox{(Conditional disjunction)} \cr}$$

This reads literally as "If x is a professor, then x is not afraid of the ducks". I can remove the "x" by saying "Every professor is not afraid of the ducks".

If you know a quantified statement is true, you can draw certain conclusions.

Universal Quantifiers. If you know $\forall x P(x)$ , then for any element c in the universe, $P(c)$ is true. Thus, if a and b are elements of the universe, $P(a)$ is true and $P(b)$ is also true.

Existential Quantifiers. If you know $\exists x P(x)$ , then you can say there is an element c such that $P(c)$ . In a proof, you will usually say something like: "Let c satisfy $P(c)$ ", or "Let c be such that $P(c)$ ". When you say "Let c ...", you create an element named c --- in this case, satisfying $P(c)$ . From then on, c acts like a constant. In particular, you can't assign a value to it arbitrarily.

In addition, the existence statement only guarantees the existence of at least one thing satisfying $P(x)$ . So having said "Let c satisfy $P(c)$ ", you can't say in addition "And let d satisfy $P(d)$ ", since this creates another thing d which satisfies $P(x)$ . On the other hand, you can't assume that c is the only thing which satisfies $P(x)$ . Thus, there might be an element d such that $P(d)$ --- but you're not justified in saying there is.

Example. (a) Consider the following statement about natural numbers:

$$\forall x (x \le x^2).$$

If I know this is true, then I can specialize it to any particular natural number. So "$1 \le 1^2$ " is true, "$2 \le 2^2$ " is true, "$3 \le 3^2$ " is true, and so on.

(b) Consider the following statement about differentiable functions $\real \to \real$ :

$$\exists f (f(x) = f'(x)).$$

If I know this is true and I want to use it in a proof, I might say: "Let f be a differentiable function from $\real$ to $\real$ such that $f(x) = f'(x)$ ."

Once I've done this, f comes into existence and acts like a constant --- like 17, or $\pi$ , or $\sqrt{2}$ . The difference between f and other constant things is that at the moment, all I know about f is that $f(x) = f'(x)$ . But being "constant", I can't later say "Let $f(x) = x^2$ ", because that would assign "$x^2$ " to $f(x)$ .

I also can't reuse the existence statement and now say: "Let g be a differentiable function from $\real$ to $\real$ such that $g(x) = g'(x)$ ." I'm only entitled to one such function, and I already "let" it be f. At the same time, there might be another function g such that $g(x) = g'(x)$ --- I just can't assume there is.

Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2007 by Bruce Ikenaga