Proof technique

Mathematicians do not write derivations in the notation of the previous lessons, and they are not being sloppy.

A published proof is written in English, with symbols where they help, and it leaves out every step a competent reader can supply. What makes it a proof rather than a persuasive essay is that each of its moves corresponds to a rule already established here, so the gaps are known to be fillable. This lesson goes through the standard techniques and names the rule behind each, which is the point where the machinery starts paying for itself. It closes with induction, which is the exception: a technique that is indispensable and is not a rule of logic.

Direct proof

The plainest structure assumes the hypothesis and reasons to the conclusion. Formally it is conditional proof from the seventh lesson: assume the antecedent, derive the consequent, discharge.

Claim: the sum of two odd integers is even. An odd integer is by definition $2 k + 1$ for some integer $k$ , so take $2 k + 1$ and $2 m + 1$ . Their sum is $2 k + 2 m + 2 = 2 (k + m + 1)$ , and $k + m + 1$ is an integer, so the sum is even.

Three features are worth naming because they recur. The proof began by replacing the word "odd" with its definition, which is the only move that ever gets a proof started. It used letters for arbitrary integers, so the conclusion generalises by universal introduction, and the restriction from the eleventh lesson is satisfied because nothing was assumed about $k$ or $m$ . And it ended by checking that the result matched the definition of the target property, which is the step careless proofs omit.

Contraposition

Some claims resist a frontal attack. To show that if $n^{2}$ is even then $n$ is even, the hypothesis $n^{2} = 2 k$ gives nothing to factor.

Prove the contrapositive instead. By the fifth lesson, $P \to Q$ and $\neg Q \to \neg P$ are equivalent, so proving one proves the other, and the swap is licensed by substitution rather than by taste. So assume $n$ is odd: $n = 2 k + 1$ gives $n^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1$ , which is odd. Done, and the direct version was never attempted.

The technique is worth reaching for whenever the hypothesis is an existence-free negative claim or the conclusion is a negation, since those are the shapes that leave nothing to manipulate. And it must be kept apart from proving the converse, $Q \to P$ , which is a different statement and proves nothing about the original.

Example. Prove that if $m n$ is odd then both $m$ and $n$ are odd.

The conclusion is a conjunction, so its negation is a disjunction and a direct attack would need cases. Contraposition is cleaner: assume not both are odd, so at least one is even, say $m = 2 k$ . Then $m n = 2 k n$ , which is even. That establishes the contrapositive and therefore the claim. Note the use of De Morgan to turn "not both odd" into "at least one even", which is the fifth lesson's law doing quiet work in an ordinary sentence.

Now you. Prove that if $n^{3}$ is even then $n$ is even.

Answer

Contrapositive: assume $n$ is odd, so $n = 2 k + 1$ . Then $n^{3} = (2 k + 1)^{3} = 8 k^{3} + 12 k^{2} + 6 k + 1 = 2 (4 k^{3} + 6 k^{2} + 3 k) + 1$ , which is odd. So an even $n^{3}$ forces an even $n$ .

Contradiction

Proof by contradiction assumes the negation of the target and derives an impossibility, which is negation introduction followed by double negation elimination. It is the technique that most needs the classical rule of the seventh lesson, and it is why intuitionists restrict it.

Claim: $\log_{2} 3$ is irrational. Suppose it were rational, so $\log_{2} 3 = p / q$ with $p$ and $q$ positive integers. Then $2^{p / q} = 3$ , and raising both sides to the power $q$ gives

2^{p} = 3^{q}

The left side is even, since $p \geq 1$ . The right side is odd, since a product of odd numbers is odd. An integer cannot be both, so the assumption fails and $\log_{2} 3$ is irrational. The whole proof is four lines, and the only fact it needs is that 2 and 3 have different parities.

Two cautions. First, a proof by contradiction should end at a genuine contradiction, a formula and its negation, not at something merely surprising. Second, contradiction is often used where a direct proof exists and is clearer: if the assumed negation is never really used, the proof is direct with a wrapper around it, and removing the wrapper improves it.

Cases

Argument by cases is disjunction elimination: establish a disjunction that covers all possibilities, then derive the conclusion from each disjunct.

Claim: $n^{2} + n$ is even for every integer $n$ . Either $n$ is even or it is odd, which is an instance of excluded middle and exhausts the possibilities. If $n = 2 k$ , then $n^{2} + n = 4 k^{2} + 2 k = 2 (2 k^{2} + k)$ , even. If $n = 2 k + 1$ , then $n^{2} + n = (4 k^{2} + 4 k + 1) + (2 k + 1) = 4 k^{2} + 6 k + 2 = 2 (2 k^{2} + 3 k + 1)$ , even. Both cases give the same conclusion, so it holds.

The discipline is that the cases must be exhaustive, and that failing to check one is the standard error. They need not be exclusive: overlapping cases are fine, since the rule asks only that each disjunct yield the conclusion.

Example. Prove that $n^{2} + n$ is even without cases, and say which is better.

Factor it: $n^{2} + n = n (n + 1)$ , a product of consecutive integers, one of which must be even, so the product is even. This is shorter and it explains why the result holds, while the case proof only verifies that it does. When both are available, prefer the one that exhibits the reason.

Now you. Prove that for every integer $n$ , $n^{3} - n$ is divisible by 3, using cases on the remainder of $n$ on division by 3.

Answer

Every integer is $3 k$ , $3 k + 1$ or $3 k + 2$ . Factor first: $n^{3} - n = (n - 1) n (n + 1)$ , three consecutive integers. If $n = 3 k$ the middle factor is divisible by 3; if $n = 3 k + 1$ then $n - 1 = 3 k$ is; if $n = 3 k + 2$ then $n + 1 = 3 k + 3$ is. In every case one factor carries the 3, so the product does.

Existence, uniqueness and counterexample

An existence proof is existential introduction: produce an object and verify it. Such proofs come in two kinds, and the difference matters. A constructive proof exhibits the thing; a non-constructive one shows that it must exist without producing it.

The standard illustration: are there irrational numbers $a$ and $b$ with $a^{b}$ rational? Consider ${\sqrt{2}}^{\sqrt{2}}$ . Either it is rational, in which case $a = b = \sqrt{2}$ works, or it is irrational, in which case take $a = {\sqrt{2}}^{\sqrt{2}}$ and $b = \sqrt{2}$ , giving $a^{b} = {\sqrt{2}}^{2} = 2$ , which is rational. Either way such a pair exists, and the proof does not say which case holds. It runs on excluded middle, and an intuitionist rejects it for exactly that reason.

A uniqueness proof is the second half of the twelfth lesson's "exactly one": assume two objects both have the property and show they are identical. Existence and uniqueness are separate obligations and a proof owing both must discharge both.

A counterexample refutes a universal claim, and the ninth lesson's negation law says why one is enough: $\neg \forall x φ$ is $\exists x \neg φ$ , so refuting "all" requires producing exactly one. A nineteenth-century conjecture held that every odd composite number is a prime plus twice a square. It holds for 9, for 15, for 21 and for every odd composite up to 5775. It fails at 5777, and again at 5993, and at no other number below 12,000. One number ends the conjecture, and no amount of prior agreement rescues it.

Induction, and why it is not a rule of logic

Mathematical induction proves $S (n)$ for every natural number by proving $S (0)$ and proving $S (n) \to S (n + 1)$ for arbitrary $n$ . The second part is conditional proof and the first is a single check, so both halves are familiar. What is not familiar is the step from those two to the universal conclusion.

That step is not licensed by any rule in this course. From $S (0)$ and $\forall n (S (n) \to S (n + 1))$ , the rules of the eleventh lesson give $S (1)$ , then $S (2)$ , then $S (3)$ , one at a time and never all of them, because a derivation is finite. The universal conclusion needs an extra principle, and in the standard treatment it is an axiom: the induction schema of Peano arithmetic, one axiom for each formula $S$ , asserting exactly that the two halves give the universal claim.

So induction is a truth about the natural numbers rather than a truth of logic. It holds because the natural numbers are generated by starting at zero and adding one, with nothing else in there, and a structure without that property does not support it. Recognising this is what stops induction from looking circular: it is not being derived, it is being assumed, and assuming it is what fixes which structure is being talked about.

The eleventh lesson's completeness theorem still applies to the logic, so anything that genuinely follows from the Peano axioms has a derivation. What Gödel showed in 1931 is that the axioms do not settle everything: any consistent system strong enough for arithmetic leaves true statements about the natural numbers unprovable within it. That is a limit on axiom systems, not on the proof rules, and the last lesson returns to it.

Example. Prove by induction that the sum of the first $n$ positive integers is $n (n + 1) / 2$ .

Base case: for $n = 1$ the sum is 1 and $1 \times 2 / 2 = 1$ . Inductive step: assume the sum to $n$ is $n (n + 1) / 2$ . Then the sum to $n + 1$ is $n (n + 1) / 2 + (n + 1) = (n + 1) (n + 2) / 2$ , which is the formula with $n + 1$ in place of $n$ . Both parts hold, so the formula holds for every $n$ . Note the assumption in the step is about one particular $n$ , not about all of them, and confusing those two is what makes induction look like question-begging.

Now you. Where exactly does a proof by induction use conditional proof, and where does it use the extra axiom?

Answer

Conditional proof appears in the inductive step, where $S (n)$ is assumed and $S (n + 1)$ derived, then discharged into $S (n) \to S (n + 1)$ , which is then generalised. The extra axiom is used at the very end, to pass from the base case and the universally quantified conditional to $\forall n S (n)$ , and no rule of first-order logic licenses that step.

What a finished proof owes the reader

A proof is complete when every step is one a reader could expand into the rules of this course, and that is a lower standard than writing them out and a much higher one than sounding convincing.

Three checks catch most failures. Every term used has been defined or is standard. Every case has been covered, and the cases exhaust the possibilities. Every quantifier the proof generalises over was genuinely arbitrary, which is the eleventh lesson's restriction and the source of the classic error of proving something about "an arbitrary $n$ " after assuming $n$ was prime.

That is the whole of the formal apparatus, applied. What remains is the harder question the subject has been postponing since the first lesson: whether an argument that passes every test here is therefore a good argument. It is not, and the reasons are worth a lesson.