Section 2.3 Predicates and quantifiers
Basic propositional logic as you learned it in the preceding chapter is powerful enough to give us the tools we will need to prove many theorems. However, it is deficient in one key area. Consider the following example.
Example 2.3.1.
“If Hypatia is a woman and all women eat breakfast, then Hypatia eats breakfast.”
This statement is a tautology because if we suppose that all women eat breakfast (whether or not this is true) then Hypatia, a female mathematician who lived in Greece in the late 300's and early 400's, must eat breakfast. Since this statement is a tautology, the truth table should back us up...right?
Let \(p\) stand for “Hypatia is a woman,” \(q\) for “All women eat breakfast,” and \(r\) for “Hypatia eats breakfast.”
| \(p\) | \(q\) | \(r\) | \(p \wedge q\) | \((p \wedge q) \to r\) |
| \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(T\) | \(F\) | \(T\) | \(F\) |
| \(T\) | \(F\) | \(T\) | \(F\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(F\) | \(F\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(F\) | \(T\) |
| \(F\) | \(F\) | \(F\) | \(T\) | \(T\) |
This statement is not always true, since it is false in the second row. What gives?
Well, consider the statement “If pigs fly and a bear does its business in the woods, then Bob will earn an A on the exam.” Now it is not so clear that this is a tautology, because pigs, a bear, and Bob's grade presumably have nothing to do with one another.
The point of our logical structure is to capture the form of a statement, not necessarily the meaning. In the statement \((p \wedge q) \to r\text{,}\) there is no indication that \(p\text{,}\) \(q\text{,}\) and \(r\) have anything to do with each other.
But in the statement “If Hypatia is a woman and all women eat breakfast, then Hypatia eats breakfast”, the component statements have something to do with each other. Two refer to being a woman, two refer to eating breakfast, and two refer to the mathematician Hypatia. We need a way to incorporate the fact that the statements have related subjects and predicates in our logical system. This is where predicate logic comes in to help.
Subsection 2.3.1 Predicates
Definition 2.3.3.
A predicate is a function \(P:\Omega \to \{T,F\}\) that takes one or more subjects (members of some domain \(\Omega\)) and assigns to them all either true \(T\) or false \(F\text{.}\)
Predicates are typically denoted with capital letters like \(P\text{,}\) \(Q\text{,}\) and \(R\text{.}\) Subjects that are known are given lowercase letters like \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) unless there is something more reasonable to pick. Subjects whose values are unknown or arbitrary, variables, are denoted with lowercase \(x\text{,}\) \(y\text{,}\) \(z\text{,}\) etc.
The definition of predicate above is more complicated than it needs to be; this is so that we can take the central idea of a function that we saw last chapter and continue using it throughout the book. So, in the above definition, the predicate \(P\) is a function that takes a subject, a member of the set \(\Omega\text{,}\) and assigns it exactly one truth value. When a predicate \(P\) is evaluated at the subject \(a\text{,}\) the statement \(P(a)\) will be true or false.
(Take note that propositions, which you studied in the last chapter, may be regarded as constant predicates — functions whose value is the same regardless of the input, like \(f(x)=3\text{.}\))
Example 2.3.4.
Let \(P(x)\) be the predicate “\(x + 3 = 5\)” on the domain \(\mathbb{Z}\) and let \(Q(x,y)\) be the predicate “\(x\) orbits \(y\)” on the domain of celestial objects in the sky. The statement \(P(2)\) is true, but \(P(3)\) is false. If \(e\) stands for the earth and \(s\) for the sun, then \(Q(s,e)\) is false but \(Q(e,s)\) is true.
A predicate, once evaluated to a subject, is a statement. Therefore, these statements may be combined into compound statements using the logical connectives we have just studied.
Example 2.3.5.
As before let \(P(x)\) be the predicate “\(x + 3 = 5\)” on the domain \(\mathbb{Z}\) and let \(Q(x,y)\) be the predicate “\(x\) orbits \(y\)” on the domain of celestial objects in the sky, where \(e\) stands for the earth and \(s\) for the sun.
The statements \(P(2) \vee Q(s,e)\text{,}\) \(\neg P(3)\text{,}\) and \(Q(s,e) \to P(2)\) are true. For example, the statement \(P(2) \vee Q(s,e)\) means “\(2+3=5\) or the sun orbits the earth.” Since \(2+3=5\text{,}\) this disjunction is true.
The statements \(P(2) \wedge Q(s,e)\) and \(P(2) \to Q(s,e)\) are false. For instance, \(P(2) \to Q(s,e)\) is false because the antecedent \(P(2)\) is true, but the consequent \(Q(s,e)\) is false because the sun does not orbit the earth.
Subsection 2.3.2 Quantifiers
This is all well and good, you think, but what about the statement “All women eat breakfast”? How can we symbolize that a predicate is true for some or all undetermined objects in a set?
Quantifiers allow us to say that a predicate is true for all, or for at least one undetermined, object in its domain.
Definition 2.3.6.
Let \(P(x)\) be a predicate. The universal statement \(\forall x P(x)\) says that \(P(x)\) is true for all \(x\) in its domain. The operator \(\forall\) (“for all”) is called the universal quantifier.
Example 2.3.7.
The domain is very important. If \(P(x)\) is the predicate “\(x\) takes discrete math” then \(\forall x P(x)\)— “Everyone takes discrete math”—is true on the domain of computer science students at Coastal Carolina University, but not, say, on the domain of all people in South Carolina.
Definition 2.3.8.
Let \(P(x)\) be a predicate. The existential statement \(\exists x P(x)\) says that \(P(x)\) is true for at least one \(x\) in its domain. The operator \(\exists\) (“there exists”) is called the existential quantifier.
Example 2.3.9.
Again let \(P(x)\) be the predicate “\(x\) takes discrete math”. The existential statement \(\exists x P(x)\) says “Someone takes discrete math.” This is now true for people in South Carolina—pick a student at Coastal, or Clemson, or USC, or even a self-studier— but not true on the domain of dogs. Wouldn't that be cute, though?
The statement operated on by a quantifier is called its scope. Without parentheses, a quantifier is considered to apply only to the statement it is next to and no others.
Example 2.3.10.
Let \(P(x)\) be the predicate “\(x\) takes discrete math” and \(Q(x)\) be the statement “\(x\) is a math major”.
The statement \(\exists x (P(x) \wedge Q(x))\) means “There is someone who is taking discrete math and is a math major.” Both \(P\) and \(Q\) apply to the same \(x\text{.}\)
The statement \(\exists x P(x) \wedge \exists x Q(x)\) says “Someone is taking discrete math and someone is a math major.” The subjects of \(P\) and \(Q\) are possibly different.
The expression \(\exists x P(x) \wedge Q(x)\) is not a statement at all, because \(Q(x)\) is not a statement. It needs either a quantifier, or for \(x\) to refer to a specific, known member of the domain. By default, \(x\) is a variable.
There are two important quantified statements: “All \(P\)'s are \(Q\)'s” and “Some \(P\) is a \(Q\)”. These statements are all over the place in mathematics. We like to characterize mathematical objects by saying all objects of one type also belong to another; or, by saying we can find an object of one type that is another type.
The statement “All \(P\)'s are \(Q\)'s” is informal shorthand for the statement “For all \(x\) in the domain, if \(P(x)\) is true, then \(Q(x)\) is true.” The word “all” suggests that the universal quantifier is appropriate. What connective should be used to combine the predicates? Observe that the statement \(\forall x (P(x) \wedge Q(x))\) says that every \(x\) satisfies both \(P\) and \(Q\text{.}\) This isn't what we mean to say; we mean to say if something satisfies \(P\) then it will also satisfiy \(Q\text{.}\) So, the correct rendering of “All \(P\)'s are \(Q\)'s” is \(\forall x (P(x) \to Q(x))\text{.}\)
“Some \(P\)'s are \(Q\)'s” informally refers to “There exists at least one element \(x\) in the domain for which both \(P(x)\) and \(Q(x)\) are true”. We mean to say that there is an object that is at once a \(P\) and a \(Q\text{.}\) Therefore, this time the conjunction is appropriate: we write \(\exists x (P(x) \wedge Q(x))\text{.}\)
| Statement | Symbolization |
| “All \(P\)'s are \(Q\)'s” | \(\forall x (P(x) \to Q(x))\) |
| “Some \(P\)'s are \(Q\)'s” | \(\exists x (P(x) \wedge Q(x))\) |
Example 2.3.12.
Define the following predicates on the domain of vegetables. Let \(R(x)\) be “\(x\) is red”, and \(T(x)\) be “\(x\) is a tomato.”
To say “All red vegetables are tomatoes”, use the statement form \(\forall x(R(x) \to T(x))\text{.}\) Notice we don't need an additional predicate for vegetable since our domain is the set of all vegetables. This statement is false since there are red vegetables that are not tomatoes.
To say “There is a red vegetable that is a tomato”, use \(\exists x(R(x) \wedge T(x))\text{.}\) This sentence is true.
We aren't restricted to just these two sentences. For example, \(\exists x(T(x) \wedge \neg R(x))\) means “There is a tomato that is not red” (also true).
Example 2.3.13.
Let \(P(x)\) be the predicate “\(x\) is a prime number”, let \(E(x,y)\) be the predicate “\(x\) and \(y\) are equal”, and \(O(x)\) be the predicate “\(x\) is odd”. The domain of these statements is the set \(\mathbb{Z}\) of integers.
How should we symbolize the statement “Every prime number is \(2\) or odd”? It has the form “Every... is...”, so it is appropriate to use a universal quantifier and a conditional. The antecedent of the conditional will be that the number is prime, so, \(P(x)\) (assuming we use \(x\) as our variable). The consequent will be that the same number (so, \(x\)) is equal to \(2\) or else odd, which is \(E(x,2) \vee O(x)\text{.}\) Tying it all together we have
Let's try another one, backwards this time. What does
say?
The statement involves an existential quantifier. You can read \(\exists xy\) as \(\exists x \exists y\text{,}\) in other words, that there are two variables that satisfy the following predicates. It also involves a conjunction, so this is a “Some ... are ...” type statement.
To translate to and from symbolic logic, it is best to pick something you recognize and fill in the other pieces.
\(\exists xy\) on our domain says, “There are two integers.”
\(P(x)\) says one of those integers is prime.
\(O(y)\) says the other of those integers is odd. (Remember to pay attention when you have multiple variables in play!)
\(E(x,y)\) says that the two integers are equal.
All together, we could say, “There are two integers where one is prime, one is odd, and they are equal.” That's a little clunky, but we can always clean it up on a second pass: “A prime integer is equal to an odd integer.” That's better!
Finally, what is to be done with statements with two or more subjects? The ordering of the quantifiers matters. Here are the four possible combinations of universal and existential quantifiers for two subjects, as well as a diagram corresponding to each.
Example 2.3.14.
Let \(R(x,y)\) be the predicate “\(x\) and \(y\) are classmates” over the domain of students at some school. Note that, in this case, the order of the subjects does not affect the truth of the statement. Sometimes the order of the subjects does matter, as in “\(x\) pays \(y\)”.
The statement \(\exists xy R(x,y)\) means “There are two students who are classmates.” In other words, there is at least one student who is paired with at least one other student. Some writers say \(\exists x \exists y R(x,y)\) instead, but when the quantifiers are the same we will “collapse” the notation.
One element of one set is paired with one element of a second set. This corresponds to two existential quantifiers.
The statement \(\exists x \forall y R(x,y)\) means “There is a student who is classmates with every student.” We have one student who (somehow!) is classmates with the entire student body.
One element of one set is paired with every element of a second set. This corresponds to an existential quantifier followed by a universal quantifier.
The statement \(\forall x \exists y R(x,y)\) means “Every student has a classmate.” Notice that their classmate need not be the same person. If we quantify universally first, then each existential object may be different. In the preceding example, we quantified existentially first, so that one person was classmates with everybody.
Every element of one set is each paired with an element of a second set. This corresponds to an universal quantifier followed by a existential quantifier.
The statement \(\forall xy R(x,y)\) means “Every student is classmates with every other student.” Every object in our domain is paired up with every other object in the domain, including themselves! (Don't think too hard about that for this example.)
Every element of one set is each paired with every element of a second set. This corresponds to two universal quantifiers.