We are now ready for a closer look at the two types of quantifiers that we will use.
SubsectionUniversal Quantifiers
Convention1.50.
When using variables in a statement \(P\text{,}\) it is often useful to write \(P(x)\) instead of \(P\) to indicate that \(x\) is subject to change. If in a statement \(Q\) both \(x\) and \(y\) are variables, and we would denote that by writing \(Q(x, y)\text{.}\)
Definition1.51.
Let \(P(x)\) be an expression with free variable \(x\text{.}\) Let \(U\) denote a collection of possible values of \(x\text{.}\) A universal quantifier applied to \(P(x)\) is the statement, denoted \((\forall x \text{ in } U)P(x)\text{,}\) which is true if \(P(x)\) is true for all possible values of \(x\) in \(U\text{.}\)
Convention1.52.
If the collection \(U\) is understood from the context, then we will write \((\forall x)P(x)\text{.}\)
Remark1.53.
One way to think of the statement \((∀x in U)P(x)\) is to view it as the conditional statement “if \(x\) is in \(U\text{,}\) then \(P(x)\) is true.”
Convention1.54.
There are a variety of ways to write \((∀x in U)P(x)\) in English, for example:
For all values of \(x\) in \(U\text{,}\) the statement \(P(x)\) is true;
For each \(x\) in \(U\text{,}\) the statement \(P(x)\) is true;
The statement \(P(x)\) is true for all \(x\) in \(U\text{;}\)
All values of \(x\) in \(U\) satisfy the \(P(x)\text{.}\)
Example1.55.
Let \(P(α) = \)“person \(α\) has red hair,” and let \(W\) be the collection of all people in the world. The statement \((∀α in W )P(α)\) would mean that “all people in the world have red hair” (which is certainly not a true statement).
Warning1.56.
Changing the collection \(U\) in a statement of the form \((∀x in U)P(x)\) can change the truth or falsity of the statement, so that the choice of \(U\) is crucial.
Example1.57.
Let \(R(x) = \)“the number \(x\) has a square root.” If we let \(U\) be the collection of positive real numbers, then the statement \((∀x in U)R(x)\) is true. On the other hand, if we let \(W\) be the collection of all real numbers, then the statement \((∀x in W )R(x)\) is false.
Example1.58.
For the sake of completeness, we need to allow the case where the collection \(U\) has nothing in it. In that case, the statement \((∀x in U)P(x)\) is always true, no matter what \(P(x)\) is, for the following reason. The statement “\((∀x in U)P(x)\)” is equivalent to the statement “if \(x\) is in \(U\text{,}\) then \(P(x)\) is true.” When the collection \(U\) has nothing in it, then the statement “\(x\) is in \(U\)” is false, and hence the conditional statement “if \(x\) is in \(U\text{,}\) then \(P(x)\) is true” is true.
SubsectionExistential Quantifiers
Definition1.59.
Let \(P(x)\) be a statement with variable \(x\text{,}\) and let \(U\) denote a collection of possible values of \(x\text{.}\) An existential quantifier applied to \(P(x)\) is the statement, denoted \((∃x \text{ in }U)P(x)\text{,}\) which is true if \(P(x)\) is true for at least one value of \(x\) in \(U\text{.}\)
Convention1.60.
If the collection \(U\) is understood from the context, then we will write \((∃x)P(x)\text{.}\)
Remark1.61.
Observe that if the collection \(U\) has nothing in it, then the statement \((∃x)P(x)\) is false.
It is important to note that the phrase “at least one value of \(x\) in \(U\)” means one or more, possibly many, or even all \(x\) in \(U\text{.}\) In particular, if \((∀x in U)P(x)\) is true, then \((∃x in U)P(x)\) is true, except in the special case that \(U\) has nothing in it. However, the statement \((∃x in U)P(x)\) does not imply that \((∀x in U)P(x)\) is true, except in the case that \(U\) has either one thing or nothing in it.
Convention1.62.
There are a variety of ways to write \((∃x in U)P(x)\) in English, for example:
There exists some \(x\) in \(U\) such that \(P(x)\) holds;
There is \(x\) in \(U\) such that \(P(x)\) holds;
There exists at least one \(x\) in \(U\) such that \(P(x)\) holds;
For some value of \(x\) in \(U\text{,}\) the condition \(P(x)\) holds;
It is the case that \(P(x)\) is true for some \(x\) in \(U\text{.}\)
Example1.63.
Let \(Q(r) = \)“person r has brown hair,” and let \(W\) be the collection of all people in the world. Then the statement \((∃r in W )Q(r)\) would mean that “there is someone with brown hair,” or equivalently “some people have brown hair” (which is a true statement).
SubsectionMultiple Quantifiers
We can form statements with more than one quantifier, as long as different quantifiers involve different variables.
Example1.64.The Order of the Quantifiers Matters..
Suppose that \(P(x, y) = “x + y^2 = 3,”\) where \(x\) and \(y\) are real numbers. The statement \((∀y)(∃x)P(x, y)\) can then be written in English as “for all \(y\) there exists some \(x\) such that\(x + y^2 = 3\text{,}\)” or equivalently “for each \(y\) there is some \(x\) such that \(x + y^2 = 3\text{.}\)” This statement is true, because for any real number \(y\) we can always solve for \(x\) in terms of \(y\text{,}\) yielding \(x = 3 - y^2\) .
If we reverse the order of the quantifiers, we obtain the statement \((∃x)(∀y)P(x, y)\text{,}\) which can be written in English as “there exists some \(x\) such that for all \(y\text{,}\) the equation \(x+y^2 = 3\) holds.” This statement is false, because for any given \(x\text{,}\) there can be at most two values of \(y\) such that \(x + y^2 = 3\text{.}\)
Remark1.65.
When attempting to prove a theorem, the statement of which involves multiple quantifiers, it is sometimes useful to translate the statement of the theorem into symbols, to help keep track of the meaning of the quantifiers.
Example1.66.
Suppose that we are given the statement “if \(x\) is a non-negative real number, then \(x\) is a perfect square.” This statement can be interpreted as a doubly quantified statement by rephrasing it as “for each non-negative real number \(x\text{,}\) there is some real number \(y\) such that \(x = y^2\text{.}\)” Written symbolically, the statement is (\(∀x\) in the non-negative real numbers)(\(∃y\) in the real numbers)(\(x = y^2\)).
Warning1.67.
A lack of attention to the order of quantifiers can easily lead to mistakes in proving theorems that have statements with multiple quantifiers.
There are eight possible generic ways of writing two quantifiers in a statement that has variables. Most of the eight possibilities have different meanings from one another.
Example1.68.
\((\forall x)(\forall y)L(x, y)\text{.}\) This statement can be written in English as “for each person \(x\text{,}\) for each type of fruit \(y\text{,}\) person \(x\) likes to eat \(y\text{,}\)” and more simply as “every person likes every type of fruit.” To verify whether this statement is true, we would have to ask each person in the world if she likes every type of fruit; if even one person does not like one type of fruit, then the statement would be false.
\((\forall y)(\forall x)L(x, y)\text{.}\) This statement can be written as “for each type of fruit \(y\text{,}\) for each person \(x\text{,}\) we know \(x\) likes to eat \(y\text{,}\)” and more simply as “every type of fruit is liked by every person.” This statement is equivalent to Statement 1.
\((\forall x)(∃y)L(x, y)\text{.}\) This statement can be written as “for each person \(x\text{,}\) there is a type of fruit y such that \(x\) likes to eat \(y\text{,}\)” and more simply as “every person likes at least one type of fruit.” To verify whether this statement is true, we would have to ask each person in the world if she likes some type of fruit; if at least one person does not like any type of fruit, then the statement would be false.
\((∃x)(\forall y)L(x, y)\text{.}\) This statement can be written as “there is a person \(x\) such that for all types of fruit \(y\text{,}\) person \(x\) likes to eat \(y\text{,}\)” and more simply as “there is a person who likes every type of fruit.” To verify whether this statement is true, we would start asking one person at a time if she likes every type of fruit; as soon as we found one person who answers yes, we would know that the statement is true, and we could stop asking more people. If no such person is found, then the statement would be false.
\((\forall y)(∃x)L(x, y)\text{.}\) This statement can be written as “for each type of fruit \(y\text{,}\) there is a person \(x\) such that \(x\) likes to eat \(y\text{,}\)” and more simply as “every type of fruit is liked by at least one person.” To verify whether this statement is true, we would have to list all the types of fruit, and then for each type of fruit, ask one person at a time whether she likes the fruit; once we found someone who liked that fruit, we could move onto the next fruit, and again ask one person at a time about it. For the statement to be true, we would have to find at least one person per fruit, though the same person could be selected for more than one fruit.
\((∃y)(\forall x)L(x, y)\text{.}\) This statement can be written as “there is a type of fruit \(y\) such that for all persons \(x\text{,}\) we know that \(x\) likes to eat \(y\text{,}\)” and more simply as “there is a type of fruit that all people like.” To verify whether this statement is true, we would have to list all the types of fruit, and then for one type of fruit at a time, ask each person in the world if she likes that type of fruit; as soon as we found one type of fruit that everyone likes, we would know that the statement is true, and we could stop asking about more types of fruit.
\((∃x)(∃y)L(x, y)\text{.}\) This statement can be written as “there is a person \(x\) such that there is a type of fruit \(y\) such that \(x\) likes to eat \(y\text{,}\)” and more simply as “there is a person who likes at least one type of fruit.” To verify whether this statement is true, we would have to start asking one person at a time if she likes some type of fruit; as soon as we found one person who answers yes, we would know that the statement is true, and we could stop asking more people.
\((∃y)(∃x)L(x, y)\text{.}\) This statement can be written as “there is a type of fruit \(y\) such that there is a person \(x\) such that \(x\) likes to eat \(y\text{,}\)” and more simply as “there is a type of fruit that is liked by at least one person.” This statement is equivalent to Statement 7.
In the above example we had eight cases, because there were two variables. When there are more variables, then the number of cases will be even larger. Also, we observe that whereas most of the cases in the above example are different from one another, there exist some examples of statements where some of the distinct cases above happen to coincide.
SubsectionNegating Quantifiers
We now look at the negation of statements with quantifiers.
Fact1.69.
Let \(P(x)\) be a statement with variable \(x\text{,}\) which takes values in some collection \(U\text{.}\)
\(¬[(∀x in U)P(x)] ⇔ (∃x in U)(¬P(x))\text{.}\)
\(¬[(∃x in U)P(x)] ⇔ (∀x in U)(¬P(x))\text{.}\)
Remark1.70.
Unlike the equivalences discussed in Section 1.3, we cannot use truth tables to verify the equivalences in Fact 1.69, though they are true nonetheless, based on the meanings of the quantifiers.
We can use the above equivalences to negate statements with more than one quantifier.
Example1.71.
Suppose that \(f\) is a function that takes real numbers to real numbers (for example \(f (x) = x^2\) for all real numbers \(x\)). Let \(Q =\) “for each real number \(w\text{,}\) there is some real number \(y\) such that \(f (y) = w\text{.}\)” We would like to find \(¬Q\text{.}\) We start by writing \(Q\) symbolically. Let \(P(w, y) = “ f (y) = w.”\) Then \(Q = (∀w)(∃y)P(w, y)\text{.}\) Using our equivalences we have ¬Q ⇔ ¬[(∀w)(∃y)P(w, y)] ⇔ (∃w)¬[(∃y)P(w, y)] ⇔ (∃w)(∀y)(¬P(w, y)). Rephrasing this last expression in English yields \(¬Q = \)“there exists a real number \(w\) such that for all real numbers \(y\text{,}\) the relation \(f (y) \neq w\) holds.
It is often easier to negate statements with multiple quantifiers by first translating them into symbolic form, negating them symbolically and then translating back into English. With a bit of practice it is possible to negate such statements directly in English as well, as long as the statements are not too complicated.
