Quantifiers

Here is a (true) statement about integers: "Every integer is either even or odd."

Remember that an integer is even if it's divisible by 2, and an integer is odd if it's not even.

I could try to translate the statement as follows: Let

P = "x is an integer"

Q = "x is even"

R = "x is odd"

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

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

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

(a) $\forall$ , the universal quantifier, which is read "for all", "for every", or "for each".

(b) $\exists$ , the existential quantifier, which is read "there is" or "there exists".

Here are some examples which show how they're used. 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".

Here are how the negations of the statements come out in words:

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

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

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

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

(a) 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) 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:

1. The theorem doesn't tell you how to find an x that works.

2. The statement doesn't say that there is only one x that works. "There exists" means "there exists at least one" --- but there may be more than one.

(c) 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) 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))$

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

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

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

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

(b) $\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))$ means "Everyone likes pepperoni and is afraid of someone".

(d) $\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."

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

(c) "Everyone likes pepperoni and onions."

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

(b) 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) The statement means that everybody likes both pepperoni 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 the statement "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:

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

(b) $\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))$

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

(a)

$$\matrix{\lnot\left[\forall x (P(x) \ifthen Q(x))\right] & \iff & \exists x \lnot\left[P(x) \ifthen Q(x)\right] & \hbox{(Negate a quantifier)} \cr & \iff & \exists x \lnot\left[\lnot P(x) \lor Q(x)\right] & \hbox{(Conditional disjunction)} \cr & \iff & \exists x \left[\lnot\lnot P(x) \land \lnot Q(x)\right] & \hbox{(DeMorgan)} \cr & \iff & \exists x \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)

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

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

(a) 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) 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.

For instance, 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.

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.

As an example, 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.

We will spend some time doing formal logic proofs involving logical connectives and rules for inference, but will not do formal logic proofs involving quantifiers. You can find proofs of that kind in books on classical or formal logic.

On the other hand, the proofs which we do involving quantifiers will be ordinary proofs in mathematics.

Example. (a) ( Proving a statement with an existential quantifier) Prove that

$$(\exists x \in \real) (x^2 - 2 x < 0)$$

(b) ( Disproving a statement with a universal quantifier) Show that the following statement is false:

$$(\forall x \in \real) ((x - 1)^2 > 0)$$

(a) To show that an existence statement is true, I only need to find one case where it is true. The given statement says in words that there is a real number x such that $x^2 - 2 x < 0$ .

The graph of $y = x^2 - 2 x$ is a parabola with roots at 0 and 2, so between 0 and 2 the parabola will be below the x-axis. There are an infinite number of real numbers for which this is the case. For example, $x = 1$ works: $1^2 - 2 \cdot 1 = -1 < 0$ .

(b) To disprove a universal statement, I only need to find one case where it is false. The given statement says in words that for every real number x, I have $(x - 1)^2 > 0$ . But this is false for $x = 1$ : $(1 - 1)^2 = 0^2 = 0$ , and $0 \not{>} 0$ .

Note the parallel between (a) and (b). Also, note that disproving an existence statement or proving a universal statement is more work than what we did here.

Contact information

Bruce Ikenaga's Home Page

Copyright 2019 by Bruce Ikenaga