What follows from what, and how to write it down
Last modified: 2026-10-27 13:24:37 (PDT)
Source
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Logic 4, Proofs Intro, Direct Proof”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. The rules of inference, the definition of “divides”, the observation that a definition’s “if” means “if and only if”, the template for a direct proof, and the ideas of proof by cases and “without loss of generality” come from those notes; the exercises are new.
The definitions of logical entailment, the integers, even and odd integers, and proof are included from the mathematics prerequisites notes, so they read the same in both places.
Exercise 1 (Which conclusions are safe?) Let \(P\) be “the tests pass”, \(Q\) be “the build is deployed” and \(R\) be “the build is rolled back”. Each argument below lists some propositions, then “so”, then one more proposition. For each argument, decide whether the proposition after “so” must be true whenever all of the propositions before it are true.
Solution 1.
Definition 1 (Argument) An argument is a list of propositions (Definition: Proposition (statement)), called its premises, together with one more proposition, called its conclusion. An argument is written with “so” or \(\therefore\) before its conclusion.
Remark 1 (Two uses of “premise” and “conclusion”). The premise and conclusion of a conditional \(P \Rightarrow Q\) (Remark: Names for the parts, and other notation) are its parts \(P\) and \(Q\). The premises and conclusion of an argument (Definition 1) are whole propositions: in argument 1 of Exercise 1, the premises are \(P \Rightarrow Q\) and \(P\), and the conclusion is \(Q\).
Definition 2 (Logical entailment (logical consequence, deductive consequence)) Propositions or predicates \(P_1, \ldots, P_n\) (Definition: Proposition (statement), Definition: Predicate) logically entail (Wikipedia contributors 2026b) a proposition or predicate \(Q\) when every choice of values for their variables that makes all of \(P_1, \ldots, P_n\) true also makes \(Q\) true. Then \(Q\) is a logical consequence, or deductive consequence, of \(P_1, \ldots, P_n\).
Example 1 (Entailment in the deployment arguments) In Exercise 1, the premises of arguments 1, 3 and 4 (Definition 1) logically entail their conclusions (Definition 2). The premises of argument 2 do not: the values \(P\) false and \(Q\) true make both premises true and the conclusion false.
Definition 3 (Rule of inference) A rule of inference is a pattern of argument (Definition 1), written in terms of propositions \(P, Q, \ldots\), whose premises logically entail its conclusion (Definition 2) whatever propositions are put in place of \(P, Q, \ldots\). It is written with its premises above a line and its conclusion below: \[ \frac{P_1, \ldots, P_n}{Q}. \]
Example 2 (Modus ponens) Argument 1 of Exercise 1 follows the pattern \[ \frac{P \Rightarrow Q, \quad P}{Q}, \] called modus ponens. It is a rule of inference (Definition 3): by Solution 1, its premises entail its conclusion for any propositions \(P\) and \(Q\), not only for tests and builds.
Theorem 1 (Common rules of inference) For propositions \(P\) and \(Q\), each of the following is a rule of inference (Definition 3):
Example 3 (Modus tollens on a slow page) “If the cache is warm, then the page loads in under a second” and “the page did not load in under a second” together give “the cache is not warm”, by modus tollens (Theorem 1).
Remark 2 (Two arguments that are not rules of inference). Argument 2 of Exercise 1, \[ \frac{P \Rightarrow Q, \quad Q}{P}, \] is called affirming the consequent, since it concludes \(P\) from the consequent \(Q\) of \(P \Rightarrow Q\) (Remark: Names for the parts, and other notation). It is not a rule of inference (Definition 3): \(P\) false and \(Q\) true make its premises true and its conclusion false.
Denying the antecedent, \[ \frac{P \Rightarrow Q, \quad \neg P}{\neg Q}, \] fails for the same values of \(P\) and \(Q\). Both read like modus ponens or modus tollens (Theorem 1), which is why they are common mistakes.
Exercise 2 (Two times something, plus maybe one) Write each of \(14\), \(15\), \(-7\) and \(0\) as \(2k\) or as \(2k + 1\), for an integer \(k\).
Solution 2.
Definition 4 (Integers) The integers (Wikipedia contributors 2026a) are the whole numbers, together with their negatives and \(0\):
\[\mathbb{Z} \stackrel{\text{def}}{=}\mathopen{}\left\{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\right\}\mathclose{}\]
An integer is an element of \(\mathbb{Z}\).
Definition 5 (Positive integers) The integers (Definition 4) greater than \(0\) are the positive integers.
Definition 6 (Negative integers) The integers (Definition 4) less than \(0\) are the negative integers.
Example 4 (Integers and non-integers)
Definition 7 (Even integer) An integer (Definition 4) \(n\) is even (Wikipedia contributors 2026d) if \(n = 2k\) for some integer \(k\).
Definition 8 (Odd integer) An integer (Definition 4) \(n\) is odd (Wikipedia contributors 2026d) if \(n = 2k + 1\) for some integer \(k\).
Example 5 (Even and odd integers)
Remark 3 (Facts about integers used without proof). These notes use two facts about the integers (Definition 4) without proving them:
Remark 4 (A definition’s “if” means “if and only if”). Definition 7 says that \(n\) is even “if” \(n = 2k\) for some integer \(k\), but it means “if and only if” (Definition: If and only if): an integer is even exactly when it can be written as \(2k\). So a proof can use a definition in both directions: to show that \(n\) is even, write \(n\) as \(2k\); and from “\(n\) is even”, conclude that \(n = 2k\) for some integer \(k\).
Definition 9 (Divides) Let \(a\) and \(b\) be integers (Definition 4). We say that \(a\) divides \(b\), written \(a \mid b\), if \(b = a c\) for some integer \(c\). When \(a\) does not divide \(b\), we write \(a \nmid b\).
Example 6 (Divisors)
Remark 5 (Divisibility in Racket). For a nonzero integer a, Racket’s (remainder b a) returns 0 exactly when \(a \mid b\) (Definition 9), so (zero? (remainder b a)) tests divisibility. (zero? (remainder 12 3)) returns #t and (zero? (remainder 13 3)) returns #f, as in Example 6. (remainder 12 0) raises an error, so a Racket test of \(a \mid b\) has to handle \(a = 0\) on its own.
Exercise 3 (An odd input) Show that if \(n\) is an odd integer, then \(3 n + 5\) is even.
Hint
What does Definition 8 let you write in place of \(n\)?
Solution 3. Suppose \(n\) is an odd integer. By Definition 8, \(n = 2 k + 1\) for some integer \(k\). Then \[ 3 n + 5 = 3 (2 k + 1) + 5 = 6 k + 3 + 5 = 6 k + 8 = 2 (3 k + 4). \] Since \(3 k + 4\) is an integer (Remark 3), \(3 n + 5\) is even, by Definition 7.
Definition 10 (Proof) A proof (Wikipedia contributors 2026c) of a proposition (Definition: Proposition (statement)) is a finite list of statements that ends with that proposition, in which each statement is
Example 7 (A proof, statement by statement) Solution 3 is a proof (Definition 10) of “\(3 n + 5\) is even” in which “\(n\) is an odd integer” is an assumption. Its statements are:
Definition 11 (Direct proof) A direct proof of a conditional \(P \Rightarrow Q\) (Definition: Implies) is a proof (Definition 10) of \(Q\) in which \(P\) is an assumption.
Example 8 (A direct proof) Solution 3 is a direct proof (Definition 11) of “if \(n\) is an odd integer, then \(3 n + 5\) is even”: it assumes \(P\), “\(n\) is an odd integer”, and ends with \(Q\), “\(3 n + 5\) is even”.
Remark 6 (The shape of a direct proof). A direct proof (Definition 11) of “if \(P\), then \(Q\)” has this shape:
Suppose \(P\).
\(\vdots\)
Therefore \(Q\).
Write the first and last lines first, then fill in the middle, usually by replacing each defined term with its definition (Remark 4).
A direct proof proves \(P \Rightarrow Q\): when \(P\) is true, the proof shows that \(Q\) is true, and when \(P\) is false, \(P \Rightarrow Q\) is true anyway (Definition: Implies).
When the statement is about every element of a set, as in “for every odd integer \(n\)” (Definition: Universal quantifier), the proof starts from an arbitrary element: “Suppose \(n\) is an odd integer.” Since the proof uses nothing about \(n\) except that \(n\) is odd, the same steps work for every odd integer.
Exercise 4 (Divisors of divisors) Let \(a\), \(b\) and \(c\) be integers. Prove that if \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
Solution 4. Suppose \(a \mid b\) and \(b \mid c\). By Definition 9, \(b = a j\) and \(c = b k\) for some integers \(j\) and \(k\). Then \[ c = b k = (a j) k = a (j k). \] Since \(j k\) is an integer (Remark 3), \(a \mid c\), by Definition 9.
Exercise 5 (Even for every integer) Prove that \(n^2 + n\) is even for every integer \(n\).
Hint
Every integer is even or odd (Remark 3). Handle the two kinds separately.
Solution 5. Let \(n\) be an integer. Every integer is even or odd (Remark 3), so one of these cases holds.
Case 1: \(n\) is even. By Definition 7, \(n = 2 k\) for some integer \(k\), and \[ n^2 + n = (2 k)^2 + 2 k = 4 k^2 + 2 k = 2 (2 k^2 + k). \]
Case 2: \(n\) is odd. By Definition 8, \(n = 2 k + 1\) for some integer \(k\), and \[ n^2 + n = (2 k + 1)^2 + (2 k + 1) = (4 k^2 + 4 k + 1) + (2 k + 1) = 4 k^2 + 6 k + 2 = 2 (2 k^2 + 3 k + 1). \]
In each case, \(n^2 + n\) is \(2\) times an integer (Remark 3), so \(n^2 + n\) is even, by Definition 7.
Definition 12 (Proof by cases) A proof by cases splits the situation into cases that together cover every possibility, and proves the conclusion separately in each case.
Example 9 (Two cases) Solution 5 is a proof by cases (Definition 12): every integer is even or odd (Remark 3), so its two cases cover every integer \(n\).
Exercise 6 (Larger plus smaller) For real numbers \(x\) and \(y\), let \(\max(x, y)\) be the larger of \(x\) and \(y\) and \(\min(x, y)\) the smaller (both equal \(x\) when \(x = y\)). Prove that \(\max(x, y) + \min(x, y) = x + y\).
Solution 6. Let \(x\) and \(y\) be real numbers. Either \(x \le y\) or \(y \le x\). Both sides of the equation stay the same when \(x\) and \(y\) are swapped, so without loss of generality, suppose \(x \le y\). Then \(\max(x, y) = y\) and \(\min(x, y) = x\), so \[ \max(x, y) + \min(x, y) = y + x = x + y. \]
Remark 7 (Without loss of generality). Solution 6 is a proof by cases (Definition 12) with two cases, \(x \le y\) and \(y \le x\). The proof of the second case is the proof of the first with the names \(x\) and \(y\) swapped, which changes neither side of the equation. “Without loss of generality, suppose \(x \le y\)” says this, and writes out only the first case. Use it only when the other cases really are the same proof with names changed.