Direct Proof and Counterexample I: Introduction to Proof Techniques
Section 4.1 – Direct Proof and Counterexample I: Introduction
Discovery and Proof
Discovery and proof are integral parts of problem-solving. When you believe a statement is true, try to understand why. Success validates your discovery, while failure provides insights into the problem and may reveal the statement’s falsity.
Assumptions
- This text assumes familiarity with basic algebra laws (see Appendix A).
- We utilize the three properties of equality: For all objects A, B, and C, (1) A = A, (2) if A = B then B = A, and (3) if A = B and B = C, then A = C.
- We assume no integer exists between 0 and 1 and that integers are closed under addition, subtraction, and multiplication. Results of these operations on integers remain integers.
- Most integer quotients are not integers. For example, 3 divided by 2 (3/2) is not an integer, and 3/0 is undefined.
Definitions
Understanding a statement’s truth or falsity requires comprehending its meaning and the definitions of its terms. Mathematicians emphasize precise definitions and encourage learning them verbatim.
Example 1 – Even and Odd Integers
Use the definitions of even and odd integers to justify your answers:
- a. Is 0 even? Yes, because 0 = 2 * 0.
- b. Is -301 odd? Yes, because -301 = 2 * (-151) + 1.
- c. If a and b are integers, is 6a2b even? Yes, because 6a2b = 2 * (3a2b), and since a and b are integers, so is 3a2b.
- d. If a and b are integers, is 10a + 8b + 1 odd? Yes, because 10a + 8b + 1 = 2 * (5a + 4b) + 1, and since a and b are integers, so is 5a + 4b.
- e. Is every integer either even or odd? Yes, although the proof is not immediately apparent.
Example 2 – Prime and Composite Numbers
- a. Is 1 prime? No, a prime number must be greater than 1.
- b. Is every integer greater than 1 either prime or composite? Yes. For any integer n greater than 1, consider all positive integer pairs r and s where n = rs. At least two such pairs exist: r = n and s = 1, and r = 1 and s = n.
- c. Write the first six prime numbers. 2, 3, 5, 7, 11, 13
- d. Write the first six composite numbers. 4, 6, 8, 9, 10, 12
Proving Existential Statements
A statement of the form “∃x ∈ D such that Q(x)” is true if and only if Q(x) is true for at least one x in D. Constructive proofs demonstrate this by finding or providing a method to find such an x.
Example 3 – Constructive Proofs of Existence
- a. Prove: ∃ an even integer n that can be written in two ways as a sum of two prime numbers. Let n = 10. Then 10 = 5 + 5 = 3 + 7, and 3, 5, and 7 are prime.
- b. Suppose r and s are integers. Prove: ∃ an integer k such that 22r + 18s = 2k. Let k = 11r + 9s. Then k is an integer, and 2k = 2 * (11r + 9s) = 22r + 18s.
Disproving Universal Statements by Counterexample
Disproving a statement means showing it’s false. To disprove “∀x in D, if P(x) then Q(x)”, we show its negation, “∃x in D such that P(x) and not Q(x)”, is true by finding a counterexample.
Method of Disproof by Counterexample
To disprove “∀x ∈ D, if P(x) then Q(x)”, find an x in D where P(x) is true and Q(x) is false. This x is a counterexample.
Example 4 – Disproof by Counterexample
Disprove: ∀ real numbers a and b, if a2 = b2 then a = b.
Counterexample: Let a = 1 and b = -1. Then a2 = 1 = b2, but a ≠ b.
Proving Universal Statements
Most mathematical statements are universal, often in the form “∀x ∈ D, if P(x) then Q(x)”. When D is finite or only finitely many elements satisfy P(x), the method of exhaustion can be used.
Example 5 – The Method of Exhaustion
Prove: ∀n ∈ Z, if n is even and 4 ≤ n ≤ 26, then n can be written as a sum of two prime numbers.
(This proof would involve checking each even integer from 4 to 26.)
Proving Universal Statements: Generalizing from the Generic Particular
A powerful technique for proving universal statements is generalizing from the generic particular. To show a property holds for all elements in a set, we consider an arbitrary element and demonstrate the property holds for it.
Example 6 – Generalizing from the Generic Particular
Consider the “trick”: Pick a number, add 5, multiply by 4, subtract 6, divide by 2, and subtract twice the original number. The result is always 7.
Let ‘x‘ represent the chosen number. Following the steps:
(x + 5) * 4 – 6) / 2 – 2x = (4x + 20 – 6) / 2 – 2x = (4x + 14) / 2 – 2x = 2x + 7 – 2x = 7
Regardless of the initial number, the result is always 7. This illustrates generalizing from a generic particular (x).
Proving Universal Statements: Method of Direct Proof
Applying the method of generalizing from the generic particular to “If P(x) then Q(x)” results in the method of direct proof. Since an if-then statement is false only when the hypothesis is true and the conclusion is false, we show the truth of P(x) necessitates the truth of Q(x).
Method of Direct Proof
- Express the statement as “∀x ∈ D, if P(x) then Q(x)”.
- Suppose x ∈ D and P(x) is true.
- Show Q(x) is true using definitions, established results, and logical inference.
Example 7 – A Direct Proof of a Theorem
Prove: The sum of any two even integers is even.
Theorem 4.1.1: The sum of any two even integers is even.
Proof: Suppose m and n are any even integers. [We must show that m + n is even.]
By definition of even, m = 2r and n = 2s for some integers r and s. Then
m + n = 2r + 2s = 2(r + s)
Let t = r + s. Note that t is an integer. Hence
m + n = 2t (where t is an integer)
It follows by definition of even that m + n is even. [This is what we needed to show.]
Getting Proofs Started
Understanding generalizing from the generic particular and direct proof allows you to begin proofs even for unfamiliar theorems. The starting point and conclusion depend on the statement’s structure, not its content.
Example 8 – Identifying the “Starting Point” and the “Conclusion to Be Shown”
Statement: Every complete, bipartite graph is connected.
Formal Restatement: ∀ graphs G, if G is complete and bipartite, then G is connected.
Starting Point: Suppose G is a graph that is complete and bipartite.
Conclusion to Be Shown: G is connected.
Showing That an Existential Statement Is False
Since the negation of an existential statement is universal, to prove an existential statement false, we prove its universal negation true.
Example 9 – Disproving an Existential Statement
Show the following is false: There is a positive integer n such that n2 + 3n + 2 is prime.
Claim: The statement “There is a positive integer n such that n2 + 3n + 2 is prime” is false.
Proof: Suppose n is any positive integer. [We will show that n2 + 3n + 2 is not prime.]
We can factor n2 + 3n + 2 as (n + 1)(n + 2).
Since n ≥ 1, both n + 1 > 1 and n + 2 > 1. Thus, n2 + 3n + 2 is a product of two integers greater than 1, and therefore not prime.