Last modified: 2026-11-06 15:35:15 (PST)
This page collects general advice on how to write proofs and derivations. The goal of a proof is not just to convince yourself that a result is true; it is to convince a reader, and to show them why it is true. Each principle on this page serves that goal. The symbols for logical entailment are listed under Definitions for proofs below.
Definition 1 (Proposition, statement) A proposition, or statement, is a declarative sentence that is either true or false (Wikipedia contributors 2026z).
Example 1 (Propositions, and a sentence that is not one)
Definition 2 (Predicate) A predicate (Wikipedia contributors 2026w) \(P(x)\) is a declarative sentence about a variable \(x\) that becomes a proposition (Definition 1) whenever a value is substituted for \(x\).
Example 2 (A predicate) Let \(P(x)\) be the predicate “\(x > 2\)”, for real numbers \(x\).
Example 3 (The domain changes the truth value)
Let \(P(x)\) be the predicate “\(x^2 = 2\)”. If its domain of discourse is the real numbers, then \(P(x)\) is true for \(x = \sqrt{2}\). If its domain of discourse is the integers, then \(P(x)\) is false for every \(x\), since the squares of the integers are \(0, 1, 4, 9, \ldots\), and none of them is \(2\).
Definition 4 (Logical connective) A logical connective (Wikipedia contributors 2026n) builds a new proposition (Definition 1) from one or two propositions \(P\) and \(Q\), with a truth value that depends only on the truth values of \(P\) and \(Q\). These notes use five, each defined next: not, and, or, implies, and if and only if.
Definition 5 (Not) The logical connective (Definition 4) not (Wikipedia contributors 2026v) is written \(\neg P\) (“not \(P\)”); it is true when \(P\) is false, and false when \(P\) is true.
Example 4 (Negating a true and a false proposition) Let \(P\) be “\(5 > 3\)”, which is true, and let \(Q\) be “\(2 > 3\)”, which is false.
Definition 6 (And) The logical connective (Definition 4) and is written (Wikipedia contributors 2026m) \(P \land Q\) (“\(P\) and \(Q\)”); it is true when \(P\) and \(Q\) are both true, and false otherwise.
Example 5 (Two propositions joined by “and”) Let \(P\) be “\(3 < 5\)”, which is true, let \(Q\) be “\(5 < 4\)”, which is false, and let \(R\) be “\(5 < 7\)”, which is true.
Definition 7 (Or) The logical connective (Definition 4) or is written (Wikipedia contributors 2026p) \(P \lor Q\) (“\(P\) or \(Q\)”); it is true when at least one of \(P\) and \(Q\) is true, and false when both are false.
Example 6 (Two propositions joined by “or”) Let \(P\) be “\(3 < 2\)”, which is false, let \(Q\) be “\(5 < 7\)”, which is true, and let \(R\) be “\(5 < 4\)”, which is false.
Definition 8 (Implies) The logical connective (Definition 4) implies is written (Wikipedia contributors 2026r) \(P \Rightarrow Q\) (“if \(P\), then \(Q\)”, or “\(P\) implies \(Q\)”); it is false when \(P\) is true and \(Q\) is false, and true otherwise.
Example 7 (Implications with a true and a false premise) Take \(x = 3\).
Definition 9 (If and only if) The logical connective (Definition 4) if and only if is written (Wikipedia contributors 2026l) \(P \Leftrightarrow Q\) (“\(P\) if and only if \(Q\)”); it is true when \(P\) and \(Q\) have the same truth value, and false otherwise.
Example 8 (“If and only if” with equal and different truth values) Take \(x = 4\).
Example 9 (Truth values of connectives) Let \(P\) be “\(2 + 3 = 5\)”, which is true, and let \(Q\) be “\(7\) is even”, which is false.
Definition 10 (Truth table) A truth table (Wikipedia contributors 2026ad) for a proposition built from propositions \(P_1, \ldots, P_n\) with logical connectives has one row for each of the \(2^n\) combinations of truth values of \(P_1, \ldots, P_n\), and gives the truth value of the proposition in each row.
Example 10 (A truth table for \(P \Rightarrow Q\)) The proposition \(P \Rightarrow Q\) is built from two propositions, so its truth table has \(2^2 = 4\) rows. By the definition of implies, \(P \Rightarrow Q\) is false only in the row where \(P\) is true and \(Q\) is false:
| \(P\) | \(Q\) | \(P \Rightarrow Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Definition 11 (Logically equivalent) Two propositions \(A\) and \(B\), each built from some or all of the propositions \(P_1, \ldots, P_n\) with logical connectives, are logically equivalent (Wikipedia contributors 2026q), written \(A \equiv B\), when they have the same truth value in every row of a truth table on \(P_1, \ldots, P_n\).
Example 11 (\(P \Rightarrow Q\) is logically equivalent to \(\neg P \lor Q\)) Adding a column for \(\neg P \lor Q\) to the truth table of Example 10 gives:
| \(P\) | \(Q\) | \(\neg P\) | \(\neg P \lor Q\) | \(P \Rightarrow Q\) |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
The last two columns agree in every row, so \((P \Rightarrow Q) \equiv (\neg P \lor Q)\).
Theorem 1 (A biconditional is two conditionals) For propositions \(P\) and \(Q\),
\[ (P \Leftrightarrow Q) \equiv \mathopen{}\left((P \Rightarrow Q) \land (Q \Rightarrow P)\right)\mathclose{}. \]
Example 12 (Proving an “if and only if” in two parts)
Let \(n\) be an integer. By a biconditional is two conditionals, to prove “\(n\) is even if and only if \(n + 2\) is even”, it is enough to prove both conditionals:
Theorem 2 (A cycle of conditionals) Let \(P_1, P_2, \ldots, P_k\) be propositions. If \(P_1 \Rightarrow P_2\), \(P_2 \Rightarrow P_3\), \(\ldots\), \(P_{k-1} \Rightarrow P_k\) and \(P_k \Rightarrow P_1\) are all true, then \(P_1, \ldots, P_k\) all have the same truth value.
Example 13 (Three equivalent statements)
Let \(n\) be an integer, and let:
If \(n = 2m\), then \(n + 1 = 2m + 1\), so \(P_1 \Rightarrow P_2\). If \(n + 1 = 2m + 1\), then \(n + 2 = 2(m + 1)\), so \(P_2 \Rightarrow P_3\). If \(n + 2 = 2m\), then \(n = 2(m - 1)\), so \(P_3 \Rightarrow P_1\). By a cycle of conditionals, the three propositions are all true or all false. Three conditionals were enough, where checking each pair both ways would take six.
Theorem 3 (De Morgan’s laws for propositions) For any propositions \(P\) and \(Q\) (Wikipedia contributors 2026f):
\[ \begin{aligned} \neg (P \land Q) &\equiv \neg P \lor \neg Q \\ \neg (P \lor Q) &\equiv \neg P \land \neg Q \end{aligned} \]
Definition 12 (Tautology) A tautology is a proposition that is true in every row of its truth table.
Example 14 (\(P \lor \neg P\) is a tautology)
By the definitions of or and not, the truth table of \(P \lor \neg P\) is:
| \(P\) | \(\neg P\) | \(P \lor \neg P\) |
|---|---|---|
| T | F | T |
| F | T | T |
The last column is true in every row, so \(P \lor \neg P\) is a tautology.
Definition 13 (Contradiction) A contradiction is a proposition that is false in every row of its truth table.
Example 15 (\(P \land \neg P\) is a contradiction)
By the definitions of and and not, the truth table of \(P \land \neg P\) is:
| \(P\) | \(\neg P\) | \(P \land \neg P\) |
|---|---|---|
| T | F | F |
| F | T | F |
The last column is false in every row, so \(P \land \neg P\) is a contradiction.
Theorem 4 (Equivalence is a tautological biconditional) For propositions \(A\) and \(B\), \(A\) and \(B\) are logically equivalent exactly when \(A \Leftrightarrow B\) is a tautology.
Example 16 (A tautological biconditional)
Example 11 showed that \(P \Rightarrow Q\) and \(\neg P \lor Q\) are logically equivalent. Adding a column for the biconditional to its truth table gives:
| \(P\) | \(Q\) | \(\neg P \lor Q\) | \(P \Rightarrow Q\) | \((P \Rightarrow Q) \Leftrightarrow (\neg P \lor Q)\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | T | T |
| F | F | T | T | T |
The last column is true in every row, so the biconditional is a tautology, as equivalence as a tautological biconditional says it must be.
Theorem 5 (Double negation) For a proposition \(P\),
\[ \neg \neg P \equiv P. \]
Example 17 (Removing a double negation)
Let \(P\) be the proposition “\(7\) is odd”. Then \(\neg \neg P\) is “it is not the case that \(7\) is not odd”. By double negation, \(\neg \neg P\) says the same thing as \(P\): \(7\) is odd.
Definition 14 (Quantifier) A quantifier (Wikipedia contributors 2026ab) turns a predicate \(P(x)\) (Definition 2) about the elements \(x\) of a set \(S\) into a proposition (Definition 1). There are two, each defined next: the universal quantifier and the existential quantifier.
Definition 15 (Universal quantifier) The universal quantifier (Wikipedia contributors 2026ae) “for all” is a quantifier (Definition 14): \(\forall x \in S, P(x)\) (“for every \(x\) in \(S\), \(P(x)\)”) is true when \(P(x)\) is true for every element \(x\) of \(S\), and false otherwise.
Example 18 (A universally quantified proposition) Let \(P(x)\) be the predicate “\(x\) is even”.
Definition 16 (Existential quantifier) The existential quantifier (Wikipedia contributors 2026h) “there exists” is a quantifier (Definition 14): \(\exists x \in S, P(x)\) (“there is an \(x\) in \(S\) such that \(P(x)\)”) is true when \(P(x)\) is true for at least one element \(x\) of \(S\), and false otherwise.
Example 19 (An existentially quantified proposition) Let \(P(x)\) be the predicate “\(x\) is even”.
Example 20 (Quantified propositions) Let \(P(x)\) be the predicate “\(x > 2\)”, for integers \(x\).
Theorem 6 (De Morgan’s laws for quantifiers) For a set \(S\) and a predicate \(P(x)\) whose domain of discourse is \(S\):
\[ \begin{aligned} \neg (\forall x \in S, P(x)) &\equiv \exists x \in S, \neg P(x) \\ \neg (\exists x \in S, P(x)) &\equiv \forall x \in S, \neg P(x) \end{aligned} \]
Remark 1 (Why the two laws share a theorem). The two laws in De Morgan’s laws for quantifiers are one rule seen from each side: negating a quantifier swaps \(\forall\) and \(\exists\) and moves the negation onto the predicate. De Morgan’s laws for propositions pair their two laws the same way, and these laws extend them from two propositions to a whole set of them.
Example 21 (Negating “every integer is even”)
Let \(S\) be the integers, and let \(P(x)\) be “\(x\) is even”. By the first of De Morgan’s laws for quantifiers, \(\neg (\forall x \in S, P(x)) \equiv \exists x \in S, \neg P(x)\): the negation of “every integer is even” is “some integer is not even”. By the second law, \(\neg (\exists x \in S, P(x)) \equiv \forall x \in S, \neg P(x)\): the negation of “some integer is even” is “no integer is even”.
Definition 17 (Inequality) An inequality is a proposition (Definition 1) or a predicate (Definition 2) that compares two expressions \(a\) and \(b\) whose values are real numbers, in one of the forms:
Example 22 (Inequalities)
Definition 18 (Logical entailment, logical consequence, deductive consequence) Propositions or predicates \(P_1, \ldots, P_n\) (Definition 1, Definition 2) logically entail (Wikipedia contributors 2026o) 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 23 (Entailment, and its failure) Let \(x\) be an integer.
We can use any of:
\therefore in LaTeX),\Rightarrow),\models)to denote logical entailment. \(\Rightarrow\) also writes the connective “implies”; \(P\) entails \(Q\) exactly when \(P \Rightarrow Q\) is true for every choice of values for the variables in \(P\) and \(Q\).
Let’s save \(\rightarrow\) (\rightarrow) for convergence results.
Definition 19 (Logical argument) A logical argument is a list of propositions \(P_1, \ldots, P_n\) together with one more proposition \(Q\). It is written with “so” or \(\therefore\) before \(Q\).
Definition 20 (Premise) The premises of a logical argument \(P_1, \ldots, P_n \therefore Q\) are the propositions \(P_1, \ldots, P_n\).
Definition 21 (Conclusion) The conclusion of a logical argument \(P_1, \ldots, P_n \therefore Q\) is the proposition \(Q\).
Example 24 (A logical argument)
“If \(n\) is even, then \(n^2\) is even. \(n\) is even. So \(n^2\) is even.” is a logical argument. Its premises are “if \(n\) is even, then \(n^2\) is even” and “\(n\) is even”. Its conclusion is “\(n^2\) is even”.
Definition 22 (Rule of inference) A rule of inference is a pattern of logical argument, written with propositions \(P, Q, \ldots\) as placeholders, whose premises logically entail its conclusion 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 25 (A pattern that is not a rule of inference)
The pattern
\[ \frac{P \Rightarrow Q, \quad Q}{P} \]
is not a rule of inference. In the row of the truth table where \(P\) is false and \(Q\) is true, both premises are true, by the definition of implies, but the conclusion \(P\) is false. For example, “if \(n = 2\), then \(n\) is even” and “\(n\) is even” are both true for \(n = 4\), but “\(n = 2\)” is false.
Theorem 7 (Modus ponens) For propositions \(P\) and \(Q\), this is a rule of inference:
\[ \frac{P \Rightarrow Q, \quad P}{Q} \]
Proof. By the definition of implies, \(P \Rightarrow Q\) is false only when \(P\) is true and \(Q\) is false. Both premises are true, so \(P\) is true and \(P \Rightarrow Q\) is true. So \(Q\) is not false, and the conclusion \(Q\) is true.
Theorem 8 (Modus tollens) For propositions \(P\) and \(Q\), this is a rule of inference:
\[ \frac{P \Rightarrow Q, \quad \neg Q}{\neg P} \]
Proof. Suppose both premises are true. By the definition of not, \(Q\) is false. By the definition of implies, a true \(P \Rightarrow Q\) with a false \(Q\) needs a false \(P\). So \(P\) is false, and the conclusion \(\neg P\) is true.
Theorem 9 (Disjunctive syllogism) For propositions \(P\) and \(Q\), this is a rule of inference:
\[ \frac{P \lor Q, \quad \neg P}{Q} \]
Proof. Suppose both premises are true. By the definition of not, \(P\) is false. By the definition of or, \(P \lor Q\) is true only if \(P\) is true or \(Q\) is true. So the conclusion \(Q\) is true.
Theorem 10 (Addition) For propositions \(P\) and \(Q\), this is a rule of inference:
\[ \frac{P}{P \lor Q} \]
Proof. Suppose the premise is true. By the definition of or, \(P \lor Q\) is true when \(P\) is true. So the conclusion \(P \lor Q\) is true.
Theorem 11 (Simplification) For propositions \(P\) and \(Q\), this is a rule of inference:
\[ \frac{P \land Q}{P} \]
Proof. Suppose the premise is true. By the definition of and, \(P \land Q\) is true only if \(P\) and \(Q\) are both true. So the conclusion \(P\) is true.
Theorem 12 (Conjunction) For propositions \(P\) and \(Q\), this is a rule of inference:
\[ \frac{P, \quad Q}{P \land Q} \]
Proof. Suppose both premises are true. By the definition of and, \(P \land Q\) is true when \(P\) and \(Q\) are both true. So the conclusion \(P \land Q\) is true.
Example 26 (Chaining rules of inference)
Suppose these three premises are true:
By modus tollens on the second and third premises, “the game is not cancelled” is true. By modus tollens again, on the first premise and the fact derived from them, “it does not rain” is true. So the conclusion “it does not rain” follows from the premises.
Definition 23 (Proof) A proof (Wikipedia contributors 2026t) of a proposition (Definition 1) is a finite list of statements that ends with that proposition, in which each statement is
Example 27 (The sum of two even integers is even) Let \(a\) and \(b\) be even integers (definition). Then \(a = 2j\) and \(b = 2k\) for some integers \(j\) and \(k\), and
\[ \begin{aligned} a + b &= 2j + 2k && \text{(substitute } a = 2j \text{ and } b = 2k \text{)} \\ &= 2(j + k) && \text{(distributive law)} \end{aligned} \]
The second line uses the distributive law. Since \(j + k\) is an integer, \(a + b\) is even (definition). For example,
\[ \begin{aligned} 4 + 10 &= 2 \cdot 2 + 2 \cdot 5 \\ &= 2 \cdot 7 \\ &= 14. \end{aligned} \]
Definition 24 (Derivation) A derivation is a proof (Definition 23), or a part of one, written as a chain of expressions, one per line, in which each line is joined to the line before it by \(=\) or by an inequality sign (Definition 17), and carries an annotation that names the reason that step holds: an assumption, a definition, a previously proved result, or a rule of algebra.
Example 28 (A derivation with equalities and inequalities) For every real number \(x\):
\[ \begin{aligned} (x + 1)^2 &= x^2 + 2x + 1 && \text{(square of a sum)} \\ &\ge 2x + 1 && \text{(} x^2 \ge 0 \text{)} \\ &> 2x && \text{(} 1 > 0 \text{)} \end{aligned} \]
The first step uses the square of a sum. The steps are \(=\), \(\ge\), and \(>\), so the derivation shows \((x + 1)^2 > 2x\). For example, with \(x = 3\): \((3 + 1)^2 = 16\), and \(16 > 6 = 2 \cdot 3\).
Theorem 13 (What a derivation shows) Consider a derivation (Definition 24) with expressions \(E_0, E_1, \ldots, E_n\), where each line \(E_j\) is joined to the line \(E_{j-1}\) before it by \(=\), \(\le\) or \(<\).
The same holds with \(\ge\) and \(>\) in place of \(\le\) and \(<\).
Example 29 (Checking a derivation line by line) The derivation in Example 28 has the steps \(=\), \(\ge\) and \(>\), so by Theorem 13 it shows \((x + 1)^2 > 2x\). The code evaluates the four lines of that derivation at several values of \(x\), and checks each step and the comparison of the first line with the last.
x <- c(-3, -1, 0, 2, 3)
lines <- data.frame(
x = x,
line_0 = (x + 1)^2,
line_1 = x^2 + 2 * x + 1,
line_2 = 2 * x + 1,
line_3 = 2 * x
)
steps <- with(
lines,
data.frame(
x = x,
step_1_equal = line_0 == line_1,
step_2_geq = line_1 >= line_2,
step_3_greater = line_2 > line_3,
first_greater_than_last = line_0 > line_3
)
)
linesAt all 5 values of \(x\), the three steps hold in 5, 5 and 5 cases, and the first line exceeds the last in 5 cases, as Theorem 13 says. At \(x = 0\), for example, the first line is 1 and the last is 0.
Definition 25 (Result) A result is a proposition (Definition 1) that has a proof (Definition 23). These notes label each result by its role: as a theorem, a lemma, or a corollary, each defined next.
Example 30 (A proposition that is a result, and one that is not) “\(2 + 3 = 5\)” is a proposition (Definition 1) that has a proof, the computation of \(2 + 3\), so it is a result. “\(7\) is even” is a proposition that is false, so it has no proof and is not a result.
Remark 2 (“Proposition” as a kind of result). Some sources also call a result of moderate importance a “proposition”. In these notes, “proposition” always means a sentence that is true or false (Definition 1), whether or not it has been proved.
Definition 26 (Theorem) A theorem (Wikipedia contributors 2026ac) is a result (Definition 25) of interest in its own right.
Example 31 (A theorem) “The sum of two even integers is even” is a result: Example 27 proves it. It is of interest in its own right, since it applies whenever two even integers are added, as in \(2 + 4 = 6\), so it is a theorem.
Definition 27 (Lemma) A lemma (Wikipedia contributors 2026k) is a result (Definition 25) proved mainly as a step in the proof of another result.
Example 32 (A lemma in the proof of a larger result) To show that the sum of four even integers \(a\), \(b\), \(c\), and \(d\) is even, write \(a + b + c + d = (a + b) + (c + d)\). By the result of Example 27, \(a + b\) and \(c + d\) are even, and applying that result again to these two sums shows that their sum is even. Here that result is proved mainly as a step in the proof of another result, so it serves as a lemma. For example, \(2 + 4 + 6 + 8 = (2 + 4) + (6 + 8) = 6 + 14 = 20\), which is even.
Definition 28 (Corollary) A corollary (Wikipedia contributors 2026d) is a result (Definition 25) that follows from a theorem with little extra work.
Example 33 (A corollary of a result) Example 27 proves the result “the sum of two even integers is even”. A corollary follows with little extra work: the sum of three even integers \(a\), \(b\), and \(c\) is even, because \(a + b + c = (a + b) + c\), \(a + b\) is even by that result, and applying the result again to the even integers \(a + b\) and \(c\) shows that \((a + b) + c\) is even. For example,
\[ \begin{aligned} 2 + 4 + 6 &= (2 + 4) + 6 \\ &= 6 + 6 \\ &= 12, \end{aligned} \]
which is even.
Definition 29 (Counterexample) A counterexample (Wikipedia contributors 2026e) to a proposition of the form “for every \(x\) in \(A\), \(P(x)\)”, where \(P(x)\) is a predicate (Definition 2), is an element \(x\) of \(A\) for which \(P(x)\) is false. A single counterexample shows that the proposition is false.
Example 34 (A counterexample) The proposition “for every integer \(n\), \(n + n > n\)” is false. The integer \(n = 0\) is a counterexample: \(0 + 0 = 0\), and \(0 > 0\) is false. The proposition is true for some integers, such as \(n = 3\), since \(3 + 3 = 6 > 3\), but one counterexample is enough to make it false.
Definition 30 (Disproof) A disproof of a proposition \(P\) is a proof of its negation, \(\neg P\).
Definition 31 (Constructive proof) A constructive proof (Wikipedia contributors 2026a) of a proposition \(\exists x \in S,\ P(x)\) with an existential quantifier names a particular element of \(S\) and shows that \(P\) is true of it.
Remark 3 (Several existential quantifiers). A proposition can open with several existential quantifiers. A constructive proof of it names one element for each quantifier. For example, a constructive proof of “there are integers \(m\) and \(n\) with \(m + n = 1\)” names one value of \(m\) and one of \(n\).
Example 36 (A constructive proof) Claim: there are integers \(m\) and \(n\) with \(m + n = 1\).
Proof: take \(m = 0\) and \(n = 1\). Then \(m + n = 0 + 1 = 1\).
This proof is a constructive proof, since it names an integer for each of the two existential quantifiers.
Definition 32 (Non-constructive proof) A non-constructive proof (Wikipedia contributors 2026a) of a proposition \(\exists x \in S,\ P(x)\) shows that it is true without naming any element \(x\) of \(S\) for which \(P(x)\) is true. It is a proof that is not a constructive proof.
Example 37 (A non-constructive proof) Claim: among any three integers, there are two that are both even or both odd.
Proof: each integer is even or odd. If at most one of the three integers were even, and at most one were odd, there would be at most two integers in all. So at least two of the three are even, or at least two are odd.
This proof is a non-constructive proof, since it does not say which two of the integers share their parity.
Definition 33 (Converse) The converse (Wikipedia contributors 2026c) of the proposition “if \(P\), then \(Q\)” is the proposition “if \(Q\), then \(P\)”.
Example 38 (A true proposition with a false converse) For an integer \(n\), call \(n\) a multiple of \(4\) if \(n = 4k\) for some integer \(k\).
“If \(n\) is a multiple of \(4\), then \(n\) is even” is true:
\[ \begin{aligned} n &= 4k \\ &= 2 \cdot(2k), \end{aligned} \]
and \(2k\) is an integer.
Its converse, “if \(n\) is even, then \(n\) is a multiple of \(4\)”, is false. The integer \(n = 2\) is a counterexample (Definition 29): \(2\) is even, but \(2 = 4k\) only for \(k = \frac{1}{2}\), which is not an integer.
So a proposition can be true while its converse is false.
Definition 34 (Contrapositive) The contrapositive (Wikipedia contributors 2026b) of the proposition “if \(P\), then \(Q\)” is the proposition “if \(\neg Q\), then \(\neg P\)”.
Theorem 14 (A conditional is equivalent to its contrapositive) For any propositions \(P\) and \(Q\),
\[ (P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P). \]
Example 39 (The contrapositive versus the converse) The proposition “if \(n\) is a multiple of \(4\), then \(n\) is even” from Example 38 has:
Definition 35 (Sufficient condition) When the proposition “if \(P\), then \(Q\)” is true, \(P\) is a sufficient condition (Wikipedia contributors 2026u) for \(Q\).
Example 40 (A sufficient condition) For a real number \(x\), “if \(x > 5\), then \(x > 2\)” is true, because a number greater than \(5\) is greater than \(2\). So \(x > 5\) is a sufficient condition for \(x > 2\): knowing that \(x = 6\) satisfies \(x > 5\) is enough to conclude that \(6 > 2\).
Definition 36 (Necessary condition) When the proposition “if \(P\), then \(Q\)” is true, \(Q\) is a necessary condition (Wikipedia contributors 2026u) for \(P\).
Example 41 (A necessary condition) For an integer \(n\), “if \(n\) is a multiple of \(6\), then \(n\) is a multiple of \(3\)” is true, because \(6k = 3 \cdot(2k)\) for every integer \(k\). So being a multiple of \(3\) is a necessary condition for being a multiple of \(6\): \(12 = 6 \cdot 2\) is a multiple of \(6\), and it is also a multiple of \(3\), since \(12 = 3 \cdot 4\).
Definition 37 (Necessary and sufficient condition) When both “if \(P\), then \(Q\)” and its converse (Definition 33) are true, \(P\) is a necessary and sufficient condition (Wikipedia contributors 2026u) for \(Q\) (Definition 35, Definition 36), written “\(P\) if and only if \(Q\)”.
Example 42 (Necessary but not sufficient) In Example 38, “if \(n\) is a multiple of \(4\), then \(n\) is even” is true, so:
Being even is not a sufficient condition for being a multiple of \(4\): \(n = 2\) is even, but not a multiple of \(4\).
Definition 38 (Proof by contradiction) A proof by contradiction (Wikipedia contributors 2026x) of a proposition \(P\) assumes that \(P\) is false, and derives from that assumption a proposition that is known to be false.
Example 43 (No integer is both even and odd) Suppose, for contradiction, that some integer \(n\) is both even and odd (definition). Then \(n = 2j\) and \(n = 2k + 1\) for some integers \(j\) and \(k\), and
\[ \begin{aligned} 2j &= 2k + 1 && \text{(both equal } n \text{)} \\ 2j - 2k &= 1 && \text{(subtract } 2k \text{ from both sides)} \\ 2(j - k) &= 1 && \text{(distributive law)} \\ j - k &= \tfrac{1}{2} && \text{(divide both sides by } 2 \text{)} \end{aligned} \]
The third line uses the distributive law. But \(j - k\) is an integer, and \(\frac{1}{2}\) is not, so the last line is false. So no integer is both even and odd. For example, \(6 = 2 \cdot 3\) is even, and \(6 = 2k + 1\) would need \(k = 2.5\), which is not an integer.
Theorem 15 (A proof by contradiction proves its proposition) Let \(P\) and \(Q\) be propositions (Definition 1). If \(\neg P \Rightarrow Q\) is true and \(Q\) is false, then \(P\) is true.
Theorem 16 (Why a proof by contradiction works) For propositions \(P\) and \(C\),
\[ P \equiv \mathopen{}\left(\neg P \Rightarrow (C \land \neg C)\right)\mathclose{}. \]
Example 44 (A truth table for a proof by contradiction) There are only four ways to assign truth values to \(P\) and \(Q\). The code lists them, with the truth value of \(\neg P \Rightarrow Q\), and marks the rows where \(\neg P \Rightarrow Q\) is true and \(Q\) is false.
The hypotheses of Theorem 15 hold in 1 of the 4 rows, and in 1 of them \(P\) is true. So whenever the hypotheses hold, \(P\) is true.
Show every step of the derivation. Each line should follow from the previous line by a single, identifiable move:
When you skip steps, you force the reader to reconstruct your reasoning, which is exactly the work the proof was supposed to do for them. A step that feels “obvious” while you are writing it is often the step a reader gets stuck on. Phrases like “it can be shown that” or “clearly” usually mark a skipped step; show the step instead.
For each step, note the definition, theorem, or algebraic rule that justifies it. A brief annotation to the right of the line is usually enough. Annotations make the proof checkable, and they teach the reader which tool to reach for next time.
For example, here is a derivation that the hat matrix \(\mathbf{H} = \mathbf{X}({\mathbf{X}}^{\top}\mathbf{X})^{-1}{\mathbf{X}}^{\top}\) is idempotent, \(\mathbf{H}^2 = \mathbf{H}\), with each step annotated:
\[ \begin{aligned} \mathbf{H}^2 &= \mathbf{H}\mathbf{H} && \text{(definition of a matrix power)} \\ &= \mathbf{X}({\mathbf{X}}^{\top}\mathbf{X})^{-1}{\mathbf{X}}^{\top}\,\mathbf{X}({\mathbf{X}}^{\top}\mathbf{X})^{-1}{\mathbf{X}}^{\top} && \text{(definition of } \mathbf{H} \text{)} \\ &= \mathbf{X}({\mathbf{X}}^{\top}\mathbf{X})^{-1}({\mathbf{X}}^{\top}\mathbf{X})({\mathbf{X}}^{\top}\mathbf{X})^{-1}{\mathbf{X}}^{\top} && \text{(regroup; matrix multiplication is associative)} \\ &= \mathbf{X}\,\mathbf{I}_p\,({\mathbf{X}}^{\top}\mathbf{X})^{-1}{\mathbf{X}}^{\top} && \text{(a matrix inverse times the matrix is } \mathbf{I}_p \text{)} \\ &= \mathbf{X}({\mathbf{X}}^{\top}\mathbf{X})^{-1}{\mathbf{X}}^{\top} && \text{(the identity matrix changes nothing)} \\ &= \mathbf{H} && \text{(definition of } \mathbf{H} \text{)} \end{aligned} \]
The Linear Algebra page uses this derivation to show that \(\mathbf{H}\) is a projection matrix. The probability notes derive the variance identity \({\operatorname{Var}\mathopen{}\left(X\right)\mathclose{}} = {\mathbb{E}\mathopen{}\left[X^2\right]\mathclose{}} - {\mathopen{}\left({\mathbb{E}\mathopen{}\left[X\right]\mathclose{}}\right)\mathclose{}}^{2}\) in the same annotated style.
Definition 39 (Direct proof) A direct proof (Wikipedia contributors 2026g) of a proposition \(Q\) starts from the assumptions that \(Q\) is stated under, if any, and reaches \(Q\) through a chain of steps, each of which applies a definition, a previously proved result, or one rule of logic or algebra to the assumptions or to earlier steps. A direct proof never assumes that \(Q\) is false; compare proof by contradiction, which does.
Example 45 (The square of an odd integer is odd) Claim: if \(n\) is an odd integer, then \(n^2\) is odd.
Since \(n\) is odd, there is an integer \(k\) with \(n = 2k + 1\). Then
\[ \begin{aligned} n^2 &= (2k + 1)^2 && \text{(substitute } n = 2k + 1 \text{)} \\&= (2k)^2 + 2 \cdot 2k \cdot 1 + 1^2 && \text{(square of a sum)} \\&= 4k^2 + 4k + 1 && \text{(arithmetic)} \\&= 2(2k^2 + 2k) + 1 && \text{(distributive law, read from right to left)} \end{aligned} \]
and \(2k^2 + 2k\) is an integer, because adding or multiplying integers gives an integer. So \(n^2 = 2 \cdot(\text{an integer}) + 1\), which is the definition of odd. For example,
\[ \begin{aligned} n &= 7 \\ &= 2 \cdot 3 + 1 \end{aligned} \]
gives
\[ \begin{aligned} n^2 &= 49 \\ &= 2 \cdot 24 + 1, \end{aligned} \]
and \(2 \cdot 3^2 + 2 \cdot 3 = 24\).
The proof above that the sum of two even integers is even is also a direct proof.
Definition 40 (Proof by contrapositive) A proof by contrapositive (Wikipedia contributors 2026b) of a proposition “if \(P\), then \(Q\)” is a direct proof of its contrapositive, “if \(\neg Q\), then \(\neg P\)”: it assumes that \(Q\) is false and reaches the conclusion that \(P\) is false. By Theorem 14, proving the contrapositive proves the original proposition.
Example 46 (If \(x^2 + 3x < 0\), then \(x < 0\)) Claim: for every real number \(x\), if \(x^2 + 3x < 0\), then \(x < 0\).
A direct proof would have to start from the inequality \(x^2 + 3x < 0\), which says little about \(x\) on its own. The contrapositive (Definition 34) is “if \(x \ge 0\), then \(x^2 + 3x \ge 0\)”, and its assumption is easier to use.
Suppose \(x \ge 0\). Then \(x^2 = x \cdot x \ge 0\), because a product of two nonnegative numbers is nonnegative, and \(3x \ge 0\), because \(3 > 0\) and \(x \ge 0\). So
\[ \begin{aligned} x^2 + 3x &\ge 0 + 0 && \text{(add the inequalities } x^2 \ge 0 \text{ and } 3x \ge 0 \text{)} \\&= 0. && \text{(arithmetic)} \end{aligned} \]
That proves the contrapositive, so by Theorem 14 the claim holds. For example, \(x = -1\) gives \(x^2 + 3x = 1 - 3 = -2 < 0\), and indeed \(x < 0\).
Definition 41 (Proof by cases, proof by exhaustion) A proof by cases (Wikipedia contributors 2026y), also called a proof by exhaustion, of a proposition \(Q\) lists propositions \(C_1, \ldots, C_k\), the cases, shows that at least one of them is true, and proves \(C_i \Rightarrow Q\) for each \(i\).
Example 47 (The square of a real number is nonnegative) Claim: for every real number \(x\), \(x^2 \ge 0\).
Every real number \(x\) satisfies \(x \ge 0\) or \(x < 0\), so these two cases cover every \(x\).
Case 1: \(x \ge 0\). Then \(x^2 = x \cdot x\) is a product of two nonnegative numbers, so \(x^2 \ge 0\).
Case 2: \(x < 0\). Then \(-x > 0\), and
\[ \begin{aligned} x^2 &= x \cdot x && \text{(definition of } x^2 \text{)} \\&= (-x) \cdot(-x) && \text{(the two minus signs cancel)} \end{aligned} \]
is a product of two positive numbers, so \(x^2 > 0\), and in particular \(x^2 \ge 0\).
The claim holds in both cases, so it holds for every real number \(x\).
In general, follow the golden rule: treat your readers the way you want to be treated as a reader.
When you read someone else’s proof, you want to be able to follow every step without guessing, to know which result is being used at each line, and to never be left wondering where a quantity came from. Write your own proofs to meet that same standard.
Many proofs in these notes show that a statement holds for every natural number \(n\), or for every integer \(n\) from some starting value on. Checking the statement one \(n\) at a time would never finish; induction proves it for all of them with two arguments.
Definition 42 (Proof by induction) Let \(n_0\) be an integer, and let \(P(n)\) be a predicate about the integers \(n \ge n_0\). A proof by induction (Wikipedia contributors 2026s) on \(n\) shows that \(P(n)\) holds for every integer \(n \ge n_0\) by showing two things:
In the inductive step, the assumption that \(P(n - 1)\) holds is called the induction hypothesis.
Remark 4 (Why the two steps suffice). The base case gives \(P(n_0)\). The inductive step with \(n = n_0 + 1\) then gives \(P(n_0 + 1)\), with \(n = n_0 + 2\) it gives \(P(n_0 + 2)\), and so on: each integer \(n \ge n_0\) is reached after \(n - n_0\) uses of the inductive step.
When \(P(n)\) is needed only for \(n_0 \le n \le r\), it is enough to show the inductive step for \(n_0 < n \le r\); the same chain then stops at \(P(r)\).
The following example uses summation notation.
Example 48 (Sum of the first \(n\) natural numbers) For every \(n \in \mathbb{N}\),
\[ \sum_{i=1}^ni = \frac{n(n+1)}{2}. \]
For example, with \(n = 3\), \(1 + 2 + 3 = 6\) and \(\frac{3 \cdot 4}{2} = 6\). To prove the equation for every \(n\), let \(P(n)\) be the equation and use Definition 42 with \(n_0 = 1\).
Base case, \(n = 1\). The sum has one term:
\[ \begin{aligned} \sum_{i=1}^{1} i &= 1 && \text{(definition of a sum)} \end{aligned} \]
and the right side is
\[ \begin{aligned} \frac{1\,(1+1)}{2} &= \frac{1 \cdot 2}{2} && \text{(} 1 + 1 = 2 \text{)} \\ &= \frac{2}{2} && \text{(} 1 \cdot 2 = 2 \text{)} \\ &= 1. && \text{(} \tfrac{2}{2} = 1 \text{)} \end{aligned} \]
So \(P(1)\) holds.
Inductive step. Let \(n \ge 2\), and suppose \(P(n - 1)\) holds:
\[ \sum_{i=1}^{n-1} i = \frac{(n-1)\,\mathopen{}\left((n-1)+1\right)\mathclose{}}{2}. \]
Then
\[ \begin{aligned} \sum_{i=1}^ni &= 1 + 2 + \cdots + (n-1) + n && \text{(definition of a sum)} \\ &= \mathopen{}\left(1 + 2 + \cdots + (n-1)\right)\mathclose{} + n && \text{(associative law)} \\ &= \sum_{i=1}^{n-1} i + n && \text{(definition of a sum)} \\ &= \frac{(n-1)\,\mathopen{}\left((n-1)+1\right)\mathclose{}}{2} + n && \text{(induction hypothesis)} \\ &= \frac{(n-1)\,n}{2} + n && \text{(} (n-1) + 1 = n \text{)} \\ &= \frac{(n-1)\,n}{2} + \frac{2n}{2} && \text{(} n = \tfrac{2n}{2} \text{)} \\ &= \frac{(n-1)\,n + 2n}{2} && \text{(common denominator)} \\ &= \frac{\mathopen{}\left((n-1) + 2\right)\mathclose{}\,n}{2} && \text{(distributive law)} \\ &= \frac{(n+1)\,n}{2} && \text{(} (n-1) + 2 = n + 1 \text{)} \\ &= \frac{n(n+1)}{2}, && \text{(commutative law)} \end{aligned} \]
which is \(P(n)\). By Definition 42, the equation holds for every \(n \in \mathbb{N}\).
Definition 43 (Propositional logic) Propositional logic (Wikipedia contributors 2026aa) is the study of logical entailment among propositions built from basic propositions \(P, Q, R, \ldots\) using only the logical connectives. Whether such propositions entail one another depends only on the truth values of the basic propositions, not on what the basic propositions say.
Example 49 (\(P\) and \(P \Rightarrow Q\) entail \(Q\)) Suppose \(P\) is true and \(P \Rightarrow Q\) is true. If \(Q\) were false, then \(P \Rightarrow Q\) would have a true \(P\) and a false \(Q\), so \(P \Rightarrow Q\) would be false, which contradicts the assumption. So \(Q\) is true. This holds whatever \(P\) and \(Q\) say, so \(P\) and \(P \Rightarrow Q\) logically entail \(Q\).
Definition 44 (First-order logic) First-order logic (Wikipedia contributors 2026i) extends propositional logic (Definition 43) by also allowing:
Example 50 (From “for all” to one element) Let \(P(x)\) be a predicate about the elements of a set \(S\), and let \(a \in S\). The propositions \(\forall x \in S, P(x)\) and \(a \in S\) logically entail \(P(a)\): if \(P(x)\) is true for every element \(x\) of \(S\), then it is true for the element \(a\). For example, \(\forall x \in \mathbb{Z}, x^2 \ge 0\) entails \(3^2 \ge 0\). Propositional logic alone cannot express this entailment, because it has no way to refer to the elements of \(S\).
Definition 45 (Formal proof) A formal proof (Wikipedia contributors 2026j) is a proof written in propositional logic (Definition 43) or first-order logic (Definition 44) in which each step is an assumption or follows from earlier steps by one rule taken from a fixed list of allowed rules, so that checking the proof needs no understanding of what its propositions say.
Example 51 (A three-step formal proof) Suppose the allowed rules include “from \(P\) and \(P \Rightarrow Q\), conclude \(Q\)”. Then this is a formal proof of \(Q\) from the assumptions \(P\) and \(P \Rightarrow Q\):
Free course materials on formal logic: