Proof techniques I: direct proof and contrapositive

A proof is a sequence of statements, each justified by a definition, an axiom, an earlier result or a valid rule of inference, that ends with the statement to be proved. This lesson teaches the two most common techniques for proving conditional statements: direct proof and proof by contrapositive. It also covers how to disprove a universal claim with a counterexample and how to write proofs that other people can read and check.

The structure of a theorem

Most theorems have the shape \(\forall x\, (P(x) \to Q(x))\): for every object of some kind, if it has property \(P\) then it has property \(Q\). Often the universal quantifier is left implicit. If \(n\) is odd, then \(n^2\) is odd really means for every integer \(n\), if \(n\) is odd then \(n^2\) is odd. To prove a universal statement, you let \(x\) be an arbitrary object of the domain and prove the claim for that \(x\) using only properties every such object has. Because nothing special was assumed about \(x\), the argument works for all of them. This step is called universal generalization.

Proofs in this lesson use a few basic facts about integers: they are closed under addition, subtraction and multiplication; every integer is either even or odd and not both; and the definitions below.

Direct proof

A direct proof of \(P \to Q\) assumes \(P\) and uses definitions, algebra and known results to reach \(Q\). It is the natural method when the hypothesis gives you something concrete to work with, such as an equation. The pattern is always the same: write down what the hypothesis means, write down what the conclusion means, and connect them.

The comment at the end of that example points to a frequent error. Each time you use a definition, introduce a fresh variable. Writing \(b = ak\) and \(c = bk\) silently assumes the two multipliers are equal, and the proof would then cover only a special case.

Proof by contrapositive

Sometimes the hypothesis gives you little to work with, while the negation of the conclusion gives you a lot. In that case, prove the contrapositive \(\neg Q \to \neg P\), which lesson 2 showed is logically equivalent to \(P \to Q\). You assume the conclusion is false and show the hypothesis must be false too.

How do you decide which method to use? Try writing out the hypothesis and the negated conclusion. Whichever gives a concrete form, such as an equation you can substitute into, is usually the better starting point. Statements about something being not divisible, not rational or not prime often have awkward hypotheses, because not having a property is harder to work with than having one; the contrapositive turns them around.

If and only if

A biconditional \(P \longleftrightarrow Q\) is proved by proving two conditionals: \(P \to Q\) and \(Q \to P\). Each direction can use a different method. Combining this lesson's results, we have proved that for every integer \(n\), \(n\) is even if and only if \(n^2\) is even: one direction follows from the fact that the square of an even number is even (a one-line direct proof), and the other is the contrapositive example above.

Disproving with a counterexample

To show a universal statement \(\forall x\, P(x)\) is false, you need only one \(x\) for which \(P(x)\) is false. This is the quantifier negation rule of lesson 4 put to work. A counterexample must be specific and checkable: give the value and show the calculation. Python is an excellent counterexample hunter, because it can test thousands of cases in a second.

# Claim: for every positive integer n, n**2 - n + 11 is prime.
def is_prime(m):
    if m < 2:
        return False
    return all(m % d for d in range(2, int(m ** 0.5) + 1))

for n in range(1, 100):
    v = n * n - n + 11
    if not is_prime(v):
        print(f"counterexample: n = {n}, n^2 - n + 11 = {v} = 11 * {v // 11}")
        break

counterexample: n = 11, n^2 - n + 11 = 121 = 11 * 11

Here \(n = 11\) gives \(121 - 11 + 11 = 121 = 11^2\). You can also see why without searching: when \(n = 11\), every term has a factor of 11. Spotting the reason behind a counterexample often leads to a correct, weaker theorem.

A counterexample disproves only universal claims. An existential claim, \(\exists x\, P(x)\), is proved by exhibiting a single witness and disproved only by showing that no \(x\) works, which is a universal statement requiring proof. Do not confuse the two directions: one example can prove an existential claim or refute a universal one, but it can never prove a universal claim.

Writing proofs well

A proof is a piece of writing. In this course and in later ones, a proof is expected to be in complete sentences that a classmate could follow. A few conventions help readers.

The last convention addresses the most serious logical error in student proofs: starting from what you want to prove and working toward something true. Deriving a true statement from \(Q\) shows only \(Q \to \text{true}\), which is always true and says nothing about \(Q\). For instance, from \(1 = 2\) you can multiply both sides by 0 to get \(0 = 0\), which is true, but that does not make \(1 = 2\) true. Working backward is fine as scratch work to find a proof, but the final proof must run forward from the hypothesis.

Proof checking with Python

Python cannot prove a universal statement over an infinite domain, but it can check a proof's algebra. A symbolic algebra library such as SymPy can confirm that \((2k+1)^2 = 2(2k^2+2k)+1\). With only the standard library you can at least test the identity on many values, which catches slips in algebra before you rely on them.

import random
random.seed(272)
ok = all((2*k + 1)**2 == 2*(2*k*k + 2*k) + 1 for k in (random.randint(-10**6, 10**6) for _ in range(10000)))
print("identity (2k+1)^2 = 2(2k^2+2k)+1 holds on 10,000 random k:", ok)
# Divisibility transitivity, checked on random triples a | b, b | c
trials = 0
for _ in range(10000):
    a = random.randint(1, 50); m = random.randint(-50, 50); n = random.randint(-50, 50)
    b, c = a * m, a * m * n
    assert c % a == 0
    trials += 1
print("transitivity of divisibility held in", trials, "random cases")

identity (2k+1)^2 = 2(2k^2+2k)+1 holds on 10,000 random k: True
transitivity of divisibility held in 10000 random cases