Contents / Discrete Mathematics / Logic and Proofs

Chapter 1

Logic and Proofs

Propositions and the five connectives; functional completeness of NAND alone; equivalences, contrapositive and vacuous truth; quantifiers and their negation; rules of inference and the classic fallacies; direct proof, contraposition and contradiction with the irrationality of the square root of 2; and induction, strong induction and well-ordering shown to be equivalent.

Introduction

A program either returns the right answer on every input or it does not. Testing it on a thousand inputs establishes something about those thousand inputs and nothing whatever about the thousand-and-first. The only instrument that settles the general case is a proof, and a proof is an object with a grammar: it is built out of statements, combined by a small fixed set of connectives, quantified over domains, and chained together by rules that preserve truth. This chapter is about that grammar.

Two things make the subject unexpectedly concrete for a computer scientist. The first is that the connectives of propositional logic are exactly the gates of a circuit, and the question which gates do I need? has a sharp answer: a single gate type, NAND, suffices to build every boolean function there is. That is a theorem about logic and simultaneously a fact about silicon. The second is that a truth table is a finite object, so every question about a formula in $n$ variables — is it a tautology, is it satisfiable, are these two formulas the same? — can be decided by checking $2^{n}$ rows. Finite does not mean cheap: $2^{n}$ rows for $n = 60$ is more rows than there have been seconds since the Big Bang, and the question of whether satisfiability can be decided substantially faster is the P versus NP problem. But it does mean the semantics of this chapter never requires an act of faith.

The second half turns to proof itself. We isolate the three moves that do almost all the work — direct argument, contraposition, contradiction — and, crucially, prove that they are valid, rather than asserting them. Proof by contradiction is not a convention we agree to; it is a consequence of the truth table for implication. Then comes induction, the one technique genuinely peculiar to the discrete world, in its ordinary and strong forms, together with the well-ordering principle, which turns out to be the same statement wearing a different hat. We finish by dissecting a famous induction that proves all horses are the same colour, because knowing precisely which step of that argument fails is worth more than any number of correct inductions.

Throughout, $Z$ is the integers and $N = {1, 2, 3, \dots}$ . We work informally, in the sense that our object of study is mathematical reasoning as practised rather than a formal deductive calculus with its own axioms and derivation rules. That formal turn — where "provable" becomes a syntactic notion, and one asks whether it coincides with "true" — belongs to Mathematical Logic, and we will point at the door without walking through it.

1.1Propositions and truth values

Everything begins with a restriction on what counts as a sentence we may reason about.

Definition 1.1 (Proposition). A proposition is a declarative sentence that is either true or false, and not both. Its truth value is $T$ (true) or $F$ (false). We write propositional variables $p, q, r, \dots$ for propositions whose particular content does not matter.

The definition excludes three large families of English sentences. Questions ("Is $7$ prime?") assert nothing. Commands ("Return $- 1$ on failure") assert nothing. Open sentences (" $x > 3$ ") assert something only once $x$ is supplied; until then they are predicates, which we take up in the section on quantifiers. And a fourth family is excluded for a subtler reason: sentences like "this sentence is false" are declarative and yet cannot consistently be assigned either value. We simply do not admit them. Ruling out self-reference by fiat is a blunt instrument, and the delicate version of the question — what happens to a formal system rich enough to talk about its own provability — is the subject of Gödel's incompleteness theorems in Mathematical Logic.

Example 1.2 (Which sentences are propositions?). Classify each as a proposition (with its truth value) or not: (a) $17$ is prime. (b) Every even integer greater than $2$ is a sum of two primes. (c) Sort the array. (d) $n^{2} \geq n$ . (e) $3 + 4 = 8$ .

Solution.

(a) is a proposition, true.
(b) is a proposition — Goldbach's conjecture. It is either true or false; nobody currently knows which. Being a proposition is about having a truth value, not about our access to it.
(c) is imperative, so not a proposition.
(d) is an open sentence: its truth depends on $n$ . It becomes a proposition once $n$ is fixed, or once it is quantified ("for all integers $n$ , $n^{2} \geq n$ " — false, take $n = 0$ ... in fact true for integers, but false for reals, take $n = 1/2$ ).
(e) is a proposition, false. Falsity is no obstacle: a proposition need not be true.

□

Notation. We reserve $T$ and $F$ for truth values and use $1$ and $0$ for them only where the arithmetic is the point, as when counting satisfying assignments. In code the same two values appear as true/false, and the correspondence between a boolean expression in a program and a compound proposition is exact — which is why the laws of this chapter are the laws a compiler uses to simplify a conditional.

A compound proposition built from $n$ variables is completely described by what it does to each assignment of truth values to those variables. This is the fundamental finiteness that makes propositional logic decidable.

Definition 1.3 (Truth assignment and truth table). A truth assignment for the variables $p_{1}, \dots, p_{n}$ is a function giving each $p_{i}$ a value in ${T, F}$ . The truth table of a compound proposition lists its value under every truth assignment, one assignment per row.

Theorem 1.4 (Size of a truth table). A compound proposition in $n$ distinct variables has exactly $2^{n}$ truth assignments, so its truth table has $2^{n}$ rows.

Proof. A truth assignment chooses one of two values independently for each of the $n$ variables. The choices are unconstrained and independent, so by the multiplication principle the number of assignments is $2 \cdot 2 \dots 2$ with $n$ factors, which is $2^{n}$ .∎

Intuition. Reading a row of a truth table as an $n$ -bit binary string makes the count obvious: the rows of a table for $p, q, r$ are exactly the eight strings $000$ through $111$ , and listing them in that order is why the standard layout alternates the last column fastest. A truth table is a complete enumeration of a finite universe of possibilities, which is precisely why it decides every propositional question — and precisely why it is useless for $n$ in the hundreds.

Two propositions with the same truth table are indistinguishable by any argument that treats their variables as arbitrary. This suggests counting not formulas but tables, and the count is startling.

Theorem 1.5 (Number of boolean functions). There are exactly $2^{2^{n}}$ distinct functions from ${T, F}^{n}$ to ${T, F}$ .

Proof. Such a function is determined by its output on each of the $2^{n}$ inputs, by the theorem Size of a truth table, and conversely any choice of outputs determines a function. Choosing an output is choosing one of two values, and the $2^{n}$ choices are independent, so the number of functions is $2$ raised to the number of inputs, namely $2^{2^{n}}$ .∎

Figure 1.6. The number of

n

-variable boolean functions, drawn as the number of decimal digits of

2^{2^{n}}

— that is, bar height

= 2^{n} lo g_{10} 2

. Plotting the count itself is impossible: at

n = 5

it is a

10

-digit number, at

n = 6

20

-digit one, and each step doubles the height of the bar. Only

2^{2^{0}} = 2

and

2^{2^{1}} = 4

of these are small enough to name comfortably.

Example 1.7 (Counting three-variable tables). How many distinct compound propositions in the variables $p, q, r$ are there, up to having the same truth table? How many of those are tautologies, and how many are satisfiable?

Solution.

By the theorem Number of boolean functions with $n = 3$ there are $2^{2^{3}} = 2^{8} = 256$ distinct truth tables.
A tautology is true in every row, which pins down all eight outputs, so there is exactly $1$ .
A proposition fails to be satisfiable only when every output is $F$ , again exactly one table, so $256 - 1 = 255$ are satisfiable.
Note the moral: almost everything is satisfiable, and being a tautology is extraordinarily special. This is why checking satisfiability is the interesting computational problem.

□

Pitfall. "The same proposition" is ambiguous and the ambiguity matters. As strings, $p \land q$ and $q \land p$ are different; as functions, they are the same. Every theorem in this chapter is about the functions. Two formulas with identical truth tables are interchangeable inside any larger formula, which is exactly the licence a compiler needs to rewrite a && b as b && a, and exactly the licence it does not have when evaluating a has a side effect.

Exercises for §1.1 →

1.2Connectives, conditionals and functional completeness

Five connectives generate everything we will write.

Definition 1.8 (The five connectives). For propositions $p$ and $q$ :

Negation $\neg p$ ("not $p$ ") is true exactly when $p$ is false.
Conjunction $p \land q$ (" $p$ and $q$ ") is true exactly when both are true.
Disjunction $p \lor q$ (" $p$ or $q$ ") is true exactly when at least one is true. This is the inclusive or.
Conditional $p \to q$ ("if $p$ then $q$ ") is false exactly when $p$ is true and $q$ is false, and true otherwise.
Biconditional $p \leftrightarrow q$ (" $p$ if and only if $q$ ") is true exactly when $p$ and $q$ have the same truth value.

In $p \to q$ we call $p$ the antecedent and $q$ the consequent.

The first three match ordinary usage closely enough to cause no trouble, with one exception: English "or" is often exclusive ("soup or salad"), and mathematical $\lor$ never is. The exclusive version is a separate connective, $p \oplus q$ , true when exactly one of $p, q$ holds; it is the parity bit, the XOR gate, and the operation that makes a one-time pad work.

The conditional is where every student stumbles, because three of its four rows are true and two of those three feel like cheating.

Figure 1.9. The truth table of

p \to q

drawn as a grid, with the single false row isolated. The conditional asserts nothing except that the case "

p

true,

q

false" does not occur; the two rows where

p

is false are true *vacuously*, since there is nothing for the promise to break.

Definition 1.10 (Vacuous truth). A conditional $p \to q$ whose antecedent $p$ is false is said to be vacuously true. Its truth value is $T$ regardless of $q$ .

This convention is not arbitrary, and it is not chosen for convenience. It is forced, in the following precise sense.

Theorem 1.11 (The conditional's truth table is forced). Suppose a binary connective $\Rightarrow$ satisfies both of the following:

From $p$ and $p \Rightarrow q$ one may always infer $q$ (the rule is sound).
For every predicate $P$ over a domain $D$ , the sentence "for all $x \in D$ , $P (x) \Rightarrow P (x)$ " is true.

Then $\Rightarrow$ agrees with $\to$ on all four rows.

Proof. Row $TF$ is settled by condition 1: if $p$ is true and $q$ is false, then $p \Rightarrow q$ must be false, since otherwise both premises of the rule would be true and we could infer the false $q$ .

Row $TT$ is settled by condition 2. Take any predicate $P$ and any $a \in D$ with $P (a)$ true. Condition 2 makes $P (a) \Rightarrow P (a)$ true, and that is an instance of the connective applied to a true antecedent and a true consequent.

Now the two rows with false antecedent. Take $D = Z$ and $P (x)$ the predicate " $x > 5$ ". Condition 2 makes " $x > 5 \Rightarrow x > 5$ " true for every integer $x$ , in particular for $x = 0$ , where both sides are false; so row $FF$ is true. For row $FT$ , take $Q (x)$ to be " $x > 5$ " and $R (x)$ to be " $x > 1$ ". The sentence "for all integers $x$ , $Q (x) \Rightarrow R (x)$ " is one we certainly wish to call true, and at $x = 3$ its antecedent is false while its consequent is true. So that row is true as well.∎

Intuition. Read $p \to q$ as a promise: "if you give me $p$ , I will give you $q$ . " You have broken the promise only if $p$ arrived and $q$ did not. If $p$ never arrived, the promise stands unbroken — not because you kept it in any interesting sense, but because there is no evidence against it. "Every element of the empty list is negative" is true for the same reason, and any convention that made it false would force us to say the empty list contains a non-negative element.

Example 1.12 (Vacuous truth in a loop invariant). A function scans a list and returns true if every element is even. On the empty list it returns true. Justify this using the conditional's truth table.

Solution.

The claim is "for every index $i$ in the list, the element at $i$ is even", which unpacks to " $i$ is a valid index $\to$ element at $i$ is even" for every $i$ .
On the empty list no $i$ is a valid index, so every antecedent is false.
Each conditional is therefore vacuously true, and the universally quantified claim holds. Returning true is correct, and a loop for i in list: if odd: return false followed by return true implements exactly this.
The alternative convention would make the function's answer on the empty list depend on nothing at all in the list, which is the definition of an arbitrary choice.

□

Definition 1.13 (Tautology, contradiction, satisfiable). A compound proposition is a tautology if it is true under every truth assignment, a contradiction if it is false under every truth assignment, and satisfiable if it is true under at least one. A contingency is a proposition that is neither a tautology nor a contradiction.

Example 1.14 (Classifying by truth table). Classify $(p \to q) \lor (q \to p)$ and $(p \lor q) \land \neg p \land \neg q$ , and count the satisfying assignments of $(p \to q) \land (q \to r)$ .

Solution.

For the first, suppose it were false under some assignment. Then $p \to q$ and $q \to p$ are both false, so $p$ is true and $q$ is false from the first, and $q$ is true from the second — a contradiction. Hence it is a tautology.
For the second, if $\neg p$ and $\neg q$ both hold then $p \lor q$ is false, so the conjunction is false; it is a contradiction.
For the third, of the eight assignments to $(p, q, r)$ the formula fails exactly when $p$ is true and $q$ false, or $q$ true and $r$ false. Listing: $TTT$ ✓, $TTF$ ✗, $TFT$ ✗, $TFF$ ✗, $FTT$ ✓, $FTF$ ✗, $FFT$ ✓, $FFF$ ✓. So $4$ assignments satisfy it.

□

Now to the structural question. We introduced five connectives, but nothing so far says we needed five. The next theorem shows that any truth table whatsoever can be realised, which will make the reduction to fewer connectives straightforward.

Definition 1.15 (Literal and disjunctive normal form). A literal is a variable or its negation. A compound proposition is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals, such as $(p \land \neg q) \lor (\neg p \land q \land r)$ .

Theorem 1.16 (Every truth table has a DNF). Let $f$ be any function from ${T, F}^{n}$ to ${T, F}$ with $n \geq 1$ . Then some compound proposition in disjunctive normal form, using only $\neg$ , $\land$ and $\lor$ , has truth table $f$ .

Proof. If $f$ is false on every input, take the proposition $p_{1} \land \neg p_{1}$ , which is a conjunction of literals and so a DNF with one disjunct.

Otherwise, let $a^{(1)}, \dots, a^{(m)}$ be the assignments on which $f$ is true. For each such assignment $a$ define the conjunction

C_{a} = ℓ_{1} \land ℓ_{2} \land \dots \land ℓ_{n}, ℓ_{i} = {p_{i} \neg p_{i} if a (p_{i}) = T, if a (p_{i}) = F .

By construction

C_{a}

is true under the assignment

a

and false under every other assignment, since any other assignment differs from

a

at some

p_{i}

and so makes

ℓ_{i}

false.

Put $φ = C_{a^{(1)}} \lor \dots \lor C_{a^{(m)}}$ . Under an assignment $b$ : if $b = a^{(j)}$ for some $j$ then $C_{a^{(j)}}$ is true so $φ$ is true; if $b$ is none of them then every disjunct is false so $φ$ is false. Thus $φ$ has truth table $f$ , and it uses only $\neg$ , $\land$ , $\lor$ .∎

Definition 1.17 (Functional completeness). A set $S$ of connectives is functionally complete if every boolean function of every arity $n \geq 1$ is the truth table of some proposition built using only connectives from $S$ .

Theorem 1.18 (Completeness of NOT and AND). The set ${\neg, \land}$ is functionally complete. So are ${\neg, \lor}$ and ${\neg, \to}$ .

Proof. By the theorem Every truth table has a DNF, it is enough to express $\lor$ using $\neg$ and $\land$ . Compare truth tables of $p \lor q$ and $\neg (\neg p \land \neg q)$ : the latter is false exactly when $\neg p \land \neg q$ is true, that is exactly when $p$ and $q$ are both false, which is exactly when $p \lor q$ is false. They agree on all four rows. Replacing every $\lor$ in a DNF by this expression gives a formula over ${\neg, \land}$ with the same table, so ${\neg, \land}$ is complete.

For ${\neg, \lor}$ , dually $p \land q$ and $\neg (\neg p \lor \neg q)$ agree on all four rows, and we rewrite every $\land$ . For ${\neg, \to}$ , note $p \lor q$ and $\neg p \to q$ agree: both are false exactly when $p$ is false and $q$ is false. So ${\neg, \to}$ expresses $\lor$ , hence expresses everything ${\neg, \lor}$ does.

Finally the remaining two connectives are definable in any of these sets, since $p \to q$ has the table of $\neg p \lor q$ and $p \leftrightarrow q$ has the table of $(p \to q) \land (q \to p)$ .∎

A natural next question is how small a complete set can be. One connective is enough, and the one that works is the gate a chip fabricator would rather build than any other.

Definition 1.19 (NAND and NOR). The Sheffer stroke or NAND is $p ∣ q$ , defined to be false exactly when $p$ and $q$ are both true; equivalently $p ∣ q$ has the truth table of $\neg (p \land q)$ . The Peirce arrow or NOR is $p ↓ q$ , with the table of $\neg (p \lor q)$ .

Theorem 1.20 (NAND alone is functionally complete). The single connective ${∣}$ is functionally complete.

Proof. By the theorem Completeness of NOT and AND it suffices to express $\neg$ and $\land$ using only $∣$ .

For negation, consider $p ∣ p$ . It is false exactly when $p$ and $p$ are both true, that is exactly when $p$ is true; so $p ∣ p$ has the truth table of $\neg p$ .

For conjunction, $p ∣ q$ has the table of $\neg (p \land q)$ , so applying the negation just constructed gives

(p ∣ q) ∣ (p ∣ q),

whose table is

\neg\neg (p \land q)

, that is

p \land q

Every boolean function therefore has a DNF over ${\neg, \land, \lor}$ , which rewrites over ${\neg, \land}$ , which rewrites over ${∣}$ .∎

Remark. The same argument with $↓$ in place of $∣$ shows NOR is complete too: $p ↓ p$ is $\neg p$ and $(p ↓ q) ↓ (p ↓ q)$ is $p \lor q$ . These are the only two binary connectives that are complete on their own, which can be checked by eliminating the other fourteen. The practical consequence is that a chip needs one gate type: a NAND is two transistors in series and two in parallel, and everything from an adder to a flip-flop is built from copies of it.

Example 1.21 (Building XOR from NAND). Express $p \oplus q$ (exclusive or) using only the Sheffer stroke, and check the count of strokes.

Solution.

$p \oplus q$ is true exactly on $TF$ and $FT$ , so a DNF is $(p \land \neg q) \lor (\neg p \land q)$ .
Write $a = p ∣ q$ . Then $p ∣ a$ has the table of $\neg (p \land \neg (p \land q))$ , and one checks directly that
$p \oplus q = (p ∣ (p ∣ q)) ∣ (q ∣ (p ∣ q)) .$
Verify on the four rows: at $TT$ , $p ∣ q = F$ , so $p ∣ F = T$ and $q ∣ F = T$ , and $T ∣ T = F$ ✓. At $TF$ , $p ∣ q = T$ , so $p ∣ T = F$ and $q ∣ T = T$ , and $F ∣ T = T$ ✓. The remaining rows are symmetric.
The expression uses $4$ stroke symbols, and no expression with $3$ works — this is the standard four-NAND XOR of digital design.

□

Proposition 1.22 (A complete set must contain a connective that is false somewhere). The set ${\land, \lor}$ is not functionally complete.

Proof. Every proposition built from $\land$ and $\lor$ alone is true under the all-true assignment: this holds for a single variable, and if $φ$ and $ψ$ are true under that assignment then so are $φ \land ψ$ and $φ \lor ψ$ , so the claim propagates up the structure of the formula. But $\neg p$ is false under the all-true assignment. Hence $\neg p$ is not expressible, and the set is incomplete.∎

Exercises for §1.2 →

1.3Logical equivalence and the laws of algebra for propositions

Definition 1.23 (Logical equivalence). Propositions $φ$ and $ψ$ are logically equivalent, written $φ \equiv ψ$ , if they have the same truth value under every truth assignment — equivalently, if $φ \leftrightarrow ψ$ is a tautology.

Notation. The symbols $\leftrightarrow$ and $\equiv$ do different jobs. $φ \leftrightarrow ψ$ is itself a proposition, with a truth table, which may be true in some rows and false in others. $φ \equiv ψ$ is a claim about those two propositions, made in our own language rather than in the object language, and it is either right or wrong. The same distinction separates $=$ from "is identically equal to" in algebra.

Equivalence is what licenses rewriting. If $φ \equiv ψ$ then either may be substituted for the other inside any larger formula without changing its table, because the table of the larger formula depends on its parts only through their tables. The standard rewrites, together, make the propositions into an algebra:

\neg\neg p \equiv p, p \land p \equiv p, p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) .

We prove the two families that are used constantly and are most often got wrong.

Theorem 1.24 (De Morgan's laws). For all propositions $p$ and $q$ ,

\neg (p \land q) \equiv \neg p \lor \neg q, \neg (p \lor q) \equiv \neg p \land \neg q .

Proof. Take the first. The left side is true exactly when $p \land q$ is false, that is exactly when it is not the case that both $p$ and $q$ are true, that is exactly when at least one of $p$ , $q$ is false. The right side is true exactly when at least one of $\neg p$ , $\neg q$ is true, that is exactly when at least one of $p$ , $q$ is false. The two conditions are the same, so the tables agree in all four rows.

For the second, apply the first to $\neg p$ and $\neg q$ : $\neg (\neg p \land \neg q) \equiv \neg\neg p \lor \neg\neg q \equiv p \lor q$ . Negating both sides and using $\neg\neg φ \equiv φ$ gives $\neg p \land \neg q \equiv \neg (p \lor q)$ .∎

Intuition. Negation turns the connective inside out. "It is not the case that the file exists and is readable" does not mean the file fails both tests; it means at least one test failed, and you do not know which. Pushing a negation through a compound condition and forgetting to flip $\land$ to $\lor$ is the single most common bug in a hand-simplified if statement.

Example 1.25 (Negating a guard condition). A program takes a branch when 0 <= i && i < n && a[i] != 0. Write the condition for taking the other branch, with negation applied to the individual comparisons only.

Solution.

Write $p$ for $0 \leq i$ , $q$ for $i < n$ , $r$ for $a [i] \neq = 0$ . The guard is $p \land q \land r$ .
By De Morgan's laws, applied twice, $\neg (p \land q \land r) \equiv \neg p \lor \neg q \lor \neg r$ .
Translating back: $i < 0$ or $i \geq n$ or $a [i] = 0$ .
Note the "or": a single failing test is enough. Writing the negation as $i < 0$ and $i \geq n$ and $a [i] = 0$ would describe a condition that never holds.

□

Next, the three relatives of a conditional. Distinguishing them is the highest-yield piece of vocabulary in the chapter.

Definition 1.26 (Converse, contrapositive, inverse). Given the conditional $p \to q$ , its converse is $q \to p$ , its contrapositive is $\neg q \to \neg p$ , and its inverse is $\neg p \to \neg q$ .

Theorem 1.27 (A conditional is equivalent to its contrapositive). For all propositions $p, q$ ,

p \to q \equiv \neg q \to \neg p .

Proof. Both sides are false in exactly one circumstance. The left side is false precisely when $p$ is true and $q$ is false. The right side is false precisely when its antecedent $\neg q$ is true and its consequent $\neg p$ is false, that is when $q$ is false and $p$ is true. These are the same circumstance, and a proposition that takes the value $F$ on exactly the same assignments takes $T$ on exactly the same assignments. Hence the tables agree in all four rows.

Alternatively, chain equivalences: $p \to q \equiv \neg p \lor q \equiv q \lor \neg p \equiv \neg\neg q \lor \neg p \equiv \neg q \to \neg p$ .∎

Theorem 1.28 (A conditional is not equivalent to its converse). There exist propositions $p, q$ with $p \to q$ true and $q \to p$ false. Hence $p \to q \neq \equiv q \to p$ . The same holds for the inverse.

Proof. Take the assignment $p$ false, $q$ true. Then $p \to q$ is true, since its antecedent is false, while $q \to p$ has a true antecedent and a false consequent and so is false. One disagreeing row is enough to refute an equivalence.

For the inverse, $\neg p \to \neg q$ is the contrapositive of $q \to p$ , so by the theorem A conditional is equivalent to its contrapositive it is equivalent to the converse, and therefore fails to be equivalent to $p \to q$ on the same row.∎

Example 1.29 (A concrete converse that fails). Let $n$ range over the integers, $p$ be " $n$ is divisible by $4$ " and $q$ be " $n$ is even". Evaluate the conditional, its converse, its contrapositive and its inverse.

Solution.

$p \to q$ : if $4 ∣ n$ then $n = 4 k = 2 (2 k)$ is even. True for every $n$ .
The converse $q \to p$ : if $n$ is even then $4 ∣ n$ . False, and $n = 6$ is a witness — $6$ is even and $4 ∤ 6$ . This is exactly the assignment $p$ false, $q$ true used in the theorem A conditional is not equivalent to its converse.
The contrapositive $\neg q \to \neg p$ : if $n$ is odd then $4 ∤ n$ . True for every $n$ , as it must be.
The inverse $\neg p \to \neg q$ : if $4 ∤ n$ then $n$ is odd. False, again at $n = 6$ .
The pattern to carry away: conditional and contrapositive stand or fall together; converse and inverse stand or fall together; the two pairs are independent.

□

Pitfall. " $p$ only if $q$ " means $p \to q$ , not $q \to p$ . " $p$ if $q$ " means $q \to p$ . English word order is not a reliable guide to which is the antecedent, so translate through the truth conditions: ask which situation the sentence forbids. "You may board only if you have a ticket" forbids boarding without a ticket, so it is board $\to$ ticket.

Proposition 1.30 (Negating a conditional). For all propositions $p, q$ ,

\neg (p \to q) \equiv p \land \neg q .

Proof. $p \to q$ is false in exactly one row, the one where $p$ is true and $q$ is false; so $\neg (p \to q)$ is true in exactly that row. And $p \land \neg q$ is true in exactly that row as well. The tables agree.∎

Notice what this says: the negation of a conditional is not a conditional. The denial of "if it compiles then it runs" is not "if it compiles then it does not run"; it is "it compiles and it does not run" — a single counterexample. That asymmetry is why refuting an implication is usually far easier than proving one.

Example 1.31 (Simplifying with the laws). Simplify $\neg (p \to (q \land \neg r))$ to a conjunction of literals and a disjunction.

Solution.

By Negating a conditional, the expression is $p \land \neg (q \land \neg r)$ .
By De Morgan's laws, $\neg (q \land \neg r) \equiv \neg q \lor \neg\neg r \equiv \neg q \lor r$ .
So the whole thing is $p \land (\neg q \lor r)$ .
Sanity check on a row: at $p = T$ , $q = T$ , $r = F$ the original is $\neg (T \to T) = F$ , and the simplified form is $T \land (F \lor F) = F$ ✓.

□

Exercises for §1.3 →

1.4Predicates and quantifiers

Propositional logic cannot express "every integer has a successor", because the sentence is about all integers at once and propositional variables are atoms with no internal structure. We need variables ranging over a domain, and two operators that bind them.

Definition 1.32 (Predicate). A predicate $P$ over a domain $D$ assigns to each $x \in D$ a proposition $P (x)$ . The predicate itself has no truth value; $P (a)$ does, for each $a \in D$ .

Definition 1.33 (Quantifiers). Let $P$ be a predicate over a nonempty domain $D$ .

The universal statement $\forall x P (x)$ is true if $P (a)$ is true for every $a \in D$ .
The existential statement $\exists x P (x)$ is true if $P (a)$ is true for at least one $a \in D$ .

A value $a$ with $P (a)$ false is a counterexample to $\forall x P (x)$ ; a value $a$ with $P (a)$ true is a witness for $\exists x P (x)$ .

Pitfall. The domain is part of the statement, never an afterthought. " $\forall x (x^{2} \geq x)$ " is true over $Z$ and false over $R$ , where $x = 1/2$ is a counterexample. Writing a quantified sentence without saying what $x$ ranges over is writing half a sentence.

Over a finite domain $D = {a_{1}, \dots, a_{n}}$ the quantifiers are abbreviations: $\forall x P (x)$ is $P (a_{1}) \land \dots \land P (a_{n})$ and $\exists x P (x)$ is $P (a_{1}) \lor \dots \lor P (a_{n})$ . That is the right mental model, and it immediately predicts how negation behaves.

Theorem 1.34 (De Morgan's laws for quantifiers). For any predicate $P$ over any domain $D$ ,

\neg\forall x P (x) \equiv \exists x \neg P (x), \neg\exists x P (x) \equiv \forall x \neg P (x) .

Proof. Take the first. Suppose $\neg\forall x P (x)$ is true. Then $\forall x P (x)$ is false, so by the definition of $\forall$ it is not the case that $P (a)$ holds for every $a \in D$ ; hence some $a \in D$ has $P (a)$ false, that is $\neg P (a)$ true, and this $a$ witnesses $\exists x \neg P (x)$ .

Conversely, suppose $\exists x \neg P (x)$ is true, with witness $a$ . Then $P (a)$ is false, so $P$ does not hold of every element, so $\forall x P (x)$ is false and $\neg\forall x P (x)$ is true. The two statements hold under exactly the same circumstances.

For the second law, apply the first to the predicate $\neg P$ : $\neg\forall x \neg P (x) \equiv \exists x \neg\neg P (x) \equiv \exists x P (x)$ . Negating both sides gives $\forall x \neg P (x) \equiv \neg\exists x P (x)$ .∎

Intuition. To deny "everything works", you need one broken thing. To deny "something works", you must certify that all of them are broken. Negation swaps the quantifier and pushes inward, exactly as it swaps $\land$ and $\lor$ — which is no coincidence, since over a finite domain the quantifiers are iterated $\land$ and $\lor$ .

Definition 1.35 (Nested quantifiers). Quantifiers may be applied in sequence, as in $\forall x \exists y P (x, y)$ , where $P$ is a predicate of two variables. The quantifiers are read left to right, and the value chosen for a variable may depend on the variables quantified to its left.

Corollary 1.36 (Negating a nested quantifier string). For a block of quantifiers $Q_{1} x_{1} Q_{2} x_{2} \dots Q_{n} x_{n} P (x_{1}, \dots, x_{n})$ , the negation is obtained by replacing every $\forall$ with $\exists$ and every $\exists$ with $\forall$ , in place, and negating $P$ :

\neg Q_{1} x_{1} \dots Q_{n} x_{n} P \equiv \overline{Q_{1}} x_{1} \dots \overline{Q_{n}} x_{n} \neg P,

where

\overline{\forall} = \exists

and

\overline{\exists} = \forall

Proof. Induct on the number $n$ of quantifiers. For $n = 1$ this is exactly the theorem De Morgan's laws for quantifiers.

Suppose it holds for blocks of $n$ quantifiers, and consider $Q_{1} x_{1} (R)$ where $R = Q_{2} x_{2} \dots Q_{n + 1} x_{n + 1} P$ is a block of $n$ . For each fixed value of $x_{1}$ , $R$ is a statement about the remaining variables, so the case $n = 1$ gives $\neg Q_{1} x_{1} (R) \equiv \overline{Q_{1}} x_{1} (\neg R)$ . By the inductive hypothesis $\neg R \equiv \overline{Q_{2}} x_{2} \dots \overline{Q_{n + 1}} x_{n + 1} \neg P$ . Substituting completes the step.∎

Example 1.37 (Negating a limit-style statement). Negate: "for every $ε > 0$ there exists $N \in N$ such that for all $n > N$ , $∣ a_{n} - L ∣ < ε$ . "

Solution.

Symbolically, $\forall ε > 0 \exists N \forall n > N (∣ a_{n} - L ∣ < ε)$ .
By Negating a nested quantifier string, flip all three quantifiers and negate the core: $\exists ε > 0 \forall N \exists n > N (∣ a_{n} - L ∣ \geq ε)$ .
In words: some $ε$ is bad, in the sense that however far out you go there is still a later term at distance at least $ε$ from $L$ .
Notice each flip happens in place; the order of the variables never changes, and $ε$ stays outermost.

□

Theorem 1.38 (Order of quantifiers matters). There is a predicate $P$ over a domain $D$ for which $\forall x \exists y P (x, y)$ is true and $\exists y \forall x P (x, y)$ is false. The two are therefore not equivalent.

Proof. Take $D = Z$ and $P (x, y)$ the statement $y > x$ .

$\forall x \exists y (y > x)$ is true: given any integer $x$ , the integer $y = x + 1$ satisfies $y > x$ , so a witness exists for each $x$ .

$\exists y \forall x (y > x)$ is false: it asserts a single integer $y$ exceeding every integer, and taking $x = y$ gives $y > y$ , which is false. So no such $y$ exists.

One statement true and the other false is exactly a failure of equivalence.∎

Intuition. In $\forall x \exists y$ the witness $y$ may be chosen after seeing $x$ , and may depend on it. In $\exists y \forall x$ the witness must be committed to first and then work for every $x$ . "Every lock has a key" is not "some key opens every lock". Reading the quantifier prefix as an order of play — the $\forall$ moves are the adversary's, the $\exists$ moves are yours — makes the asymmetry hard to forget.

Example 1.39 (Translating and negating a database claim). Let $S (x, y)$ mean "student $x$ has submitted assignment $y$ ", over students $X$ and assignments $Y$ . Express "some student has submitted every assignment", and its negation, in words.

Solution.

The claim is $\exists x \in X \forall y \in Y S (x, y)$ .
Its negation flips both quantifiers: $\forall x \in X \exists y \in Y \neg S (x, y)$ .
In words: every student has missed at least one assignment — and which assignment they missed may differ from student to student, since $y$ is chosen after $x$ .
Contrast with the negation of $\forall y \exists x S (x, y)$ ("every assignment has been submitted by someone"), which is $\exists y \forall x \neg S (x, y)$ : some assignment nobody submitted.

□

Proposition 1.40 (Universal quantification distributes over conjunction only). For predicates $P, Q$ over a domain $D$ ,

\forall x (P (x) \land Q (x)) \equiv (\forall x P (x)) \land (\forall x Q (x)),

but

\forall x (P (x) \lor Q (x))

and

(\forall x P (x)) \lor (\forall x Q (x))

are not equivalent.

Proof. For the equivalence: if $P (a) \land Q (a)$ holds for every $a$ then in particular $P (a)$ holds for every $a$ and $Q (a)$ holds for every $a$ , giving the right side. Conversely if both conjuncts on the right hold, then for any $a$ both $P (a)$ and $Q (a)$ hold, so $P (a) \land Q (a)$ does.

For the non-equivalence, let $D = Z$ , $P (x)$ be " $x$ is even" and $Q (x)$ be " $x$ is odd". Every integer is one or the other, so $\forall x (P (x) \lor Q (x))$ is true; but neither "every integer is even" nor "every integer is odd" is true, so the right side is false.∎

Exercises for §1.4 →

1.5Rules of inference

An equivalence says two statements carry the same information. An inference is different: it takes premises and produces a conclusion that may say strictly less, and the demand on it is only that it never manufactures a falsehood from truths.

Definition 1.41 (Argument and validity). An argument is a list of premises $φ_{1}, \dots, φ_{k}$ together with a conclusion $ψ$ . It is valid if under every truth assignment making all the premises true, $ψ$ is also true — equivalently, if $(φ_{1} \land \dots \land φ_{k}) \to ψ$ is a tautology. An argument is sound if it is valid and its premises are in fact true.

Validity is about form and nothing else. A valid argument from false premises can have a false conclusion, and that is no defect in the argument. What a valid argument guarantees is only this: you will never pass from truth to falsehood.

Theorem 1.42 (Modus ponens). The argument with premises $p$ and $p \to q$ and conclusion $q$ is valid.

Proof. Consider any truth assignment making both premises true. Since $p$ is true, the row in question has a true antecedent. Since $p \to q$ is true and $p \to q$ is false exactly when $p$ is true and $q$ is false, that combination is excluded; so $q$ is not false. Hence $q$ is true, which is what validity requires.∎

Theorem 1.43 (Modus tollens). The argument with premises $\neg q$ and $p \to q$ and conclusion $\neg p$ is valid.

Proof. By the theorem A conditional is equivalent to its contrapositive, the premise $p \to q$ may be replaced by the equivalent $\neg q \to \neg p$ without changing any truth value. The argument is then: premises $\neg q$ and $\neg q \to \neg p$ , conclusion $\neg p$ , which is an instance of Modus ponens with $\neg q$ for $p$ and $\neg p$ for $q$ . Hence it is valid.∎

Theorem 1.44 (Hypothetical syllogism). The argument with premises $p \to q$ and $q \to r$ and conclusion $p \to r$ is valid.

Proof. Take an assignment making both premises true, and suppose for the sake of the argument that $p \to r$ is false under it. Then $p$ is true and $r$ is false. From $p$ true and $p \to q$ true, Modus ponens gives $q$ true. From $q$ true and $q \to r$ true, Modus ponens gives $r$ true. But $r$ is false. So $p \to r$ cannot be false under such an assignment, and it is therefore true whenever both premises are.∎

Proposition 1.45 (Affirming the consequent is invalid). The argument with premises $q$ and $p \to q$ and conclusion $p$ is not valid. Neither is the argument with premises $\neg p$ and $p \to q$ and conclusion $\neg q$ .

Proof. Take $p$ false and $q$ true. Then the premise $q$ is true, and $p \to q$ is true because its antecedent is false; but the conclusion $p$ is false. A single such assignment refutes validity. The same assignment refutes the second argument: $\neg p$ is true, $p \to q$ is true, and the conclusion $\neg q$ is false.∎

Example 1.46 (Diagnosing three arguments). Which of these are valid? (a) If the input is sorted the search returns in $O (lo g n)$ ; the search returned in $O (lo g n)$ ; therefore the input was sorted. (b) If a number is divisible by $6$ it is divisible by $3$ ; $n$ is not divisible by $3$ ; therefore $n$ is not divisible by $6$ . (c) If it rains the match is cancelled; if the match is cancelled refunds are issued; therefore if it rains refunds are issued.

Solution.

(a) has the form $q$ , $p \to q$ , therefore $p$ — affirming the consequent, invalid by Affirming the consequent is invalid. A sorted-input guarantee says nothing about unsorted inputs that happen to finish fast, such as a one-element array.
(b) has the form $\neg q$ , $p \to q$ , therefore $\neg p$ — Modus tollens, valid. It is also sound, since the premise about $6$ and $3$ is true.
(c) has the form $p \to q$ , $q \to r$ , therefore $p \to r$ — Hypothetical syllogism, valid. Note it is valid whether or not it ever rains.

□

Remark. One can go further and ask for a complete list of rules: a fixed finite set from which every valid propositional argument can be derived by pure symbol manipulation, and a theorem saying derivability and validity coincide. Such systems exist, and the theorem is the completeness theorem for propositional logic. Building the calculus and proving that theorem is the business of Mathematical Logic; here we use the rules informally and justify each by its truth table.

Exercises for §1.5 →

1.6Direct proof and proof by contraposition

Almost every theorem worth stating has the form $\forall x \in D (P (x) \to Q (x))$ . A direct proof attacks it head on: fix an arbitrary $x$ , assume $P (x)$ , and derive $Q (x)$ by a chain of definitions and previously established results. The word arbitrary is carrying the weight — because nothing beyond $P (x)$ was assumed about $x$ , the argument applies to every element of $D$ , and that is how a finite argument establishes an infinite family of statements.

Definition 1.47 (Parity). An integer $n$ is even if $n = 2 k$ for some integer $k$ , and odd if $n = 2 k + 1$ for some integer $k$ . Every integer is exactly one of the two.

Example 1.48 (A direct proof about parity). Prove that the sum of two odd integers is even, and that the product of two odd integers is odd.

Solution.

Let $m$ and $n$ be arbitrary odd integers. By the definition of Parity write $m = 2 a + 1$ and $n = 2 b + 1$ with $a, b \in Z$ .
Then $m + n = 2 a + 2 b + 2 = 2 (a + b + 1)$ . Since $a + b + 1$ is an integer, $m + n$ is even.
And $mn = (2 a + 1) (2 b + 1) = 4 ab + 2 a + 2 b + 1 = 2 (2 ab + a + b) + 1$ , with $2 ab + a + b$ an integer, so $mn$ is odd.
The proof used nothing about $m$ and $n$ beyond oddness, so it holds for every odd pair — including negative ones, since $a$ and $b$ were allowed to be any integers.

□

Direct proof runs out of road when the hypothesis is hard to use. "If $n^{2}$ is even then $n$ is even" gives you a fact about $n^{2}$ , and prying $n$ out of it requires the fundamental theorem of arithmetic. The contrapositive hands you $n$ odd, which is an immediate construction.

Theorem 1.49 (Validity of proof by contraposition). To prove $P \to Q$ it suffices to prove $\neg Q \to \neg P$ .

Proof. Suppose $\neg Q \to \neg P$ has been established. By the theorem A conditional is equivalent to its contrapositive, $\neg Q \to \neg P \equiv P \to Q$ , since the contrapositive of $\neg Q \to \neg P$ is $\neg\neg P \to \neg\neg Q$ , which is $P \to Q$ . Logically equivalent statements have the same truth value under every assignment, so $P \to Q$ is true as well.∎

Proposition 1.50 (Squares and parity). For every integer $n$ : if $n^{2}$ is even then $n$ is even.

Proof. We prove the contrapositive: if $n$ is odd then $n^{2}$ is odd, which by Validity of proof by contraposition establishes the claim.

Let $n$ be odd, so $n = 2 k + 1$ for some integer $k$ . Then

n^{2} = (2 k + 1)^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1,

and

2 k^{2} + 2 k

is an integer, so

n^{2}

is odd.∎

Intuition. Contraposition is not a different logic; it is the same statement read from the other end. The reason it helps so often is purely practical: a negated conclusion is frequently a constructive hypothesis. " $n$ is not even" means " $n = 2 k + 1$ ", something you can substitute into an expression, whereas " $n^{2}$ is even" means " $n^{2} = 2 m$ " for an $m$ you know nothing about.

Example 1.51 (Choosing between direct and contrapositive). Prove: for integers $a, b$ , if $a + b \geq 15$ then $a \geq 8$ or $b \geq 8$ .

Solution.

The conclusion is a disjunction, awkward to produce directly. Negate it: by De Morgan's laws, $\neg (a \geq 8 \lor b \geq 8)$ is $a \leq 7 \land b \leq 7$ .
So prove the contrapositive: if $a \leq 7$ and $b \leq 7$ then $a + b \leq 14$ , that is $a + b < 15$ .
That is immediate: adding the two inequalities gives $a + b \leq 7 + 7 = 14$ .
By Validity of proof by contraposition the original statement follows. Contraposition turned a disjunctive conclusion into a conjunctive hypothesis, which is the general reason to reach for it here.

□

Definition 1.52 (Proving a biconditional). To prove $P \leftrightarrow Q$ one proves both $P \to Q$ and $Q \to P$ ; each direction may use whichever technique suits it. For a chain $P_{1} \leftrightarrow P_{2} \leftrightarrow \dots \leftrightarrow P_{k}$ it suffices to prove the cycle $P_{1} \to P_{2} \to \dots \to P_{k} \to P_{1}$ .

Example 1.53 (A biconditional in two directions). Prove that an integer $n$ is odd if and only if $n^{2}$ is odd.

Solution.

( $\Rightarrow$ ) If $n$ is odd then $n^{2}$ is odd, proved directly inside Squares and parity.
( $\Leftarrow$ ) If $n^{2}$ is odd then $n$ is odd. Contrapositive: if $n$ is even, $n = 2 k$ , then $n^{2} = 4 k^{2} = 2 (2 k^{2})$ is even.
Both directions hold, so the biconditional holds. Note that each direction was proved by a different route; that is normal and is why a biconditional is two theorems.

□

Pitfall. Proving $P \to Q$ and then also proving $P \to Q$ again in different words is not proving a biconditional. Before writing the second half, check that you have genuinely swapped hypothesis and conclusion. The commonest way to lose marks on an "if and only if" is to prove one direction twice.

Exercises for §1.6 →

1.7Proof by contradiction

Contraposition assumes the negation of the conclusion and aims at the negation of the hypothesis. Contradiction is more aggressive: it assumes the negation of the whole statement and aims at anything impossible at all.

Theorem 1.54 (Validity of proof by contradiction). Let $S$ be a proposition. If $\neg S \to (r \land \neg r)$ is true for some proposition $r$ , then $S$ is true.

Proof. The proposition $r \land \neg r$ is false under every truth assignment: whichever value $r$ takes, one of the two conjuncts is false.

Now suppose $\neg S \to (r \land \neg r)$ is true and suppose, towards the conclusion, that $S$ is false. Then $\neg S$ is true, and a conditional with true antecedent and true value must have true consequent — by Modus ponens we infer $r \land \neg r$ . But that proposition is false under every assignment. So $S$ false is impossible, and since $S$ takes one of two values, $S$ is true.∎

Intuition. A contradiction is the only thing a consistent set of assumptions can never produce. So if your assumptions yield one, at least one of them is wrong — and if every assumption but $\neg S$ was already established, the wrong one is $\neg S$ . The technique is powerful precisely because the target is so cheap: you may aim at any absurdity, not a specific conclusion, which is why it works on statements that assert non-existence, where there is nothing to construct.

Definition 1.55 (Rational and irrational). A real number $x$ is rational if $x = a / b$ for integers $a, b$ with $b \neq = 0$ , and irrational otherwise. Every rational may be written in lowest terms, with $a$ and $b$ sharing no common factor greater than $1$ .

Theorem 1.56 (Irrationality of the square root of two). There is no rational number $x$ with $x^{2} = 2$ . That is, $2$ is irrational.

Proof. Suppose, for contradiction, that $2$ is rational. Then we may write

2 = \frac{a}{b}

with

a, b

integers,

b \neq = 0

, and the fraction in lowest terms, so that

a

and

b

have no common factor greater than

1

Squaring and clearing the denominator gives $a^{2} = 2 b^{2}$ . Hence $a^{2}$ is even, and by the proposition Squares and parity, $a$ is even. Write $a = 2 c$ with $c$ an integer.

Substituting, $4 c^{2} = 2 b^{2}$ , so $b^{2} = 2 c^{2}$ . Hence $b^{2}$ is even, and by Squares and parity again, $b$ is even.

So $a$ and $b$ are both even, and therefore share the common factor $2$ . This contradicts the choice of the fraction in lowest terms. The assumption that $2$ is rational is therefore untenable, and by Validity of proof by contradiction no rational squares to $2$ .∎

Remark. The lowest-terms hypothesis is doing real work and it is where the finiteness hides. Without it the argument still runs — one gets an infinite descent $a > a /2 > a /4 > \dots$ of positive integers, which is impossible by well-ordering. Both versions ultimately appeal to the fact that a set of positive integers cannot descend forever, the same principle that will underwrite induction in the next section.

Example 1.57 (Contradiction where construction is unavailable). Prove that there is no smallest positive rational number.

Solution.

Suppose for contradiction that $q$ is the smallest positive rational.
Then $q /2$ is rational, since the rationals are closed under division by $2$ , and $q /2 > 0$ since $q > 0$ .
But $q /2 < q$ , contradicting the minimality of $q$ .
Hence no smallest positive rational exists. Notice there was nothing to construct here — the statement asserts a non-existence, so contradiction is the natural tool.

□

Pitfall. Two failure modes look like proof by contradiction and are not. The first is assuming $\neg S$ , deriving $\neg P$ where $P$ was a hypothesis, and calling it a contradiction — that is contraposition, correctly done, and should be written as such; dressing it up as contradiction adds an unused assumption and obscures the argument. The second is deriving something merely surprising rather than logically impossible. "Therefore $n$ is very large" is not a contradiction. You must exhibit a proposition and its negation.

Exercises for §1.7 →

1.8Mathematical induction, strong induction and well-ordering

Induction proves infinitely many statements with two finite arguments. It is the characteristic technique of discrete mathematics because its domain is $N$ , a set with a starting point and a successor operation and nothing in between.

Theorem 1.58 (Principle of mathematical induction). Let $P (n)$ be a predicate over the integers $n \geq n_{0}$ . Suppose

$P (n_{0})$ is true (the base case), and
for every $k \geq n_{0}$ , $P (k) \to P (k + 1)$ (the inductive step).

Then $P (n)$ is true for every integer $n \geq n_{0}$ .

Proof. Let $C = {n \in Z : n \geq n_{0} and P (n) is false}$ be the set of counterexamples, and suppose it is nonempty. Shifting by $n_{0}$ , the set ${n - n_{0} : n \in C}$ is a nonempty set of non-negative integers, so by the well-ordering principle it has a least element; hence $C$ has a least element $m$ .

By hypothesis 1, $P (n_{0})$ is true, so $m \neq = n_{0}$ and therefore $m > n_{0}$ . Then $m - 1 \geq n_{0}$ , and $m - 1 \in / C$ by minimality of $m$ , so $P (m - 1)$ is true. Hypothesis 2 applied at $k = m - 1$ gives $P (m - 1) \to P (m)$ , and Modus ponens yields $P (m)$ true. But $m \in C$ means $P (m)$ is false.

So $C$ is empty, which says $P (n)$ holds for every $n \geq n_{0}$ .∎

Figure 1.59. Induction as a chain of dominoes. The base case topples the first domino; the inductive step is the guarantee that any domino that falls knocks over its successor. Neither half alone does anything: a first push with a gap in the chain stops at the gap, and a perfect chain nobody pushes stands forever.

Theorem 1.60 (Sum of the first n positive integers). For every integer $n \geq 1$ ,

1 + 2 + \dots + n = \frac{n ( n + 1 )}{2} .

Proof. Let $P (n)$ be the displayed statement.

Base case. For $n = 1$ the left side is $1$ and the right side is $1 \cdot 2/2 = 1$ , so $P (1)$ holds.

Inductive step. Let $k \geq 1$ and assume $P (k)$ , that is $1 + \dots + k = k (k + 1) /2$ . Then

1 + \dots + k + (k + 1) = \frac{k ( k + 1 )}{2} + (k + 1) = (k + 1) (\frac{k}{2} + 1) = \frac{( k + 1 ) ( k + 2 )}{2},

which is the statement

P (k + 1)

Both hypotheses of the Principle of mathematical induction hold with $n_{0} = 1$ , so $P (n)$ holds for every $n \geq 1$ .∎

Example 1.61 (An inequality by induction). Prove that $2^{n} > n$ for every integer $n \geq 1$ , and identify where the inductive hypothesis is used.

Solution.

Base case $n = 1$ : $2^{1} = 2 > 1$ ✓.
Step: assume $2^{k} > k$ for some $k \geq 1$ . Then $2^{k + 1} = 2 \cdot 2^{k} > 2 k$ , where the inductive hypothesis was used to replace $2^{k}$ .
Since $k \geq 1$ we have $2 k = k + k \geq k + 1$ , so $2^{k + 1} > 2 k \geq k + 1$ .
By the Principle of mathematical induction, $2^{n} > n$ for all $n \geq 1$ . The hypothesis $k \geq 1$ was needed at step 3; the argument would break at $k = 0$ , where $2 k = 0 < k + 1$ .

□

Sometimes $P (k)$ alone is not enough and one needs the whole history below $k$ . The classic case is a statement about factorisation, where splitting $n = ab$ produces two smaller numbers, neither of which is $n - 1$ .

Theorem 1.62 (Strong induction). Let $P (n)$ be a predicate over integers $n \geq n_{0}$ . Suppose that for every $k \geq n_{0}$ ,

(P (n_{0}) \land P (n_{0} + 1) \land \dots \land P (k - 1)) \to P (k) .

Then

P (n)

holds for all

n \geq n_{0}

Proof. We derive this from the Principle of mathematical induction applied to a different predicate. Define

Q (n) : P (j) holds for every integer j with n_{0} \leq j \leq n .

Base case. At $k = n_{0}$ the hypothesis has an empty conjunction of antecedents, which is vacuously true, so the hypothesis delivers $P (n_{0})$ outright. Hence $Q (n_{0})$ holds.

Inductive step. Assume $Q (k)$ for some $k \geq n_{0}$ ; that is, $P (j)$ holds for all $j$ from $n_{0}$ to $k$ . This is exactly the antecedent of the hypothesis at $k + 1$ , so $P (k + 1)$ follows. Combining with $Q (k)$ , $P (j)$ holds for all $j$ from $n_{0}$ to $k + 1$ , which is $Q (k + 1)$ .

By the Principle of mathematical induction, $Q (n)$ holds for every $n \geq n_{0}$ . Since $Q (n)$ implies $P (n)$ , the conclusion follows.∎

Remark. Strong induction is therefore not a stronger axiom — it proves nothing that ordinary induction cannot. It is a stronger convenience: the inductive hypothesis you are handed is larger, and you may reach back as far as you like. Note also that a separate base case is usually still written out in practice, because checking that the step really does work at the smallest values is where flawed inductions are caught.

Proposition 1.63 (Every integer above one has a prime divisor). Every integer $n \geq 2$ has a prime divisor.

Proof. By strong induction on $n \geq 2$ . Let $k \geq 2$ and assume every integer $j$ with $2 \leq j < k$ has a prime divisor.

If $k$ is prime, then $k$ is a prime divisor of itself and we are done. Otherwise $k$ is composite, so $k = ab$ with integers $2 \leq a < k$ and $2 \leq b < k$ . The inductive hypothesis applies to $a$ , giving a prime $p$ with $p ∣ a$ . Since $a ∣ k$ , transitivity of divisibility gives $p ∣ k$ .

By the theorem Strong induction, every $n \geq 2$ has a prime divisor. Notice that ordinary induction is useless here: knowing about $k - 1$ tells us nothing about the factors of $k$ .∎

Theorem 1.64 (Well-ordering is equivalent to induction). The following are equivalent over the integers.

(Well-ordering) Every nonempty set of non-negative integers has a least element.
(Induction) Any predicate $P$ with $P (0)$ true and $P (k) \to P (k + 1)$ for all $k \geq 0$ holds for all $n \geq 0$ .

Proof. $(1) \Rightarrow (2)$ is the proof of the Principle of mathematical induction given above, with $n_{0} = 0$ : the set of counterexamples is a nonempty set of non-negative integers, so it has a least element, and that least element is neither $0$ nor a successor of a non-counterexample.

$(2) \Rightarrow (1)$ . Let $S$ be a set of non-negative integers with no least element; we show $S$ is empty. Let $P (n)$ be the statement "no integer $j$ with $0 \leq j \leq n$ lies in $S$ ".

$P (0)$ holds: if $0 \in S$ then $0$ would be a least element of $S$ , since no non-negative integer is smaller.

Assume $P (k)$ . If $k + 1 \in S$ , then since no $j \leq k$ is in $S$ , every element of $S$ is at least $k + 1$ , making $k + 1$ a least element of $S$ — contrary to assumption. So $k + 1 \in / S$ , and with $P (k)$ this gives $P (k + 1)$ .

By (2), $P (n)$ holds for all $n \geq 0$ , so no non-negative integer belongs to $S$ , and $S$ is empty. Contrapositively, a nonempty such set has a least element.∎

Intuition. The two principles are the same fact about $N$ seen from opposite ends. Induction says you can climb the ladder from the bottom; well-ordering says you cannot fall down it forever. Both fail for the rationals in $[0, 1]$ : there is no "next" rational after $0$ , and ${q \in Q : q > 0}$ has no least element, which is exactly what the example about the smallest positive rational showed.

An induction that proves something false

Every hypothesis in the Principle of mathematical induction is load-bearing, and the fastest way to feel that is to watch an argument that satisfies neither carefully enough.

Example 1.65 (All horses are the same colour). The following argues that in any set of $n \geq 1$ horses, all the horses have the same colour. Find the error.

Base case. A set of one horse: all its horses trivially share a colour. ✓

Inductive step. Assume any set of $k$ horses is monochromatic, and take a set $H$ of $k + 1$ horses, labelled $h_{1}, \dots, h_{k + 1}$ . The set $A = {h_{1}, \dots, h_{k}}$ has $k$ horses, so all of them share a colour. The set $B = {h_{2}, \dots, h_{k + 1}}$ also has $k$ horses, so all of them share a colour. The two sets overlap — $h_{2}$ lies in both — so the colour of $A$ equals the colour of $h_{2}$ equals the colour of $B$ , and all $k + 1$ horses share one colour.

Solution.

The base case is fine, and the inductive step is fine for every $k \geq 2$ . The failure is at exactly one value: $k = 1$ .
At $k = 1$ the set $H$ has two horses, $A = {h_{1}}$ and $B = {h_{2}}$ . The step's argument needs a horse lying in both $A$ and $B$ so that the two colours can be identified. Here $A \cap B = \emptyset$ : the sentence " $h_{2}$ lies in both" is false, because $A$ stops at $h_{1}$ .
So the implication $P (1) \to P (2)$ was never established, and the chain is broken at its first link. Everything after it — $P (2) \to P (3)$ , and so on — is genuinely valid, but there is nothing to propagate, since $P (2)$ is false.
The diagnosis in one line: the inductive step used an unstated hypothesis, $k \geq 2$ , while the base case supplied only $k = 1$ . The fix would be to verify $P (2)$ directly, which is of course impossible, since $P (2)$ says any two horses match.

□

Pitfall. Whenever an inductive step involves splitting, overlapping, or removing elements, check the step at the smallest value of $k$ it is meant to cover, by substituting that number and reading the resulting sentences literally. Arguments that are obviously correct "in general" routinely collapse at $k = 1$ or $k = 2$ , where a set becomes empty, an overlap disappears, or a sum has no terms.

Summary. The chapter's spine: a compound proposition is determined by a truth table of $2^{n}$ rows, so there are $2^{2^{n}}$ of them; every table has a DNF, hence ${\neg, \land}$ and even ${∣}$ alone are functionally complete. Equivalence licenses rewriting, and the two rewrites that matter most are De Morgan and contraposition — the latter valid, the converse not. Quantifiers extend this to predicates, with De Morgan reappearing as $\neg\forall = \exists\neg$ , and with the order of nested quantifiers carrying real content. The valid inference patterns — modus ponens, modus tollens, hypothetical syllogism — are each read off a truth table. Those tables then justify the proof techniques themselves: contraposition from the contrapositive equivalence, contradiction from the fact that $r \land \neg r$ is never true. Finally, induction, strong induction and well-ordering are three presentations of one fact about $N$ , and each derives from either of the others.

Exercises for §1.8 →

Common Mistakes

Confusing a conditional with its converse. "If $4 ∣ n$ then $n$ is even" is true; the converse is false at $n = 6$ . Only the contrapositive comes free.
Denying a conditional with another conditional. By Negating a conditional, $\neg (p \to q)$ is $p \land \neg q$ , not $p \to \neg q$ . Refuting an implication means exhibiting one case, not proving a new implication.
Refusing vacuous truth. "Every element of the empty set is red" is true. Any other convention would force the empty set to contain a non-red element.
Forgetting to flip the connective under De Morgan. $\neg (p \land q)$ is $\neg p \lor \neg q$ . Turning an && guard into a negated && guard is the classic off-by-one-connective bug.
Swapping nested quantifiers. $\forall x \exists y$ lets $y$ depend on $x$ ; $\exists y \forall x$ does not. "Every lock has a key" is not "some key opens every lock", as the theorem Order of quantifiers matters makes precise.
Negating a quantifier block out of order. Flip each quantifier in place and negate the innermost predicate; never move a variable past another.
Affirming the consequent. From $p \to q$ and $q$ , nothing follows about $p$ . Validity is a property of the form, and this form has a counterexample row.
Confusing validity with truth. A valid argument from false premises proves nothing about the world; an invalid argument may still have a true conclusion, by luck.
Proving a universal statement with an example. One case establishes $\exists$ , never $\forall$ . Conversely, one counterexample refutes $\forall$ completely — no further work is needed.
Calling a surprise a contradiction. Proof by contradiction needs an explicit $r \land \neg r$ . "This makes $n$ enormous" is not a contradiction.
Dressing contraposition up as contradiction. If your contradiction proof assumes $\neg Q$ and derives $\neg P$ , it is a contraposition proof with a spare assumption. Write it as one; it is shorter and clearer.
Omitting or faking the base case. The step alone proves nothing: " $n = n + 1$ implies $n + 1 = n + 2$ " is a perfectly valid step for a false statement.
Running the inductive step below the range where it works. This is the horses error. Check the step at its smallest $k$ , literally.
Assuming what is to be proved. The inductive hypothesis is $P (k)$ , for one fixed unspecified $k$ — never $P (n)$ for all $n$ , and never $P (k + 1)$ .
Reaching for strong induction without needing it, or refusing it when you do. Splitting $n = ab$ lands at two arbitrary smaller values, so ordinary induction cannot reach them; a recurrence in $n - 1$ alone does not need the stronger form.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter