Subsection 8.4.4 Proof by Counterexample
Suppose that we are considering a universal claim. So we might have something like one of these expressions:
[1] ∀x (P(x))
[2] ∀x (∃y (P(x, y)))
[3] (∃x (Q(x))) → (∀y (P(y)))
To prove that such a claim is true, it is necessary to prove that it holds for all values of all the universally quantified variables (drawn from the universe that we are discussing).
But to prove that such a claim is false, it suffices to find a single counterexample. The existence of even one such counterexample means that the claim cannot be true for all values.
Assume the universe of positive integers. Consider the following claim:
[1] \(\forall\)n (Prime \((3^n + 2)) \)
Suppose that we don’t have a clue how to prove the claim. In fact, we don’t even know whether it is true. One thing we could try is to examine it for several values of n to see if we can find a pattern. Doing that, we get:
n = 1 31 + 2 = 5 Prime
n = 2 32 + 2 = 11 Prime
n = 3 33 + 2 = 29 Prime
n = 4 34 + 2 = 83 Prime All prime so far, but no clue why, so keep going.
n = 5 35 + 2 = 245 Not Prime
We’re done. We have proved that [1] is false.
Single counterexamples also disprove everyday kinds of claims.
Recall our Contagious Disgruntledness example. We have a group of people among whom grumpiness is highly contagious. If even one person gets disgruntled, the bad vibes will quickly spread to the whole group. So we wrote:
[1] (\(\exists\)x (Disgruntled(x))) \(\rightarrow\) (\(\forall\)z (Disgruntled(z)))
How could we prove that this claim is false? The conclusion of the implication is only guaranteed if there exists at least one disgruntled person. But, if there does, then everyone else must be disgruntled too. So, we could prove this claim false if we could both find one disgruntled person (or, alternatively, prove the claim that such a person exists) and then find even one other person who isn’t disgruntled. So, for example, we can prove that [1] is false if we have two more claims:
[2] Disgruntled(Grouchy)
[3] \(\neg\) Disgruntled(Sunshine)
Big Idea
A single example says nothing about the truth of a universal claim. Yet a single counterexample says everything about the falsity of such a claim.
Assume the universe of positive integers. Define n factorial (written n!) as:
[1] n \(\cdot\) (n-1) \(\cdot\) (n-2) \(\cdot\) … \(\cdot\) 1
For example, 5! = 5 \(\cdot\) 4 \(\cdot\) 3 \(\cdot\) 2 \(\cdot\) 1 = 120.
Now consider the following claim:
[2] \(\forall\)n (Even(n!))
Consider the following “proof” of [2]: Let n = 4. Then n! = 24, which is even.
NOT A PROOF. We attempted to prove a universal claim with a single example.
But now consider the following proof that [2] is false: Let n = 1. Then n! = 1, which is odd.
PROOF: In this case, a single counterexample suffices to show that [2] is false.
(By the way, n = 1 is the only counterexample to this claim. You might try to prove:
[3] \(\forall\)n ((n > 1) (Even(n!))
Here is a proof:
If n > 1, then n! = n \(\cdot\) (n – 1) \(\cdot\) … \(\cdot\) 2 \(\cdot\) 1
Thus n! has 2 as a factor and thus is even.)
Exercises Exercises
1.
Hypothesis: It matters to be tall. More specifically, all US Presidents have been at least 6′ tall. Prove or disprove this claim.
Successfully proved that it is true.
Successfully proved that it is false.
2.
Let our universe of discourse be the positive integers. Consider the following claim:
[1] ∀x ((∃y (y ≥ x)) → (∃z (¬(z ≥ x))))
(In English, this says:
Every positive integer has the property that, if there exists some integer that is equal to or greater than it then there also exists an integer that is less (i. e., not greater than or equal) than it.)
We’d like to try to prove either that [1] is true or that it’s false. We’ve decided to look for counterexamples. Do it. Which of these statements is true:
There is exactly one counterexample that shows that [1] is false.
There are exactly two counterexamples, either of which would suffice to show that [1] is false.
There is an infinite number of counterexamples, any one of which would suffice to show that [1] is false.
There are no counterexamples. [1] is true.
Explanation: Notice that the “guard” in this case is always trivially satisfied since every number is equal to or greater than itself. So what we’re really trying to prove or disprove is the simpler claim:
[2] \(\forall\)x ( \(\exists\)z ( \(\neg\)(z \(\geq\) x)))
There is a single counterexample. The only positive integer for which there is no smaller positive integer is 1.
3.
Let our universe of discourse be the positive integers. Consider the following claim:
[1] ∀n (Prime(3n + 1))
We’d like to try to prove either that [1] is true or that it’s false. We’ve decided to look for counterexamples. Do it. Hint: Make a spreadsheet with one column for values of n and one column for the expression 3n + 1.
Which of these statements is true:
There is exactly one counterexample that shows that [1] is false.
There are exactly two counterexamples, either of which would suffice to show that [1] is false.
There are at least three counterexamples, any one of which would suffice to show that [1] is false.
There are no counterexamples. [1] is true.
Correct answer is C
4.
Let our universe of discourse be the positive integers. Prove or disprove:
[1] For all r, m, n, if r divides mn, then either r divides m or r divides n.
Do your proof. Now answer this question: Which of these statements is true:
[1] is true.
[1] is false because there’s a single counterexample.
[1] is false and there are multiple counterexamples.