4.4: The Introduction and Elimination Rules for Quantifiers
- Page ID
- 23902
As you know, there are two quantifiers (\(\exists\) and \(\forall\)). Each of these has an introduction rule and an elimination rule, so there are \(4\) rules to present in this section. Proofs in can use both of these rules, plus all of the rules of (such as the rules of negation and the basic theorems, including introduction and elimination rules), and also any other theorems that have been previously proved.
4.4A. \(\exists\)-introduction
We need to determine how to prove a conclusion of the form \(\exists x \in X, \dots\). For example, in a murder mystery, perhaps Inspector Thinkright gathers the suspects in a room and tells them, “Someone in this room has red hair.” That is a \(\exists\)-statement. (With an appropriate symbolization key, in which \(P\) is the set of all of the the people in the room, and \(R(x)\) is the predicate “\(x\) has red hair,” it is the assertion \(\exists p \in P, R(p)\).) How would the Inspector convince a skeptic that the claim is true? The easiest way would be to exhibit an explicit example of a person in the room who has red hair. For example, if Jim is in the room, and he has red hair, the Inspector might say,
"Look, Jim is sitting right there by the door, and now, when I take off his wig, you can see for yourself that he has red hair. So I am right that someone in this room has red hair."
In general, the most straightforward way to prove \(\exists p \in P, R(p)\) is true is to find a specific example of a \(p\) that makes \(R(p)\) true. That is the essence of the \(\exists\)-intro rule.
Here is a principle to remember:
The proof of an assertion that begins
"there exists \(x \in X\), such that. . ."
will usually be based on the statement. "Let \(x = \square\),"
where the box is filled with an appropriate element of \(X\).
Most mathematicians are not familiar with the terminology of introduction rules and elimination rules. Instead of saying this is the \(\exists\)-introduction rule, they would call it “proof by constructing an example,” or “giving an explicit example,” or other words to the same effect.
Here are some proofs that use \(\exists\)-introduction, but we cannot do very much with only one quantifier rule — the examples will be more interesting when we have more rules to work with.
Prove there is a natural number \(n\), such that \(n^2 = 64\).
Solution
Proof.
Let \(n = 8 \in \natural\). Then \(n^2 = 8^2 = 64\).
Prove there is a real number \(c\), such that \(5c^2 - 5c + 1 < 0\).
Solution
Proof.
Let \(c = 1/2 \in \mathbb{R}\). Then \[\begin{aligned} 5c^2 - 5c + 1 = 5 \left(\frac{1}{2}\right)^2 - 5 \left(\frac{1}{2}\right) + 1 = \frac{5}{4} - \frac{5}{2} + 1 = -\frac{1}{4} < 0 . & \end{aligned}\]
Let \(N = \{1,3,5,7\}\). Prove there exists \(n \in N\), such that \(n^3-11n^2+31n \neq 21\).
Solution
Proof.
Let \(n = 5 \in N\). Then \[\begin{aligned} n^3-11n^2+31n = 5^3-11(5^2)+31(5) = 125 - 11(25) + 155 = 125 - 275 + 155 = 5 \neq 21 . \end{aligned}\]
- Prove there is a real number \(r\), such that \(2r^2 + 9r + 4 = 0\).
- Let \(B = \{1,3,5,7\}\). Prove there exists \(b \in B\), such that \(3b + 1 = (b-1)^2\).
- Prove there exist natural numbers \(m\) and \(n\), such that \(m^2 = n^3 + 1 > 1\).
- Show there is an integer \(n\), such that \(3n^2 = 5n + 2\).
- Assume \(a\) is a real number. Show there is a real number \(x\), such that \(7x - 5 = a\).
\(\exists\)-elimination
Perhaps Inspector Thinkright knows that one of the men lit a match at midnight, but does not know who it was. The Inspector might say,
"We know that one of the men lit a match at midnight. Let us call this mysterious gentleman 'Mr. X'. Because right-handed matches are not allowed on the island, we know that Mr. X is left handed. Hence, Mr. X is not a butler, because all of the butlers in this town are right handed. . . ."
and so on, and so on, telling us more and more about Mr. X, based only on the assumption that he lit a match at midnight.
The situation in mathematical proofs is similar. Suppose we know there exists an element of the set \(A\). Then it would be helpful to have a name for this mysterious element, so that we can talk about it. But a mathematician would not call the element “Mr. X”: if it is an element of the set \(A\), then he or she would probably call it \(a\) (or \(a_1\) if there are going to be other elements of \(A\) to talk about). In general, the idea of the \(\exists\)-elimination rule is:
If \(\exists x \in X\), \(P(x)\) is known to be true, then we may
let \(x\) be an element of \(X\), such that \(P(x)\) is true.
In the remainder of the proof, we may assume only two things about \(x\): that \(x \in X\), and that \(P(x)\) is true.
Show that if there exists \(a \in \mathbb{R}\), such that \(a^3 + a + 1 = 0\), then there exists \(b \in \mathbb{R}\), such that \(b^3 + b - 1 = 0\).
Solution
Proof.
Assume there exists \(a \in \mathbb{R}\), such that \(a^3 + a + 1 = 0\). Let \(b = -a\). Then \(b \in \mathbb{R}\), and \[\begin{aligned}
b^{3}+b-1 &=(-a)^{3}+(-a)-1 \\
&=-a^{3}-a-1 \\
&=-\left(a^{3}+a+1\right) \\
&=-0 \\
&=0
\end{aligned}\]
(Fourth Line: by the definition of \(a\))
as desired.
Assume \(A\) and \(B\) are sets of real numbers.
- Show that if there exists \(a \in A\), such that \(2a > 5\), then there exists \(b \in A\), such that \(b > 0\).
- Show that if there exists \(x \in \mathbb{R}\), such that \(x - 2 \in A\), then there exists \(y \in \mathbb{R}\), such that \(3y \in A\).
- Show that if \(A \cap B \neq \emptyset\), then \(A \neq \emptyset\).
\(\forall\)-elimination
Perhaps Inspector Thinkright knows that Jeeves is a butler in the town, and that all of the butlers in the town are right handed. Well, then it is obvious to the Inspector that Jeeves is right handed. This is an example of \(\forall\)-elimination: if you know something is true about every element of a set, then it is true about any particular element of the set. \[\text { If } \forall x \in X, P(x) \text { is true, and } a \in X \text {, then } P(a) \text { is true. }\]
Suppose
- \(C \subset \mathbb{R}\), and
- \(\forall x \in \mathbb{R}, \bigl( (x^2 = 9) \Rightarrow (x \in C) \bigr)\).
Show \(\exists c \in \mathbb{R}, c \in C\).
Solution
Proof.
Let \(c = 3 \in \mathbb{R}\). Then \(c^2 = 3^2 = 9\), and letting \(x = c\) in Hypothesis (2) tells us that \[( c^2 = 9) \Rightarrow ( c \in C) .\] Therefore \(c \in C\).
Assume \(A \neq \emptyset\) and \(A \subset B\). Prove \(\exists b, (b \in B)\).
Solution
Proof.
Because \(A\) is not the empty set, we know it has at least one element; that is, we have \(\exists x, (x \in A)\). Hence, we may let \(a\) be some element of \(A\). Now, let \(b = a\). Because \(A \subset B\), we know that every element of \(A\) is an element of \(B\). In particular, since \(b = a \in A\), this means that \(b \in B\).
When applying \(\forall\)-elimination, the variable does not need to be called “\(x\),” (it could be \(y\) or \(z\) or any other variable), and the constant does not need to be called “\(a\)” (it could be any element of \(X\)). However, if the variable occurs more than once in the formula, it is important to replace all of its occurrences with \(a\). For example, if \(a \in X\), then, from \(\forall x \in X, \bigl( A(x) \Rightarrow B(x) \bigr)\), we can conclude \(A(a) \Rightarrow B(a)\), but not \(A(a) \Rightarrow B(x)\) or \(A(x) \Rightarrow B(a)\).
- Assume \(\forall x \in \mathbb{R}, (x^2 \in Z)\). Show \(16 \in Z\).
- Assume \(A \subset B\) and \(A \neq \emptyset\). Show \(B \neq \emptyset\).
- Assume
- for every \(x \in A\), either \(x \in B\), or \(x < 0\), and
- there exists \(a \in A\), such that \(a > 0\).
Show \(B \neq \emptyset\).
\(\forall\)-introduction
If Inspector Thinkright needs to verify that all of the butlers in town have seen the aurora borealis, he would probably get a list of all the butlers, and check them one-by-one. That is a valid approach, but it could be very time-consuming if the list is very long. In mathematics, such one-by-one checking is often not just time-consuming, but impossible. For example, the set \(\natural\) is infinite, so, if we wish to show \(\forall n \in \natural, (\text{$2n$ is even})\), then we would never finish if we tried to go through all of the natural numbers one-by-one. So we need to deal with many numbers at once.
Consider the following simple deduction:
Hypothesis:
Every butler in town got up before 6am today.
Everyone who got up before 6am today, saw the aurora.
Conclusion:
Every butler in town saw the aurora.
This is clearly a valid deduction in English. Let us translate it into to analyze how we were able to reach a conclusion about all of the butlers, without checking each of them individually. Here is a symbolization key:
\(B\): The set of all of the butlers in town.
\(P\): The set of all people.
\(U(x)\): got up before 6am today.
\(S(x)\): saw the aurora.
We can now translate our English deduction, as follows:
Hypothesis:
\(\forall b \in B, U(b)\).
\(\forall p \in P, \bigl( U(p) \Rightarrow S(p) \bigr)\).
Conclusion: \(\forall b \in B, S(b)\).
How do we justify the conclusion? Well, suppose for a moment that we start to check every butler in town, and that \(j\) represents Jimmy, who is one of the butlers in town. Then our first hypothesis allows us to conclude \(U(j)\). Since Jimmy is a person, our second hypothesis allows us to conclude that \(U(j) \Rightarrow S(j)\). Then, using \(\Rightarrow\)-elimination, we conclude \(S(j)\). But there was nothing special about our choice of Jimmy. All that we know about him, is that he is a butler in the town. So we could use exactly the same argument to deduce \(S(b)\) for any butler \(b\) in the town.
This is how we justify a \(\forall\)-introduction. If we can prove that the desired conclusion is true for an arbitrary element of a set, when we assume nothing about the element except that it belongs to the set, then the conclusion must be true for every element of the set.
We write the above deduction as follows:
Assume that every butler in town got up before 6am today. Also assume that everyone who got up before 6am today, saw the aurora. Then every butler in town saw the aurora.
- Proof
-
Let \(b\) represent an arbitrary butler in town. Then, since all of the butlers got up before 6am, we know that \(b\) got up before 6am. By hypothesis, this implies that \(b\) saw the aurora. Since \(b\) is an arbitrary butler in town, we conclude that every butler in town saw the aurora.
This reasoning leads to the \(\forall\)-introduction rule: in order to prove that every element of a set \(X\) has a certain property, it suffices to show that an arbitrary element of \(X\) has the desired property. For example, if we wish to prove \(\forall b \in B, P(b)\), then our proof should start with the sentence “Let \(b\) be an arbitrary element of \(B\).” (However, this can be abbreviated to: “Given \(b \in B\), …”) After this, our task will be to prove that \(P(b)\) is true, without assuming anything about \(b\) other than it is an element of \(B\).
The proof of an assertion that begins "for all \(x \in X\),"
will usually begin with "Let \(x\) be an arbitrary element of \(X\)"
(or, for short, "Given \(x \in X\),").
It is important not to assume anything about \(x\) other than that it is an element of \(X\). If you choose \(x\) to be a particular element of \(X\) that has some special property, then your deduction will not be valid for all elements of the set.
Suppose we would like to justify the following deduction:
All of the butlers in town dislike Jimmy, and Jimmy is a butler in town.
Therefore, all of the butlers in town dislike themselves.
Then it suffices to show, for an arbitrary butler \(b\), that \(b\) dislikes \(b\). We might try the following proof:
Solution
Proof attempt.
Let \(b\) be Jimmy, who is a butler in town. Then, since all of butlers in town dislike Jimmy, we know that \(b\) dislikes Jimmy. Since \(\text{Jimmy} = b\), this means \(b\) dislikes \(b\), as desired. So every butler in town dislikes himself.
This proof is certainly not valid, however. Letting \(b = \text{Jimmy}\) does not make \(b\) an arbitrary butler; rather, it makes \(b\) a very special butler — the one that everybody dislikes. In this case, conclusions that are true about \(b\) are not necessarily true about the other butlers.
Another point that should be emphasized is that an arbitrary member of a set is not the same as a random member of a set. If we want to prove that all of the butlers have seen the aurora, it is not enough to choose a butler at random, ask if he saw the aurora and draw a conclusion about all of the butlers based on that single answer. It is only if we can determine through logical deduction that no matter which butler we choose, that person saw the aurora, that we can conclude that all of the butlers saw the aurora.
Which of the \(4\) quantifier rules does each deduction illustrate?
- Everyone who ate in the cafeteria yesterday is sick today. Oh, no! Susie ate in the cafeteria — she must be sick!
- Susie ate in the cafeteria yesterday, so I’m sure that somebody ate in the cafeteria yesterday.
- Without knowing which of the athletes it was, I figured out that he or she must have eaten in the cafeteria yesterday. The only way that can be true is if every athlete ate in the cafeteria yesterday.
- Our food reporter says that some woman knocked over a big box of lima beans while she was eating in the cafeteria yesterday. Whoever she is, let’s call her “Ms. Clumsy.” So this morning’s headline can be “Ms. Clumsy spilled the beans!”