# Lecture 7. Proofing (methods of proof) ## Overview Lecture 6 gave us the **semantics** of propositional logic: truth tables, satisfiability, and the notion of a **tautology** (a formula true under every truth assignment). This lecture turns to the **syntax and practice of proof** — how we move from statements we accept (**premises**, or hypotheses) to statements we thereby establish (**conclusions**), and how we prove mathematical theorems. Two closely related ideas run through the whole lecture: - A **proof** is a finite sequence of statements, each of which is either an accepted premise, an axiom, or follows from earlier statements by a **rule of inference**. - Every legitimate rule of inference is nothing more than a **tautology in disguise**: the rule "from $A_1, A_2, \dots, A_n$ infer $B$" is valid exactly when the implication $$ A_1 \wedge A_2 \wedge \dots \wedge A_n \to B $$ is a tautology. We first make that connection precise, catalogue the standard rules of inference, build several formal derivations, and then study the informal-but-rigorous techniques used to prove ordinary mathematical statements: direct proof, contraposition, contradiction, cases/exhaustion, existence and uniqueness, counterexamples, and mathematical induction (both weak and strong). We close with the classic fallacies that *look* like valid rules but are not, a short history, exercises, and hints. This is the craft at the heart of every later lecture. Number theory, combinatorics, graph theory, the analysis of algorithms — all of it is stated as theorems and believed only once proved. Learning the methods here is learning the language in which the rest of the subject is written. ## 7.1 What is a proof, and why rigor? Mathematics is unusual among human activities: its claims are not merely *supported* by evidence, they are *settled*. Once a theorem is correctly proved it is true forever, with no exceptions, in every model of its hypotheses. A **proof** is what produces that certainty. > **Definition (proof, informal).** A **proof** of a statement $S$ is a finite chain of reasoning that establishes $S$ beyond any doubt, in which every step is either a definition, a previously established result (axiom, theorem, lemma), a hypothesis, or a consequence of earlier steps by a valid rule of inference. A **rigorous** proof is one in which every such step could, in principle, be expanded into the fully formal derivations of §7.4. The vocabulary of mathematical results: - A **theorem** is a statement that has been proved true. - A **proposition** is a theorem of lesser importance. - A **lemma** is an auxiliary theorem proved mainly as a stepping stone to a bigger one. - A **corollary** is a theorem that follows almost immediately from another. - A **conjecture** is a statement believed true but not yet proved (e.g. the Goldbach conjecture: every even integer $> 2$ is a sum of two primes). - An **axiom** (or **postulate**) is a statement accepted *without* proof, a starting point. - A **definition** fixes the exact meaning of a term. Proofs live or die on definitions: to prove "$n$ is odd," you must know that *odd* means "$n = 2k+1$ for some integer $k$." **Why rigor matters: patterns lie.** Empirical evidence — "it worked for the first thousand cases" — is not proof. Mathematics is full of patterns that hold for a long time and then break. - The polynomial $f(n) = n^2 + n + 41$ (studied by Euler) is **prime** for every $n = 0, 1, 2, \dots, 39$. It is tempting to conjecture it is always prime. But $f(40) = 40^2 + 40 + 41 = 1681 = 41^2$ is composite. - Pierre de Fermat conjectured that every **Fermat number** $F_n = 2^{2^n} + 1$ is prime. Indeed $F_0=3,\,F_1=5,\,F_2=17,\,F_3=257,\,F_4=65537$ are all prime. In 1732 Euler showed $F_5 = 2^{32}+1 = 4294967297 = 641 \times 6700417$ is composite. No further Fermat prime has ever been found. - Euler conjectured (1769) that a fifth power is never the sum of four positive fifth powers. In 1966 Lander and Parkin found, by computer search, $$ 27^5 + 84^5 + 110^5 + 133^5 = 144^5, $$ demolishing the conjecture (both sides equal $61\,917\,364\,224$). **Common pitfall.** *Verifying finitely many cases proves nothing about the infinitely many you did not check* — unless the statement itself only concerns finitely many cases (proof by exhaustion, §7.10). A universally quantified claim "$\forall n\, P(n)$" over an infinite domain requires a general argument, typically induction (§7.11–7.12) or a direct/indirect proof. **Remark (proofs versus discovery).** The polished proof you read is rarely the messy path by which it was found. Experiment, examples, and pattern-spotting are indispensable for *discovering* what is true; proof is how you *confirm* it. This lecture is about confirmation. ## 7.2 From semantics to syntax: tautological implication Recall from Lecture 6 that a **tautology** is a formula true under every truth assignment. We now connect this semantic notion to the act of inferring. > **Definition (tautological implication / logical consequence).** A formula $B$ is a **tautological consequence** of formulas $A_1, \dots, A_n$, written $A_1, \dots, A_n \models B$, when every truth assignment that makes all of $A_1, \dots, A_n$ true also makes $B$ true. The central theorem linking semantics to proof is the following equivalence — the **semantic deduction theorem** already proved in Lecture 6 (Theorem 6.15), restated here as a licence to infer. > **Justification theorem.** $A_1, \dots, A_n \models B$ **if and only if** the single formula $A_1 \wedge A_2 \wedge \dots \wedge A_n \to B$ is a **tautology**. *Proof.* ($\Leftarrow$) Suppose $A_1 \wedge \dots \wedge A_n \to B$ is a tautology, and take any assignment making all $A_i$ true. Then the antecedent $A_1 \wedge \dots \wedge A_n$ is true. An implication with a true antecedent can be true only if its consequent is true; since the whole implication is true (being a tautology), $B$ is true. Hence every assignment satisfying all premises satisfies $B$, i.e. $A_1,\dots,A_n \models B$. ($\Rightarrow$) Conversely suppose $A_1,\dots,A_n \models B$. Consider any assignment. If it makes all $A_i$ true, then by hypothesis it makes $B$ true, so the implication reads $\text{T}\to\text{T}=\text{T}$. If it makes some $A_i$ false, the antecedent is false and the implication reads $\text{F}\to(\cdot)=\text{T}$. Either way the implication is true, so it is a tautology. ∎ This is exactly the schema on the slides: $A \to B$ and, more generally, $A_1 \wedge A_2 \wedge \dots \wedge A_n \to B$. It is what makes **deductive proof** trustworthy: certify *once* (by a truth table, or algebraically) that a given implication is a tautology, and you may use it *forever* as a licence to write $B$ beneath any premises matching $A_1, \dots, A_n$ — regardless of what the letters concretely mean. Truth is *transmitted* from premises to conclusion. > **Definition (deductive / truth-preserving reasoning).** Reasoning in which the conclusion is **guaranteed** true whenever the premises are true. It contrasts with **inductive/empirical** reasoning (a physicist generalizing from experiments), where true premises make a conclusion only *probable*. Everything in this lecture is deductive. **Remark (soundness in one sentence).** A rule of inference is called **sound** precisely when its guaranteeing implication is a tautology. Soundness is the whole game: an unsound "rule" can lead from true premises to a false conclusion, and a single such rule would let us "prove" anything. This is why §7.16's fallacies are dangerous — they are unsound rules dressed up to look sound. ## 7.3 Rules of inference > **Definition (rule of inference).** A **rule of inference** is a fixed pattern "premises $\Rightarrow$ conclusion" whose associated implication is a tautology. We write a rule as a fraction: premises above the line, conclusion below. > $$ \frac{A_1 \quad A_2 \quad \dots \quad A_n}{\therefore\; B} $$ ![Four core rules of inference: modus ponens, modus tollens, hypothetical and disjunctive syllogism](img/l07_inference.png) The table below lists the standard propositional rules. The middle column gives the "introduction/elimination" names used on the slides (Ukrainian axiomatic tradition), the last column the guaranteeing tautology — you can verify any of them with a truth table. | Rule (standard name) | Slide name | Premises | Conclusion | Guaranteeing tautology | |---|---|---|---|---| | **Modus ponens** | Separation rule | $A,\; A \to B$ | $B$ | $\big(A \wedge (A\to B)\big)\to B$ | | **Modus tollens** | Negative separation rule | $A \to B,\; \neg B$ | $\neg A$ | $\big((A\to B)\wedge \neg B\big)\to \neg A$ | | **Hypothetical syllogism** | Hypothetical syllogism | $A \to B,\; B \to C$ | $A \to C$ | $\big((A\to B)\wedge(B\to C)\big)\to(A\to C)$ | | **Disjunctive syllogism** | Removing disjunction | $A \vee B,\; \neg A$ | $B$ | $\big((A\vee B)\wedge \neg A\big)\to B$ | | **Addition** | Including disjunction | $A$ | $A \vee B$ | $A \to (A\vee B)$ | | **Simplification** | Removing conjunction | $A \wedge B$ | $A$ | $(A\wedge B)\to A$ | | **Conjunction** | Including conjunction | $A,\; B$ | $A \wedge B$ | $\big(A \wedge B\big)\to(A\wedge B)$ | | **Resolution** | — | $A \vee B,\; \neg A \vee C$ | $B \vee C$ | $\big((A\vee B)\wedge(\neg A\vee C)\big)\to(B\vee C)$ | | **Contraposition** | Implication contraposition | $A \to B$ | $\neg B \to \neg A$ | $(A\to B)\leftrightarrow(\neg B\to \neg A)$ | A few remarks on the most important rules: - **Modus ponens** ($A,\ A\to B \therefore B$) is the workhorse rule; in the axiomatic tradition it is called the **separation rule** because it "separates" $B$ off the implication. Almost every direct proof is a chain of modus ponens steps. - **Modus tollens** propagates falsity *backwards*: knowing the consequent fails, the antecedent must fail too. It is the engine of proof by contraposition (§7.8). - **Disjunctive syllogism** is elimination by ruling out alternatives ("it is $A$ or $B$; it is not $A$; therefore $B$"). It powers proof by cases when one case is excluded. - **Resolution** is the single rule on which automated theorem provers and SAT solvers are built (see §7.5). From $A \vee B$ and $\neg A \vee C$, the complementary pair $A / \neg A$ "cancels," leaving $B \vee C$. Disjunctive syllogism is the special case where $C$ is empty. **Verifying a rule (worked example).** Let us confirm modus tollens is sound by truth table, i.e. that $\big((A\to B)\wedge \neg B\big)\to \neg A$ is a tautology. | $A$ | $B$ | $A\to B$ | $\neg B$ | $(A\to B)\wedge\neg B$ | $\neg A$ | whole $\to$ | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | F | F | T | T | T | T | T | | F | T | T | F | F | T | T | | T | F | F | T | F | F | T | | T | T | T | F | F | F | T | The last column is all T, so the rule is sound. Notice the only row where the antecedent $(A\to B)\wedge\neg B$ is true is the first, and there $\neg A$ is also true — exactly as the Justification theorem predicts. ### 3.1 Rules of inference for quantified statements Ordinary mathematics quantifies over infinite domains ("for all integers $n$…", "there exists a real $x$…"), so we also need rules that strip and attach quantifiers. These are used silently in every proof below. | Rule | From | Infer | Caveat | |---|---|---|---| | **Universal instantiation** | $\forall x\, P(x)$ | $P(c)$ | $c$ any element of the domain | | **Universal generalization** | $P(c)$ with $c$ **arbitrary** | $\forall x\, P(x)$ | $c$ must be genuinely arbitrary — no special assumptions about it | | **Existential instantiation** | $\exists x\, P(x)$ | $P(c)$ | $c$ a **new** name for some witness | | **Existential generalization** | $P(c)$ for some particular $c$ | $\exists x\, P(x)$ | — | **Common pitfall (universal generalization).** To prove "$\forall x\, P(x)$" by taking an arbitrary $c$ and proving $P(c)$, you may assume *nothing* about $c$ beyond membership in the domain. If your argument secretly uses "let $c$ be even" or "let $c=0$", you have proved only a special case, not the universal statement. ## 7.4 Formal derivations from premises > **Definition (formal derivation).** A **formal derivation (proof)** of $B$ from premises $\Gamma = \{A_1, \dots, A_n\}$, written $\Gamma \vdash B$, is a finite numbered list of formulas ending in $B$, where each line is either a premise or is obtained from earlier lines by a rule of inference. Every line carries a **justification** naming the rule and the line numbers used. The turnstile $\vdash$ ("yields", provability, a *syntactic* notion) mirrors $\models$ ("entails", a *semantic* notion). Because our rules are exactly the tautological ones, the two agree: $\Gamma \vdash B$ precisely when $\Gamma \models B$. That two-way agreement is the **soundness** ($\vdash \Rightarrow \models$) and **completeness** ($\models \Rightarrow \vdash$) of propositional calculus. **Example 7.1 (a complete derivation).** Show that $\{\,p \to q,\ \ q \to r,\ \ \neg r,\ \ p \vee s\,\} \vdash s$. | # | Formula | Justification | |---|---|---| | 1 | $p \to q$ | premise | | 2 | $q \to r$ | premise | | 3 | $\neg r$ | premise | | 4 | $p \vee s$ | premise | | 5 | $p \to r$ | hypothetical syllogism, 1, 2 | | 6 | $\neg p$ | modus tollens, 5, 3 | | 7 | $s$ | disjunctive syllogism, 4, 6 | Each step is licensed by a rule from the table, so line 7 is established: $s$ follows from the four premises. ∎ **Example 7.2 (a derivation using conjunction and simplification).** Show $\{\,p \wedge q,\ \ p \to r,\ \ q \to t\,\} \vdash r \wedge t$. | # | Formula | Justification | |---|---|---| | 1 | $p \wedge q$ | premise | | 2 | $p \to r$ | premise | | 3 | $q \to t$ | premise | | 4 | $p$ | simplification, 1 | | 5 | $q$ | simplification, 1 | | 6 | $r$ | modus ponens, 2, 4 | | 7 | $t$ | modus ponens, 3, 5 | | 8 | $r \wedge t$ | conjunction, 6, 7 | ∎ **Example 7.3 (a derivation with quantifiers — the Socrates syllogism).** From "All humans are mortal" and "Socrates is human," derive "Socrates is mortal." Let $H(x)$ mean "$x$ is human" and $M(x)$ "$x$ is mortal." | # | Formula | Justification | |---|---|---| | 1 | $\forall x\,(H(x) \to M(x))$ | premise | | 2 | $H(\text{Socrates})$ | premise | | 3 | $H(\text{Socrates}) \to M(\text{Socrates})$ | universal instantiation, 1 | | 4 | $M(\text{Socrates})$ | modus ponens, 3, 2 | ∎ **Common pitfall (order and scope).** A line may cite only lines *above* it. You cannot justify line 5 using line 7. And a rule must match its pattern *exactly*: to apply modus ponens you need both $A$ and the whole implication $A \to B$ present on earlier lines — having $A$ and $B\to A$ does not license anything. ## 7.5 The resolution rule and refutation **Resolution** deserves its own section because it is the basis of practical automated reasoning. It operates on formulas in **conjunctive normal form (CNF)** — a conjunction of **clauses**, where each clause is a disjunction of **literals** (variables or negated variables). > **Definition (resolution rule).** From two clauses that contain a complementary pair of literals, > $$ \frac{(A \vee B) \qquad (\neg A \vee C)}{\therefore\; B \vee C}, $$ > infer the **resolvent** $B \vee C$, obtained by deleting the complementary pair $A, \neg A$ and disjoining what remains. Resolving $A$ with $\neg A$ alone yields the **empty clause** $\square$, which represents $\bot$ (falsehood). ![The resolution rule: cancel the complementary pair A / ¬A to obtain the resolvent B ∨ C](img/l07_resolution.png) **Refutation.** To prove $\Gamma \vdash B$ by resolution, one shows that $\Gamma \cup \{\neg B\}$ is unsatisfiable: convert everything to CNF and derive the empty clause $\square$. Reaching $\square$ means the premises together with the *negation* of the goal are contradictory, so the goal follows. This is **proof by refutation**, the contradiction method (§7.9) mechanized. **Example 7.4 (resolution refutation).** Prove $\{\,p \to q,\ q \to r,\ p\,\} \vdash r$. Negate the goal and convert to clauses. Using $p \to q \equiv \neg p \vee q$: $$ \{\ \neg p \vee q,\quad \neg q \vee r,\quad p,\quad \neg r\ \}. $$ Now resolve: | # | Clause | From | |---|---|---| | 1 | $\neg p \vee q$ | premise ($p\to q$) | | 2 | $\neg q \vee r$ | premise ($q\to r$) | | 3 | $p$ | premise | | 4 | $\neg r$ | negated goal | | 5 | $q$ | resolve 3 & 1 (on $p$) | | 6 | $r$ | resolve 5 & 2 (on $q$) | | 7 | $\square$ | resolve 6 & 4 (on $r$) | The empty clause appears, so $\{p\to q,\ q\to r,\ p,\ \neg r\}$ is unsatisfiable; therefore $r$ follows from the three premises. ∎ **Remark (why CS cares).** A **SAT solver** decides whether a CNF formula is satisfiable; modern solvers use conflict-driven clause learning, a refined resolution. Resolution refutation underlies logic programming (Prolog's execution model is a restricted resolution called SLD-resolution) and many verification tools. That an entire industry rests on one tautology is a striking illustration of §7.2. ## 7.6 The substitution rule and propositional calculus Beyond rules that combine *whole* formulas, we need a rule that lets us **instantiate** a proven schema. > **Definition (substitution rule).** Let $F_1$ be a propositional formula and $A$ an *atomic* formula (a single propositional variable). If $F_1$ is a tautology (or theorem) containing $A$, then the formula obtained by replacing **every** occurrence of $A$ in $F_1$ by an arbitrary formula $F_2$ is again a tautology (theorem). *The replacement must be uniform: all occurrences of $A$, and only $A$, are replaced.* (This is distinct from the **replacement** rule of Lecture 6, Theorem 6.6, which swaps a subformula for a **logically equivalent** one; here an **atom** is replaced by an **arbitrary** formula.) For example, from the tautology $A \vee \neg A$ we may substitute $A := (p \wedge q)$ to obtain the tautology $(p\wedge q)\vee \neg(p\wedge q)$. **Common pitfall.** Non-uniform substitution destroys validity. From the tautology $A \to A$, replacing only the *first* $A$ by $p\wedge q$ gives $(p \wedge q) \to A$, which is **not** a tautology (false when $p, q$ true and $A$ false). These ideas let us define an **axiomatic propositional calculus** as a triple: - **Language** — the set of well-formed formulas built from propositional variables and connectives, e.g. over connective set $\{\to, \neg\}$. - **Postulates (axiom schemas)** — a chosen set of universally valid formulas taken as starting points. A classic three-schema (Hilbert-style) system is $$ \textbf{A1: } A \to (B \to A), $$ $$ \textbf{A2: } \big(A \to (B \to C)\big) \to \big((A \to B) \to (A \to C)\big), $$ $$ \textbf{A3: } (\neg B \to \neg A) \to (A \to B). $$ - **Rules** — laws for producing new theorems from old, here just the **separation rule (modus ponens)** and the **substitution rule**. A **theorem** of the calculus is any formula obtainable from the postulates by finitely many applications of the rules. This is the purely *syntactic* face of logic: theorems are generated by symbol manipulation, and the completeness theorem guarantees that the theorems are exactly the tautologies. We now leave the formal calculus and study the **informal but rigorous** proofs of everyday mathematics. Every technique below is ultimately justified by the rules above; we simply stop writing out each line. ## 7.7 Direct proof > **Definition (direct proof).** To prove an implication $p \to q$, **assume** $p$ is true and, through a chain of valid inferences and definitions, **derive** that $q$ is true. (An unconditional statement is proved the same way, with no antecedent to assume.) We use two standard definitions throughout: an integer $n$ is **even** if $n = 2k$ for some integer $k$, and **odd** if $n = 2k+1$ for some integer $k$. An integer $a$ **divides** $b$ (written $a \mid b$) if $b = ac$ for some integer $c$. **Example 7.5.** *If $n$ is an odd integer, then $n^2$ is odd.* *Proof.* Assume $n$ is odd, so $n = 2k + 1$ for some integer $k$. Then $$ n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2\,(2k^2 + 2k) + 1. $$ Put $t = 2k^2 + 2k$, an integer. Then $n^2 = 2t + 1$, which is by definition odd. ∎ **Example 7.6.** *The sum of two even integers is even.* *Proof.* Let $a, b$ be even, say $a = 2s$ and $b = 2t$ for integers $s, t$. Then $a + b = 2s + 2t = 2(s+t)$, and $s+t$ is an integer, so $a+b$ is even. ∎ **Example 7.7 (transitivity of divisibility).** *For all integers $a, b, c$: if $a \mid b$ and $b \mid c$, then $a \mid c$.* *Proof.* Assume $a \mid b$ and $b \mid c$. Then $b = a s$ and $c = b t$ for some integers $s, t$. Substituting, $c = b t = (a s) t = a (s t)$. Since $st$ is an integer, $a \mid c$. ∎ **Example 7.8.** *If $n$ is even, then $(-1)^n = 1$.* *Proof.* Assume $n$ is even, so $n = 2k$. Then $(-1)^n = (-1)^{2k} = \big((-1)^2\big)^k = 1^k = 1.$ ∎ **Example 7.9 (a sharper fact needing a lemma).** *If $n$ is odd, then $n^2 \equiv 1 \pmod 8$ — that is, $8 \mid (n^2 - 1)$.* *Proof.* First a **lemma**: the product of two consecutive integers $m(m+1)$ is always even. Indeed, one of $m, m+1$ is even; if $m = 2j$ then $m(m+1) = 2j(m+1)$, and if $m+1 = 2j$ then $m(m+1) = 2jm$ — either way the product is $2\times(\text{integer})$. Now assume $n$ is odd, $n = 2k+1$. Then $$ n^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1. $$ By the lemma $k(k+1)$ is even, say $k(k+1) = 2m$. Hence $n^2 = 4(2m) + 1 = 8m + 1$, so $n^2 - 1 = 8m$ and $8 \mid (n^2-1)$. ∎ **Remark (trivial and vacuous proofs).** Two degenerate but legitimate direct proofs of $p \to q$ deserve names. A **trivial proof** establishes $q$ outright, without using $p$ at all (then $p\to q$ is automatically true). A **vacuous proof** shows $p$ is false, so $p \to q$ is true "by default." Example (vacuous): *"If $n$ is both even and odd, then $n = n+1$"* is true because no integer is both even and odd — the hypothesis is never satisfied. ### 7.1 Biconditionals and equivalences (iff, TFAE) To prove a **biconditional** $P\iff Q$, prove the two implications **separately**: $P\Rightarrow Q$ *and* $Q\Rightarrow P$ (each by whatever method fits — direct, contrapositive, or contradiction). Both directions are required; proving only one is the single most common gap. *Example:* "$n$ is even $\iff n^2$ is even" needs $n\text{ even}\Rightarrow n^2\text{ even}$ (direct) **and** $n^2\text{ even}\Rightarrow n\text{ even}$ (contrapositive: $n$ odd $\Rightarrow n^2$ odd). To prove several statements **all equivalent** — "**TFAE:** $P_1,\dots,P_k$" — it suffices to prove one **cycle** of implications $P_1\Rightarrow P_2\Rightarrow\cdots \Rightarrow P_k\Rightarrow P_1$: any statement then implies any other by following the cycle. That is $k$ implications instead of the $k(k-1)$ ordered pairs. ## 7.8 Proof by contraposition > **Definition (proof by contraposition).** Instead of proving $p \to q$ directly, prove its **contrapositive** $\neg q \to \neg p$. The two are logically equivalent, so a proof of one is a proof of the other. ![Contraposition: prove ¬Q → ¬P instead of P → Q](img/l07_contraposition.png) The equivalence is itself a tautology, confirmed by the truth table: | $p$ | $q$ | $p \to q$ | $\neg q \to \neg p$ | |:-:|:-:|:-:|:-:| | F | F | T | T | | F | T | T | T | | T | F | F | F | | T | T | T | T | Columns 3 and 4 are identical, so $p \to q \equiv \neg q \to \neg p$. Contraposition is the method of choice when the *negated* statements are easier to compute with than the originals — typically when $q$ is a negative or existential claim. **Common pitfall (contrapositive vs. converse).** The contrapositive of $p \to q$ is $\neg q \to \neg p$ (equivalent). The **converse** is $q \to p$ and the **inverse** is $\neg p \to \neg q$ (both *not* equivalent to the original). Proving the converse proves a *different* statement. Confusing "if" with "only if" is one of the most common errors in student proofs. **Example 7.10.** *For integers, if $n^2$ is even then $n$ is even.* *Proof (contraposition).* The contrapositive is: *if $n$ is odd then $n^2$ is odd*, which is Example 7.5. Since the contrapositive is true, so is the original. ∎ **Example 7.11.** *For integers, if $3n + 2$ is odd then $n$ is odd.* *Proof (contraposition).* Contrapositive: *if $n$ is even then $3n+2$ is even.* Assume $n = 2k$. Then $3n + 2 = 6k + 2 = 2(3k+1)$, which is even. The contrapositive holds, hence so does the original. ∎ **Example 7.12.** *For all positive real numbers $n, m$: if $nm > 100$, then $n > 10$ or $m > 10$.* *Proof (contraposition).* The contrapositive is *if $n \le 10$ and $m \le 10$, then $nm \le 100$.* (Here $\neg(n>10 \vee m>10)$ becomes $n\le 10 \wedge m \le 10$ by De Morgan, and $\neg(nm>100)$ becomes $nm \le 100$.) Assume $0 < n \le 10$ and $0 < m \le 10$. Multiplying the inequalities by positive quantities, $$ n \le 10 \ \Rightarrow\ nm \le 10m, \qquad m \le 10 \ \Rightarrow\ 10m \le 100. $$ Chaining, $nm \le 10m \le 100$. Having proved the contrapositive, the original implication holds. ∎ **Remark.** Example 7.12 shows why contraposition helps: the original conclusion is a *disjunction* ("$n>10$ or $m>10$"), awkward to prove directly, whereas its negation is a *conjunction* of two clean inequalities we can just multiply. ## 7.9 Proof by contradiction (reductio ad absurdum) > **Definition (proof by contradiction).** To prove a statement $p$, **assume its negation** $\neg p$ and derive a contradiction — a formula of the form $r \wedge \neg r$, i.e. $\bot$. Since $(\neg p \to \bot)$ forces $p$ to be true, $p$ is established. ![Proof by contradiction: assume the negation, derive an absurdity (⊥)](img/l07_contra.png) The engine is the tautology $\big(\neg p \to (r \wedge \neg r)\big) \to p$. To prove an *implication* $p \to q$ by contradiction, assume $p \wedge \neg q$ and derive $\bot$; the only row where $p \to q$ is false is $p$ true, $q$ false, and that is exactly what we rule out: | $p$ | $q$ | $p \to q$ | |:-:|:-:|:-:| | F | F | T | | F | T | T | | T | F | **F** | | T | T | T | **Example 7.13 (a classic).** *$\sqrt{2}$ is irrational.* *Proof.* Suppose, for contradiction, that $\sqrt{2}$ is **rational**. Then it can be written in lowest terms as $$ \sqrt{2} = \frac{m}{n}, \qquad m, n \in \mathbb{Z},\ \ n \neq 0,\ \ \gcd(m, n) = 1. $$ Squaring, $2 = m^2/n^2$, hence $m^2 = 2n^2$. So $m^2$ is even, and therefore $m$ is even (Example 7.10). Write $m = 2k$. Substituting, $$ (2k)^2 = 2n^2 \ \Rightarrow\ 4k^2 = 2n^2 \ \Rightarrow\ n^2 = 2k^2, $$ so $n^2$ is even and hence $n$ is even. But then $2$ divides both $m$ and $n$, contradicting $\gcd(m, n) = 1$. The assumption is untenable, so $\sqrt{2}$ is irrational. ∎ **Example 7.14 (Euclid's theorem, ca. 300 BCE).** *There are infinitely many primes.* *Proof.* Suppose, for contradiction, that there are only finitely many primes, listed as $p_1, p_2, \dots, p_n$. Consider the number $$ N = p_1 p_2 \cdots p_n + 1. $$ Since $N > 1$, it has at least one prime divisor $p$ (this fact is proved in Example 7.26). That $p$ must be one of $p_1, \dots, p_n$, since those are supposedly *all* the primes. But then $p \mid N$ and $p \mid p_1 p_2 \cdots p_n = N - 1$, so $p \mid \big(N - (N-1)\big) = 1$. No prime divides $1$ — contradiction. Hence there are infinitely many primes. ∎ **Common pitfall.** Euclid's argument does **not** claim $N = p_1\cdots p_n + 1$ is itself prime. It only needs $N$ to have *some* prime factor outside the list. Indeed $N$ can be composite: $2\cdot3\cdot5\cdot7\cdot11\cdot13 + 1 = 30031 = 59 \times 509$. Students often misremember this as "the product of the first $k$ primes plus one is prime," which is false. **Example 7.15.** *There is no smallest positive rational number.* *Proof.* Suppose, for contradiction, that $r$ is the smallest positive rational. Then $r/2$ is also rational (a quotient of rationals) and positive, yet $r/2 < r$. This contradicts the minimality of $r$. Hence no smallest positive rational exists. ∎ **Example 7.16.** *$\log_2 3$ is irrational.* *Proof.* Suppose $\log_2 3$ is rational. Since $\log_2 3 > 0$, write $\log_2 3 = p/q$ with positive integers $p, q$. Then $2^{p/q} = 3$, so raising to the $q$-th power, $2^{p} = 3^{q}$. The left side $2^p$ is even (as $p \ge 1$), while the right side $3^q$ is odd. An even number cannot equal an odd number — contradiction. Hence $\log_2 3$ is irrational. ∎ **Remark (contradiction vs. contraposition).** They are close cousins but not identical. Contraposition proves $p\to q$ by proving $\neg q \to \neg p$ with a *direct* argument and no contradiction. Contradiction is more general (it proves any statement, not just implications) but is often criticized for being less informative: it tells you *that* something is impossible without always revealing *why* constructively. Where a direct or contrapositive proof is available, many mathematicians prefer it. ## 7.10 Proof by cases and exhaustion > **Definition (proof by cases).** Split the hypothesis into finitely many **exhaustive** cases $C_1, \dots, C_k$ (whose disjunction $C_1 \vee \dots \vee C_k$ is always true) and prove the conclusion separately in each. It rests on the tautology > $$ \Big((C_1 \to q) \wedge \dots \wedge (C_k \to q)\Big) \wedge (C_1 \vee \dots \vee C_k) \;\to\; q. $$ > **Definition (proof by exhaustion).** The special case in which the domain is *finite* and small enough that we simply check every element. **Common pitfall.** The cases must be **exhaustive** — their disjunction must cover every possibility. Forgetting a case (e.g. handling $x>0$ and $x<0$ but not $x=0$) leaves a hole in the proof. The cases need not be mutually exclusive, but they must together cover everything. **Example 7.17 (exhaustion).** *$(n+1)^3 \ge 3^n$ for every natural number $n$ with $1 \le n \le 4$.* *Proof.* The domain $\{1,2,3,4\}$ is finite; check each. | $n$ | $(n+1)^3$ | $3^n$ | $(n+1)^3 \ge 3^n$? | |:-:|:-:|:-:|:-:| | 1 | $8$ | $3$ | ✓ | | 2 | $27$ | $9$ | ✓ | | 3 | $64$ | $27$ | ✓ | | 4 | $125$ | $81$ | ✓ | All four hold. ∎ (The inequality *fails* at $n=5$: $6^3 = 216 < 243 = 3^5$ — which is exactly why the hypothesis restricts $n \le 4$.) **Example 7.18.** *For every integer $n$, $n^2 \equiv 0$ or $1 \pmod 4$.* *Proof (two cases on parity).* *Case 1: $n$ even.* Then $n = 2k$, so $n^2 = 4k^2 \equiv 0 \pmod 4$. *Case 2: $n$ odd.* Then $n = 2k+1$, so $n^2 = 4k^2 + 4k + 1 = 4(k^2+k) + 1 \equiv 1 \pmod 4$. Every integer is even or odd, so the cases are exhaustive and $n^2 \equiv 0$ or $1 \pmod 4$ always. ∎ (Corollary: no integer of the form $4m + 2$ or $4m+3$ is a perfect square.) **Example 7.19.** *Every prime $p > 3$ has the form $6k+1$ or $6k+5$ (equivalently $6k \pm 1$).* *Proof.* Any integer is exactly one of $6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5$. We rule out four cases for a prime $p > 3$: - $6k$, $6k+2$, $6k+4$ are all even, hence divisible by $2$; since $p > 3 > 2$, such $p$ would be composite. - $6k+3 = 3(2k+1)$ is divisible by $3$; since $p > 3$, such $p$ would be composite. The only remaining forms are $6k+1$ and $6k+5$, so a prime $p > 3$ must be one of these. ∎ **Example 7.20 (cases via "without loss of generality").** *For all real numbers $x, y$: $|x + y| \le |x| + |y|$ (the triangle inequality).* *Proof.* Recall $|a| \ge a$ and $|a| \ge -a$ for every real $a$; equivalently $-|a| \le a \le |a|$. Adding the inequalities $-|x| \le x \le |x|$ and $-|y| \le y \le |y|$ gives $$ -\big(|x|+|y|\big) \le x + y \le |x| + |y|. $$ A number $t$ satisfying $-c \le t \le c$ (with $c \ge 0$) satisfies $|t| \le c$. Taking $t = x+y$ and $c = |x|+|y|$ yields $|x+y| \le |x| + |y|$. ∎ *(This packages the four sign-cases $x,y \gtrless 0$ into one uniform argument — the phrase "without loss of generality" often signals such a compression.)* ## 7.11 Mathematical induction (weak form) > **Definition (mathematical induction, weak form).** To prove that a statement $P(n)$ holds for **every** integer $n \ge a$, establish two obligations: > - **Base step** — show $P(a)$ is true. > - **Inductive step** — show that for every $k \ge a$, *if* $P(k)$ is true (the **inductive hypothesis, IH**), *then* $P(k+1)$ is true. > > If both hold, then $P(n)$ is true for all $n \ge a$. Intuitively, the base step knocks over the first domino, and the inductive step guarantees each domino knocks over the next; so every domino falls. Formally, induction is one of the **Peano axioms** characterizing the natural numbers — it is not derived from more basic principles but assumed as part of what $\mathbb{N}$ *means*. ![The domino metaphor for induction: the base case tips the first domino and each step tips the next](img/l07_dominoes.png) **Common pitfall (never skip the base step).** Both steps are essential. Consider the false claim $P(n)$: "$n = n+1$." Its inductive step actually *goes through*: if $k = k+1$ then adding $1$ gives $k+1 = k+2$, i.e. $P(k+1)$. Yet $P(n)$ is false for every $n$, because the base step fails. An inductive step with no valid base proves nothing. **Example 7.21 (arithmetic series).** *For every integer $n \ge 1$, $\displaystyle 1 + 2 + \dots + n = \frac{n(n+1)}{2}.$* *Proof.* **Base** ($n=1$): the left side is $1$; the right side is $\tfrac{1\cdot 2}{2} = 1$. Equal, so $P(1)$ holds. **Inductive step:** assume for some $k \ge 1$ that $1 + 2 + \dots + k = \tfrac{k(k+1)}{2}$ (IH). Then $$ 1 + 2 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}, $$ which is $P(k+1)$. By induction the formula holds for all $n \ge 1$. ∎ **Example 7.22 (sum of odd numbers).** *For every integer $n \ge 1$, $\displaystyle 1 + 3 + 5 + \dots + (2n-1) = n^2.$* *Proof.* **Base** ($n=1$): left side $= 1$, right side $= 1^2 = 1$. ✓ **Inductive step:** assume $1 + 3 + \dots + (2k-1) = k^2$ (IH). The $(k+1)$-th odd number is $2(k+1)-1 = 2k+1$, so $$ \underbrace{1 + 3 + \dots + (2k-1)}_{=\,k^2\ \text{by IH}} + (2k+1) = k^2 + 2k + 1 = (k+1)^2, $$ which is $P(k+1)$. By induction the identity holds for all $n \ge 1$. ∎ **Example 7.23 (sum of squares).** *For every integer $n \ge 1$, $\displaystyle 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.$* *Proof.* **Base** ($n=1$): left $=1$, right $= \tfrac{1\cdot 2\cdot 3}{6} = 1$. ✓ **Inductive step:** assume $\sum_{i=1}^{k} i^2 = \tfrac{k(k+1)(2k+1)}{6}$ (IH). Then $$ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6}. $$ Factoring $2k^2 + 7k + 6 = (k+2)(2k+3)$ gives $\tfrac{(k+1)(k+2)(2k+3)}{6}$, which is the formula with $n = k+1$. By induction it holds for all $n \ge 1$. ∎ **Example 7.24 (a divisibility result).** *For every integer $n \ge 1$, $6 \mid (n^3 - n)$.* *Proof.* **Base** ($n=1$): $1^3 - 1 = 0$, and $6 \mid 0$. ✓ **Inductive step:** assume $6 \mid (k^3 - k)$ (IH). Then $$ (k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3k(k+1). $$ The first term is divisible by $6$ by the IH. For the second, $k(k+1)$ is a product of consecutive integers, hence even (lemma of Example 7.9), so $3k(k+1)$ is divisible by $6$. A sum of two multiples of $6$ is a multiple of $6$, so $6 \mid \big((k+1)^3 - (k+1)\big)$. By induction $6 \mid (n^3 - n)$ for all $n \ge 1$. ∎ **Example 7.25 (an inequality, non-unit base).** *For every integer $n \ge 4$, $2^n < n!$.* *Proof.* **Base** ($n = 4$): $2^4 = 16 < 24 = 4!$. ✓ *(Note the base is $n=4$, not $1$: the claim is false for $n \le 3$, since $2^3 = 8 > 6 = 3!$.)* **Inductive step:** assume $2^k < k!$ for some $k \ge 4$ (IH). Then $$ 2^{k+1} = 2\cdot 2^k < 2 \cdot k! < (k+1)\cdot k! = (k+1)!, $$ where the middle inequality uses the IH and the last uses $k + 1 > 2$ (true since $k \ge 4$). Hence $2^{k+1} < (k+1)!$. By induction $2^n < n!$ for all $n \ge 4$. ∎ **Remark (choosing the base).** Induction proves "$P(n)$ for all $n \ge a$" for whatever starting value $a$ makes the base step true. Example 7.25 illustrates that the natural starting point is not always $1$ — you begin where the statement first holds. ## 7.12 Strong induction > **Definition (strong induction / complete induction).** To prove $P(n)$ for all $n \ge a$: > - **Base step** — show $P(a)$ (and possibly a few more initial values) is true. > - **Inductive step** — show that for every $k \ge a$, *if* $P(a), P(a+1), \dots, P(k)$ are **all** true, then $P(k+1)$ is true. > > The difference from weak induction is the strength of the hypothesis: you may assume the statement for *all* smaller values, not just the immediately preceding one. Weak and strong induction are logically equivalent (each can be derived from the other, and both from the **well-ordering principle**: every nonempty set of positive integers has a least element). Strong induction is the natural tool when $P(k+1)$ depends on a value further back than $P(k)$ — for instance, when a number factors into two smaller-but-unpredictable pieces. **Example 7.26 (every integer $\ge 2$ has a prime factor).** *Every integer $n \ge 2$ is divisible by some prime.* *Proof (strong induction).* **Base** ($n = 2$): $2$ is prime and $2 \mid 2$. ✓ **Inductive step:** let $k \ge 2$ and assume every integer $m$ with $2 \le m \le k$ has a prime factor (IH). Consider $k+1$. - If $k+1$ is prime, then $k+1$ is a prime factor of itself. - If $k+1$ is composite, then $k+1 = a b$ with integers $2 \le a, b \le k$. By the IH (applied to $a$), $a$ has a prime factor $p$. Since $p \mid a$ and $a \mid (k+1)$, transitivity of divisibility (Example 7.7) gives $p \mid (k+1)$. Either way $k+1$ has a prime factor. By strong induction every integer $\ge 2$ has one. ∎ *(This is the fact borrowed in Euclid's proof, Example 7.14, and it needs the full smaller-than-$k+1$ hypothesis — hence strong induction.)* **Example 7.27 (existence of prime factorizations).** *Every integer $n \ge 2$ can be written as a product of primes.* *Proof (strong induction).* **Base** ($n=2$): $2$ is prime, a product of one prime. ✓ **Inductive step:** assume every integer $m$ with $2 \le m \le k$ is a product of primes. Consider $k+1$. - If $k+1$ is prime, it is already such a product. - If $k+1 = ab$ with $2 \le a, b \le k$, then by the IH both $a$ and $b$ are products of primes; concatenating those factorizations expresses $k+1$ as a product of primes. By strong induction every integer $\ge 2$ is a product of primes. ∎ *(This is the existence half of the **Fundamental Theorem of Arithmetic**; uniqueness of the factorization requires more work.)* **Example 7.28 (a "postage stamp" / representation result).** *Every integer $n \ge 12$ can be written as $4a + 5b$ for some nonnegative integers $a, b$ (i.e. paid with 4-cent and 5-cent stamps).* *Proof (strong induction with several base cases).* **Base cases** $n = 12, 13, 14, 15$: $$ 12 = 4\cdot 3,\quad 13 = 4\cdot 2 + 5,\quad 14 = 4 + 5\cdot 2,\quad 15 = 5\cdot 3. \ \checkmark $$ **Inductive step:** let $k \ge 15$ and assume every integer $m$ with $12 \le m \le k$ is representable (IH). Consider $k+1$. Since $k + 1 \ge 16$, we have $k+1-4 = k-3 \ge 12$, and also $k - 3 \le k$, so by the IH $k-3 = 4a + 5b$ for some $a, b \ge 0$. Then $k+1 = 4(a+1) + 5b$, a valid representation. By strong induction every $n \ge 12$ is representable. ∎ **Common pitfall (too few base cases).** In Example 7.28 the inductive step reaches back four units ($n \to n-4$), so it needs *four* consecutive base cases $12,13,14,15$ to get started; a single base case would leave $13, 14, 15$ unproved. Strong induction problems frequently require you to verify enough initial values to "feed" the inductive step. **Well-ordering and the "least counterexample".** Strong induction is equivalent to the **well-ordering principle**: *every non-empty set of positive integers has a least element.* This licenses a clean proof shape — to show $P(n)$ for all $n$, suppose the set of counterexamples is non-empty, take its **least** element $m$, and derive a contradiction (typically by producing a *smaller* counterexample, or by invoking $P(k)$ for all $k1$ has a prime factor — otherwise a least counterexample $m$ is composite, $m=ab$ with $1= 0 f := 1 i := 1 while i <= n: f := f * i i := i + 1 return f ``` *Claim.* On termination, `factorial(n)` returns $n!$. *Proof.* Take the **loop invariant** $I$: *"at the top of the while-test, $f = (i-1)!$."* - **Initialization (base).** Before the first test, $i = 1$ and $f = 1 = 0! = (i-1)!$. So $I$ holds. - **Maintenance (inductive step).** Suppose $I$ holds at some loop-top with the test true (so $i \le n$): $f = (i-1)!$. The body sets $f \leftarrow f\cdot i = (i-1)!\cdot i = i!$, then $i \leftarrow i+1$. Now $f = i! = ((i+1)-1)!$ with the new $i$, so $I$ holds again at the next loop-top. - **Termination.** The loop ends when $i > n$; since $i$ increases by $1$ from $1$, it exits with $i = n+1$. By the invariant $f = (i-1)! = n!$, which is returned. ∎ **Remark.** The same three-part schema — *initialization, maintenance, termination* — proves correctness of sorting loops, search loops, and array summations. It is induction wearing engineering clothes, and it is why "what is the loop invariant?" is the first question in verifying any loop. ## 7.14 Existence and uniqueness proofs > **Definition (existence proof).** Establishes a statement "$\exists x\, P(x)$." A **constructive** existence proof exhibits an explicit witness $x$; a **non-constructive** one proves existence without producing a specific $x$. **Example 7.30 (constructive).** *There exists a prime $p$ such that $p+2$ and $p+6$ are also prime.* *Proof.* Take $p = 5$: then $p+2 = 7$ and $p+6 = 11$, all three prime. ∎ **Example 7.31 (non-constructive).** *There exist irrational numbers $x, y$ with $x^y$ rational.* *Proof.* Consider the number $\sqrt{2}^{\,\sqrt{2}}$. - **If** it is rational, take $x = y = \sqrt{2}$ (both irrational) and we are done. - **If** it is irrational, take $x = \sqrt{2}^{\,\sqrt{2}}$ and $y = \sqrt 2$; then $$ x^y = \Big(\sqrt{2}^{\,\sqrt{2}}\Big)^{\sqrt{2}} = \sqrt{2}^{\,\sqrt{2}\cdot\sqrt{2}} = \sqrt{2}^{\,2} = 2 \in \mathbb{Q}. $$ One of the two cases must hold, so a suitable pair exists — **yet the proof never tells us which pair works**. That is the hallmark of a non-constructive proof. ∎ > **Definition (uniqueness proof).** To prove "there is a *unique* $x$ with $P(x)$," establish two things: **existence** (some $x$ has $P$) and **uniqueness** (if $P(x_1)$ and $P(x_2)$ both hold, then $x_1 = x_2$). **Example 7.32 (existence and uniqueness).** *For real numbers $a, b$ with $a \ne 0$, the equation $ax + b = 0$ has exactly one real solution.* *Proof.* **Existence:** $x = -b/a$ is defined (since $a \ne 0$) and satisfies $a(-b/a) + b = -b + b = 0$. **Uniqueness:** suppose $ax_1 + b = 0$ and $ax_2 + b = 0$. Subtracting, $a(x_1 - x_2) = 0$. Since $a \ne 0$, we may divide to get $x_1 - x_2 = 0$, i.e. $x_1 = x_2$. Thus the solution is unique. ∎ ## 7.15 Counterexamples and disproof To **disprove** a universal statement "$\forall x\, P(x)$" you need only exhibit one $x$ where $P$ fails. Such an $x$ is a **counterexample**. By duality with §7.1: a single counterexample refutes a universal claim, exactly as a single witness proves an existential one. > **Definition (counterexample).** A **counterexample** to "$\forall x\, P(x)$" is a specific element $c$ of the domain for which $P(c)$ is false. One counterexample suffices to show the universal statement is false. **Example 7.33.** *Disprove: "every prime is odd."* The prime $2$ is even. So $2$ is a counterexample and the statement is false. ∎ **Example 7.34.** *Disprove: "if $2^n - 1$ is to be prime it suffices that $n$ be prime," i.e. "$n$ prime $\Rightarrow 2^n - 1$ prime."* Take $n = 11$, which is prime. Then $2^{11} - 1 = 2047 = 23 \times 89$ is composite. Counterexample found; the claim is false. ∎ **Example 7.35.** *Disprove: "every positive integer is a sum of two perfect squares."* Take $n = 3$. The squares not exceeding $3$ are $0$ and $1$; the possible sums of two are $0, 1, 2$, never $3$. So $3$ is a counterexample. ∎ **Common pitfall (proof by example is not proof).** A counterexample *disproves* a universal claim, but examples never *prove* one. "$P$ holds for $n = 1, 2, 3$, so $\forall n\,P(n)$" is the fallacy of **hasty generalization** — recall Euler's polynomial and Fermat numbers from §7.1. Confirming instances raises confidence but settles nothing. ## 7.16 Common fallacies > **Definition (fallacy).** A **fallacy** is an argument whose form resembles a valid rule but whose guaranteeing implication is **not** a tautology. It is an *unsound* rule. **Affirming the consequent** — from $A \to B$ and $B$, wrongly concluding $A$. The formula $\big((A\to B)\wedge B\big)\to A$ is *not* a tautology: take $A$ false, $B$ true — then $A\to B$ is true and $B$ is true, yet $A$ is false. *("If it rained, the ground is wet; the ground is wet; therefore it rained" — but a sprinkler could be responsible.)* Contrast with the valid **modus ponens** ($A\to B,\ A \therefore B$). **Denying the antecedent** — from $A \to B$ and $\neg A$, wrongly concluding $\neg B$. The formula $\big((A\to B)\wedge \neg A\big)\to \neg B$ fails on the same row $A$ false, $B$ true: premises true, conclusion $\neg B$ false. *("If it rained, the ground is wet; it did not rain; therefore the ground is not wet" — again the sprinkler.)* Contrast with the valid **modus tollens** ($A\to B,\ \neg B \therefore \neg A$). **Begging the question (circular reasoning)** — assuming, somewhere in the argument, the very thing to be proved. Example: "$f$ is continuous because its graph has no breaks, and it has no breaks because it is continuous." No new information is transmitted; the conclusion is smuggled into the premises. **The "$a=b \Rightarrow 1 = 2$" fallacy (hidden division by zero).** Let $a = b$. Then $$ a^2 = ab \ \Rightarrow\ a^2 - b^2 = ab - b^2 \ \Rightarrow\ (a-b)(a+b) = b(a-b) \ \Rightarrow\ a + b = b \ \Rightarrow\ 2b = b \ \Rightarrow\ 2 = 1. $$ The error is the cancellation of $(a-b)$: since $a = b$, we have $a - b = 0$, and dividing by zero is illegitimate. A single invalid step "proves" an absurdity — a reminder that *every* step must be justified. **The "all horses are the same color" fallacy (a broken inductive step).** *Claim:* in any set of $n$ horses, all have the same color. *"Proof."* Base $n=1$: trivially one horse matches itself. Step: given $k+1$ horses $h_1,\dots,h_{k+1}$, the first $k$ (namely $h_1,\dots,h_k$) are one color by IH, and the last $k$ ($h_2,\dots,h_{k+1}$) are one color by IH; the overlap $h_2,\dots,h_k$ forces all $k+1$ to match. *The flaw:* the overlap argument needs the two $k$-subsets to share a member, which fails at the very first step $k = 1 \to k+1 = 2$: the sets $\{h_1\}$ and $\{h_2\}$ do **not** overlap. The inductive step is invalid for that one crucial value, so the chain never gets going. **The lesson:** a rule is legitimate only when its guaranteeing implication is a genuine tautology, and an induction is valid only when the inductive step holds for *every* $k \ge a$ (base included). When in doubt, test with a truth table or examine the smallest cases explicitly. ## 7.17 A short history The idea that a claim can be *demonstrated*, not merely observed, is one of the great inventions of Greek mathematics. **Thales** and the **Pythagoreans** (6th c. BCE) gave early proofs, and **Euclid**'s *Elements* (ca. 300 BCE) organized geometry and number theory into the first great **axiomatic system**: definitions and postulates at the base, theorems derived by explicit reasoning above. Euclid's proof of the infinitude of primes (Example 7.14) is still taught essentially unchanged. Explicit **mathematical induction** appears in the work of **Francesco Maurolico** (1575) and, more influentially, **Blaise Pascal** (1650s, in his treatise on the arithmetical triangle). Its modern axiomatic form is due to **Giuseppe Peano** (1889), whose axioms make induction a defining property of the natural numbers. The 19th century brought a drive for **rigor**: Cauchy, Weierstrass, and Dedekind put analysis on firm foundations, and **Gottlob Frege** (*Begriffsschrift*, 1879) created modern formal logic. **David Hilbert**'s program (1920s) sought to reduce all mathematics to the manipulation of formal symbols with a finite, checkable set of rules — the syntactic vision of §7.6. In 1931 **Kurt Gödel**'s incompleteness theorems showed the program could not fully succeed: any sufficiently rich consistent system contains true statements it cannot prove. Proof has limits, but within them it remains our only route to certainty. The modern era added **computer-assisted proof**: the **Four Color Theorem** (Appel and Haken, 1976) was proved with essential help from a computer checking thousands of cases, and today **proof assistants** such as Coq, Lean, and Isabelle let mathematicians verify proofs down to the primitive rules — the formal derivations of §7.4, carried out by machine. ## Chapter summary - A **proof** transmits certainty: a finite chain of definitions, prior results, hypotheses, and rule-justified steps. Rigor matters because **patterns lie** (Euler's polynomial, Fermat numbers, Euler's sum-of-powers conjecture). - A conclusion $B$ **follows** from premises $A_1, \dots, A_n$ exactly when $A_1 \wedge \dots \wedge A_n \to B$ is a **tautology** (Justification theorem); this is what makes a rule of inference **sound**, and it licenses every technique in the chapter. - Standard propositional rules: **modus ponens**, **modus tollens**, **hypothetical syllogism**, **disjunctive syllogism**, **addition**, **simplification**, **conjunction**, **resolution** — each backed by a tautology. Quantifier rules: **universal/existential instantiation and generalization**. - A **formal derivation** $\Gamma \vdash B$ is a numbered list of premises and rule-justified steps ending in $B$; syntactic provability $\vdash$ matches semantic entailment $\models$ (soundness + completeness). **Resolution refutation** derives the empty clause $\square$ and powers SAT solvers and Prolog. - Proof techniques for mathematics: - **Direct** — assume $p$, derive $q$. - **Contraposition** — prove $\neg q \to \neg p$ (beware: not the converse!). - **Contradiction** — assume $\neg p$, reach $\bot$ ($\sqrt 2$ irrational; infinitude of primes; $\log_2 3$ irrational). - **Cases / exhaustion** — split into exhaustive cases (must cover everything). - **Existence** (constructive vs. non-constructive) and **uniqueness** (existence + "any two coincide"). - **Counterexample** — one instance disproves a universal claim. - **Mathematical induction** proves $P(n)$ for all $n \ge a$: **weak** uses $P(k) \to P(k+1)$; **strong** uses $P(a)\wedge\dots\wedge P(k) \to P(k+1)$. Never skip the base step; strong induction may need several base cases. Induction underlies **program correctness** and **loop invariants**. - **Fallacies** — *affirming the consequent*, *denying the antecedent*, *circular reasoning*, *hidden division by zero*, and *broken inductive steps* ("all horses") mimic valid reasoning but rest on non-tautologies or gaps. ## Exercises ### Warm-up 1. Classify each statement by the proof method you would most naturally use (direct, contraposition, contradiction, cases, induction, counterexample): (a) "The sum of two odd integers is even." (b) "$\sqrt{3}$ is irrational." (c) "$\sum_{i=1}^n i^3 = \big(\tfrac{n(n+1)}2\big)^2$ for all $n\ge1$." (d) "Not every continuous function is differentiable." 2. Prove directly that the **sum of two odd integers is even**. 3. Prove directly that the **product of two odd integers is odd**. 4. Give the **contrapositive**, **converse**, and **inverse** of: "If $n$ is divisible by $6$, then $n$ is divisible by $3$." Which are true? 5. State the guaranteeing tautology for **disjunctive syllogism** and verify it with a truth table. 6. Fill in the justifications for this derivation of $r$ from $\{\,p,\ p\to q,\ q\to r\,\}$: line 1 $p$; line 2 $p\to q$; line 3 $q\to r$; line 4 $q$; line 5 $r$. 7. Disprove by counterexample: "For every integer $n$, $n^2 - n + 11$ is prime." ### Standard 8. Prove by **contraposition**: for every integer $n$, if $5n + 3$ is even then $n$ is odd. 9. Prove by **contradiction** that $\sqrt{3}$ is irrational. Identify the step that produces the contradiction. 10. Prove by **cases** that for every integer $n$, $n^2 + n$ is even. 11. Prove by **induction**: $\displaystyle \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \ge 1$. 12. Prove by **induction**: $3 \mid (n^3 + 2n)$ for all $n \ge 1$. 13. Prove by **induction** the geometric sum $\displaystyle 1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ for all $n \ge 0$. 14. Give a **formal derivation** of $\neg p$ from the premises $\{\,p \to (q \wedge r),\ \neg r\,\}$, justifying each line. *(Hint: you may use $q \wedge r \to r$.)* 15. Use **resolution refutation** to show that $\{\,p \vee q,\ \neg q \vee r,\ \neg r\,\} \vdash p$. 16. State the **loop invariant** for the following loop and use it to prove the returned value equals $\sum_{i=1}^n a_i$: ``` s := 0; i := 1 while i <= n: s := s + a[i]; i := i + 1 return s ``` ### Challenge 17. Prove that $\sqrt{2} + \sqrt{3}$ is **irrational**. *(Hint: square it and reduce to the irrationality of $\sqrt 6$.)* 18. Prove by **strong induction** that every integer $n \ge 12$ can be written as $4a + 5b$ with $a, b \ge 0$. How many base cases do you need, and why? 19. Prove: for every integer $n \ge 1$ there exist $n$ **consecutive composite** integers. *(Hint: consider $(n+1)! + 2, (n+1)! + 3, \dots, (n+1)! + (n+1)$.)* 20. Find and explain the flaw in the "all horses are the same color" induction (§7.16). At exactly which value of $k$ does the inductive step break, and why? 21. Prove that $\log_2 3$ is irrational, then adapt the argument to show $\log_2 5$ is irrational. ## Selected answers & hints - **2.** Let $a = 2s+1$, $b = 2t+1$. Then $a + b = 2s + 2t + 2 = 2(s+t+1)$, even. ∎ - **4.** Contrapositive: "If $n$ is not divisible by $3$, then $n$ is not divisible by $6$" (**true**). Converse: "If $n$ is divisible by $3$, then $n$ is divisible by $6$" (**false**; $n=3$). Inverse: "If $n$ is not divisible by $6$, then $n$ is not divisible by $3$" (**false**; $n=3$). The original and its contrapositive are true; converse and inverse are false — and are equivalent to each other, not to the original. - **7.** $n = 11$ gives $11^2 - 11 + 11 = 121 = 11^2$, composite. (Also $n=10$: $101$ is prime, so small values mislead — the point of §7.15.) - **8.** Contrapositive: if $n$ is even then $5n+3$ is odd. Let $n = 2k$: $5n + 3 = 10k + 3 = 2(5k+1) + 1$, odd. ∎ - **9.** Assume $\sqrt 3 = m/n$ in lowest terms. Then $3n^2 = m^2$, so $3 \mid m^2$, hence $3 \mid m$ (as $3$ is prime). Write $m = 3a$: $3n^2 = 9a^2 \Rightarrow n^2 = 3a^2$, so $3 \mid n$. Then $3$ divides both $m$ and $n$ — **contradiction** with $\gcd(m,n)=1$. - **10.** Case $n$ even: $n^2 + n = n(n+1)$ with $n$ even, so even. Case $n$ odd: then $n+1$ even, so $n(n+1)$ even. Exhaustive. ∎ - **12.** Base $n=1$: $1 + 2 = 3$, divisible by $3$. Step: $(k+1)^3 + 2(k+1) = (k^3 + 2k) + 3k^2 + 3k + 3 = (k^3+2k) + 3(k^2 + k + 1)$; first term divisible by $3$ by IH, second obviously. ∎ - **15.** Clauses $\{p\vee q,\ \neg q \vee r,\ \neg r,\ \neg p\}$ (last is negated goal). Resolve $\neg r$ with $\neg q \vee r \Rightarrow \neg q$; resolve $\neg q$ with $p \vee q \Rightarrow p$; resolve $p$ with $\neg p \Rightarrow \square$. Contradiction, so $p$ follows. ∎ - **16.** Invariant: at the top of the test, $s = \sum_{i'=1}^{i-1} a_{i'}$. Initialization: $i=1$, $s = 0 =$ empty sum. Maintenance: if $s = \sum_{i'=1}^{i-1}a_{i'}$ then after $s \mathrel{+}= a_i$ and $i \mathrel{+}= 1$, again $s = \sum_{i'=1}^{i-1}a_{i'}$. Termination: $i = n+1$, so $s = \sum_{i'=1}^{n} a_{i'}$. ∎ - **17.** Let $s = \sqrt2 + \sqrt3$. If $s$ were rational, so would $s^2 = 5 + 2\sqrt6$ be, forcing $\sqrt6 = (s^2-5)/2$ rational. But $\sqrt6$ is irrational (if $\sqrt6 = p/q$ lowest terms, $6q^2 = p^2 \Rightarrow p$ even $\Rightarrow p=2a \Rightarrow 2a^2 = 3q^2 \Rightarrow q$ even, contradicting lowest terms). Contradiction, so $s$ is irrational. ∎ - **18.** Base cases $12,13,14,15$ (four of them, because the inductive step goes from $n$ to $n-4$, so it needs four consecutive established values to reach every larger $n$). Step: for $k+1 \ge 16$, $k-3 \ge 12$ is representable by IH; add one $4$-stamp. - **19.** The $n$ numbers $(n+1)! + j$ for $j = 2, 3, \dots, n+1$ are consecutive; each is divisible by $j$ (since $j \mid (n+1)!$ and $j \mid j$) and exceeds $j$, hence composite. ∎ - **20.** The inductive step relies on the two overlapping $k$-element subsets sharing a horse. For $k = 1$ (proving $P(2)$ from $P(1)$) the subsets $\{h_1\}$ and $\{h_2\}$ are disjoint, so no color is forced to match. The step fails precisely at $k=1$, breaking the chain immediately after the base. - **21.** If $\log_2 3 = p/q$ ($p,q \ge 1$) then $2^p = 3^q$: even $=$ odd, contradiction. Identically, $\log_2 5 = p/q$ gives $2^p = 5^q$, even $=$ odd — impossible. ## Further reading - K. H. Rosen, *Discrete Mathematics and Its Applications* — Chapter 1 (Rules of Inference, Introduction to Proofs, Proof Methods and Strategy) and Chapter 5 (Induction and Recursion). - S. S. Epp, *Discrete Mathematics with Applications* — Chapters 4–5 (Elementary Number Theory and Methods of Proof; Sequences, Mathematical Induction, and Recursion). - D. J. Velleman, *How to Prove It: A Structured Approach* — a book-length treatment of the craft of proof, with strong coverage of quantifier reasoning and proof strategy.