Subsection 8.4.3 Proof by Example
Let’s return to the problem of proving that something exists.
Approach 1: Sometimes it’s possible to do a nonconstructive proof by traditional forward reasoning.
Suppose that we want to prove that there exists someone who is Sandy’s mother. We have two premises:
[1] \(\forall\)x (Person(x) \(\rightarrow\) \(\exists\)y (MotherOf(y, x))) All people have mothers.
[2] Person(Sandy) Sandy is a person.
We need two steps to complete our proof:
[3] Person(Sandy) \(\rightarrow\) \(\exists\)y (MotherOf(y, Sandy)) Universal Instantiation [1]
[4] \(\exists\)y (MotherOf(y, Sandy)) Modus Ponens [2], [3]
So we know that Sandy has a mother, although we have no idea who that mother is.
But sometimes we may not be able to see how to make that approach work. When that happens, we can try what we’ll call a constructive approach: we actually build (show) the required object.
Approach 2: We may be able to prove that something exists simply by finding and exhibiting the required object. In this case, the hard part is usually to find the object. Once it’s found, actually writing the proof is often trivial.
Suppose that Chris is Sandy’s mother. We could then prove that Sandy has a mother simply by exhibiting Chris.
Prove that there exist even numbers.
Proof: 2 is an even number. Now we have to show that it really is. By definition, a number is even if it is divisible by 2, which 2 is: 2 = 2*1.
Prove that there exist two prime numbers whose sum is prime.
Proof: There are many examples that work. But we’ll show a simple one: 2 + 3 = 5.
Approach 3: Suppose that we want to prove not just the existence of one individual (e. g., one prime number or one buffalo). Instead, we want to show that every prime number has a successor or that, for every buffalo, there exists a head (for sure, not the same head for every buffalo). Now what we might do is to describe an algorithm that, when given an individual object, finds the required associated one. We’ll talk about this more later in a separate section on proof by construction.
Exercises Exercises
1.
Prove that there exists a multidigit prime all of whose digits are the same.
Find an example that proves this claim.
2.
Recall Goldbach’s conjecture:
Every even integer greater than 2 can be expressed as the sum of two primes.
By the way, recall that 1 is not a prime. The smallest prime is 2.
Can even integers be expressed as the sum of two primes in more than one way? Try to prove this claim:
There exists an even integer greater than 2 that can be expressed in two different ways as the sum of two primes (where a+b and b+a don’t count as different).
Which of the following is true:
There is no such even integer.
There is an integer less than 10 that proves the claim.
There is an integer greater than 20 that proves the claim.
3.
Define: An integer n is a perfect square if there exists some integer k such that n = k2. For example, 100 is a perfect square because it is equal to 102.
Prove that there exist distinct positive integers m, n, and r such that each is a perfect square and m = n + r. (Hint: When you need to look for integers, it’s often a good idea to start small. If you try that and it doesn’t work, a good next strategy is to write a program to do the looking. But you won’t have to do that for this problem.)