23/03/2026

#EECS#Python#Intro

← Back to MCEA: Mathematical Thinking and Python

Video

Lesson assets

alternate video

Alternate video: freeCodeCamp Python basics

A longer outside walkthrough if you want the same foundations taught with a different pacing and style.

recitation

Lesson 3 Recitation

homework

Lesson 3 Homework

Proofs

Valid Arguments and Inference Rules

In Lesson 1, we built a proof system for propositional equivalences: given axioms such as De Morgan’s Laws and the Conditional axiom, we showed that two expressions can be rewritten as one another through a chain of equivalence steps. But equivalence proofs are symmetric. They establish that $p \equiv q$ , meaning $p$ and $q$ carry identical truth values under every assignment. Much of mathematics proceeds asymmetrically. We know certain facts and wish to derive new ones, in one direction only. If $p \to q$ is known and $p$ is true, we may conclude $q$ , but not the reverse. The tools for this one-way reasoning are called inference rules, and a proof is a structured chain of such inferences leading from premises to a conclusion.

Arguments and Validity

Definition 45 (Argument)

An argument in propositional logic is a finite sequence of propositions $p_1, p_2, \ldots, p_n, q$ . The propositions $p_1, \ldots, p_n$ are the premises and $q$ is the conclusion. The argument is valid if the truth of all premises guarantees the truth of the conclusion:

(p_1 \land p_2 \land \cdots \land p_n) \to q \quad \text{is a tautology.}

An argument that is not valid is invalid.

We write a valid argument with the premises above a horizontal line and the conclusion below:

\frac{p_1 \quad p_2 \quad \cdots \quad p_n}{q}

An inference rule is an argument form that remains valid regardless of which particular propositions are substituted for its variables. Just as the axioms of Lesson 1 gave us equivalences that hold universally, inference rules give us one-directional deductions that hold universally.

Remark (The Turnstile)

The notation $p_1, p_2, \ldots, p_n \vdash q$ (read ” $p_1, \ldots, p_n$ entail $q$ ”) means that $q$ can be derived from the premises $p_1, \ldots, p_n$ using axioms, inference rules, and previously established theorems. When no premises are needed, we write $\vdash q$ , meaning $q$ is derivable from the axioms alone.

Why not simply check validity by truth table? If an argument involves $k$ distinct propositional variables, the truth table has $2^k$ rows. An argument with twenty premises could demand over a million rows. Inference rules allow us to verify validity in a handful of steps, regardless of the number of variables.

Modus Ponens

The cornerstone of deductive reasoning is Modus Ponens (from the Latin modus ponendo ponens, “the method of affirming by affirming”):

\frac{p \to q \quad p}{q}

If we know $p \to q$ and $p$ , we may conclude $q$ . Its validity rests on the tautology

((p \to q) \land p) \to q

To see why this is a tautology, suppose both $p \to q$ and $p$ are true. By the truth table of the conditional (Lesson 1), the only circumstance under which $p \to q$ is true and $p$ is true is when $q$ is also true. Hence $q$ must hold.

Example 42

In Lesson 3, we established the universal statement “every prime greater than $2$ is odd.” Let $p$ denote “7 is prime and greater than 2” and $q$ denote “7 is odd.” The universal claim gives $p \to q$ , and we can verify $p$ directly (7 is prime, and $7 > 2$ ). Modus Ponens yields $q$ : the integer 7 is odd.

Problem 56

Let $p$ denote “it is snowing” and $q$ denote “the lecture is cancelled.” Suppose we know $p \to q$ and $p$ . State the conclusion and identify the inference rule. Now suppose instead we know $p \to q$ and $q$ . Can we conclude $p$ ? Justify your answer using the truth table of the conditional.

Modus Tollens

Theorem 12 (Modus Tollens)

For any propositions $p$ and $q$ ,

\frac{p \to q \quad \neg q}{\neg p}

Proof

Assume $p \to q$ and $\neg q$ . By the Contrapositive equivalence (Lesson 1), $p \to q \equiv \neg q \to \neg p$ . Since $\neg q$ is true, Modus Ponens applied to $\neg q \to \neg p$ and $\neg q$ yields $\neg p$ .

■

The Latin name modus tollendo tollens (“the method of denying by denying”) captures the reasoning: if the consequence of an implication fails, its premise must also fail.

Example 43

If $n$ is even, then $n^2$ is even. We observe that $49$ is not even ( $49 = 2 \cdot 24 + 1$ ). By Modus Tollens, 7 is not even.

Hypothetical Syllogism

Theorem 13 (Hypothetical Syllogism)

For any propositions $p$ , $q$ , $r$ ,

\frac{p \to q \quad q \to r}{p \to r}

Proof

Assume $p \to q$ and $q \to r$ . We wish to show $p \to r$ . Assume $p$ . From $p$ and $p \to q$ , Modus Ponens gives $q$ . From $q$ and $q \to r$ , a second application of Modus Ponens gives $r$ . Since assuming $p$ led to $r$ , we conclude $p \to r$ .

■

This inference is also called the chain rule or the transitivity of implication. Every multi-step mathematical deduction is, at its core, a sequence of hypothetical syllogisms. For instance, suppose we know “if $n$ is divisible by $4$ , then $n$ is even” and “if $n$ is even, then $n^2$ is even.” Hypothetical Syllogism yields: “if $n$ is divisible by $4$ , then $n^2$ is even.”

Implication Elimination

Theorem 14 (Implication Elimination)

For any propositions $p$ and $q$ , $(p \to q) \vdash (p \vdash q)$ .

Proof

Assume $p \to q$ . We must show $p \vdash q$ . Assume $p$ . From $p \to q$ and $p$ , Modus Ponens yields $q$ . Thus $p \vdash q$ .

■

This gives one direction of the link between a conditional and a derivation: if $p \to q$ is known, then from the assumption $p$ one may derive $q$ . The reverse direction will appear later in Direct Proof, where we show that if assuming $p$ leads to $q$ , then the conditional $p \to q$ is established. Together, the two directions show how the turnstile and the conditional correspond: $p \vdash q$ if and only if $\vdash p \to q$ .

Further Propositional Inference Rules

Several additional inference rules arise from tautologies. Each is stated with its justifying tautology.

Conjunction. From two established truths, their conjunction follows.

\frac{p \quad q}{p \land q} \qquad \text{Tautology: } (p \land q) \to (p \land q)

The tautological justification is immediate, but Conjunction can also be derived from Modus Ponens alone via reductio.

Proof

Assume $p$ and $q$ . Suppose for contradiction that $\neg(p \land q)$ . By De Morgan’s Law (Theorem 6, Lesson 1), $\neg(p \land q) \equiv \neg p \lor \neg q$ . By the Conditional axiom (Lesson 1), $\neg p \lor \neg q \equiv p \to \neg q$ . Since $p$ holds, Modus Ponens yields $\neg q$ . But $q$ is assumed, a contradiction. Therefore $p \land q$ .

■

Simplification. From a conjunction, either conjunct may be extracted.

\frac{p \land q}{p} \qquad \text{Tautology: } (p \land q) \to p

Addition. A known truth may be weakened to a disjunction.

\frac{p}{p \lor q} \qquad \text{Tautology: } p \to (p \lor q)

Disjunctive Syllogism. If one disjunct is eliminated, the other must hold.

\frac{p \lor q \quad \neg p}{q} \qquad \text{Tautology: } ((p \lor q) \land \neg p) \to q

Resolution. Two clauses sharing a complementary literal may be combined, eliminating the shared variable.

\frac{\neg p \lor r \quad p \lor q}{q \lor r} \qquad \text{Tautology: } ((\neg p \lor r) \land (p \lor q)) \to (q \lor r)

Constructive Dilemma. Two conditionals with a disjunction of their antecedents yield the disjunction of their consequents.

\frac{(\alpha \to \gamma) \quad (\beta \to \delta) \quad (\alpha \lor \beta)}{\gamma \lor \delta} \qquad \text{Tautology: } ((\alpha \to \gamma) \land (\beta \to \delta) \land (\alpha \lor \beta)) \to (\gamma \lor \delta)

Notice the relationships among these rules. Disjunctive Syllogism is a special case of Resolution (set $r = \bot$ and apply the Identity axiom). Addition is dual to Conjunction, and Simplification is a special case of Modus Ponens (since $(p \land q) \to p$ is a tautology).

Remark (Resolution Subsumes Other Rules)

Resolution is remarkably powerful. It can recover Hypothetical Syllogism: rewrite $p \to q$ as $\neg p \lor q$ and $q \to r$ as $\neg q \lor r$ (by the Conditional axiom, Lesson 1), then a single resolution step on $q$ yields $\neg p \lor r$ , which is $p \to r$ . It can also recover Modus Ponens: express $p$ as $p \lor \bot$ and $p \to q$ as $\neg p \lor q$ , and resolution gives $q \lor \bot \equiv q$ by the Identity axiom. This universality makes Resolution the basis of automated theorem proving in computer science.

The following table collects the propositional inference rules for reference.

\begin{array}{lcc} \textbf{Name} & \textbf{Rule} & \textbf{Tautology} \\ \hline \text{Modus Ponens} & p,\; p \to q \;\vdash\; q & ((p \to q) \land p) \to q \\ \text{Modus Tollens} & \neg q,\; p \to q \;\vdash\; \neg p & ((p \to q) \land \neg q) \to \neg p \\ \text{Hyp.\ Syllogism} & p \to q,\; q \to r \;\vdash\; p \to r & ((p \to q) \land (q \to r)) \to (p \to r) \\ \text{Conjunction} & p,\; q \;\vdash\; p \land q & (p \land q) \to (p \land q) \\ \text{Simplification} & p \land q \;\vdash\; p & (p \land q) \to p \\ \text{Addition} & p \;\vdash\; p \lor q & p \to (p \lor q) \\ \text{Disj.\ Syllogism} & p \lor q,\; \neg p \;\vdash\; q & ((p \lor q) \land \neg p) \to q \\ \text{Resolution} & \neg p \lor r,\; p \lor q \;\vdash\; q \lor r & ((\neg p \lor r) \land (p \lor q)) \to (q \lor r) \\ \text{Constr.\ Dilemma} & (\alpha \to \gamma),\; (\beta \to \delta),\; \alpha \lor \beta \;\vdash\; \gamma \lor \delta & ((\alpha \to \gamma) \land (\beta \to \delta) \land (\alpha \lor \beta)) \to (\gamma \lor \delta) \\ \text{Disj.\ Elimination} & (p \to r),\; (q \to r),\; p \lor q \;\vdash\; r & ((p \to r) \land (q \to r) \land (p \lor q)) \to r \\ \text{Ex Falso} & p,\; \neg p \;\vdash\; q & (p \land \neg p) \to q \end{array}

Problem 57

Identify the inference rule applied in each step of the following argument. Premises: (i) $p \to q$ , (ii) $\neg q \lor r$ , (iii) $\neg r$ .

From (ii) and (iii), conclude $\neg q$ .
From (i) and step 1, conclude $\neg p$ .

Building Complex Arguments

The power of inference rules lies in chaining them. A valid argument is a sequence of steps in which each step is either a premise or follows from earlier steps by a single inference rule.

Example 44

We show the following argument is valid. Premises: (1) $p \land (p \to q)$ , (2) $q \to r$ . Conclusion: $r$ .

\begin{array}{rll} 1. & p \land (p \to q) & \text{Premise} \\ 2. & q \to r & \text{Premise} \\ 3. & p & \text{Simplification from 1} \\ 4. & p \to q & \text{Simplification from 1} \\ 5. & q & \text{Modus Ponens from 3, 4} \\ 6. & r & \text{Modus Ponens from 5, 2} \end{array}

Problem 58

Show that the following argument is valid by listing each step and the inference rule used. Premises: (1) $p \to q$ , (2) $q \to (r \land s)$ , (3) $\neg r \lor u$ , (4) $p$ . Conclusion: $u$ .

Hint. Apply Hypothetical Syllogism, then Modus Ponens, then Simplification, then Disjunctive Syllogism.

Inference Rules for Quantified Statements

The rules above govern propositional logic. When predicates and quantifiers enter the picture, additional rules are needed to bridge the gap between universal or existential claims and their specific instances.

Universal Instantiation (UI). If a predicate holds for every element of the universe, it holds for any particular element $c$ :

\frac{\forall x\, P(x)}{P(c)} \quad \text{for any } c \text{ in the universe}

Universal Generalisation (UG). If $P(c)$ can be established for an arbitrary element $c$ (one about which no special assumptions are made), then $\forall x\, P(x)$ follows:

\frac{P(c) \text{ for arbitrary } c}{\forall x\, P(x)}

The word “arbitrary” is critical. If the proof of $P(c)$ exploits any property peculiar to $c$ , the generalisation is invalid.

Existential Instantiation (EI). If at least one element satisfies $P$ , we may introduce a name $c$ for such an element:

\frac{\exists x\, P(x)}{P(c) \text{ for some } c}

The name $c$ must be fresh: not previously used in the argument.

Existential Generalisation (EG). If a particular element $c$ satisfies $P$ , then at least one element does:

\frac{P(c)}{\exists x\, P(x)}

Universal Modus Ponens (UMP). Combining Universal Instantiation with Modus Ponens yields perhaps the most frequently used quantifier rule in practice:

\frac{\forall x\,(P(x) \to Q(x)) \quad P(c)}{Q(c)}

Example 45

Suppose we know $\forall x\,(x > 0 \to \sqrt{x} \in \mathbb{R})$ (the universe is $\mathbb{R}$ ) and that $9 > 0$ . Universal Modus Ponens yields $\sqrt{9} \in \mathbb{R}$ .

Problem 59

Identify the quantifier inference rule used in each step. The universe is the positive integers.

“Every multiple of $6$ is a multiple of $3$ .” (Premise)
” $18 = 6 \cdot 3$ , so $18$ is a multiple of $6$ .” (Premise)
“Therefore, $18$ is a multiple of $3$ .”
“Therefore, there exists a positive integer that is a multiple of $3$ .”

Example 46 (Combining Quantifier Rules)

We show that “a student in this class has not read the book” and “every student in this class passed the first exam” together imply “someone who passed the first exam has not read the book.”

Let $C(x)$ denote ” $x$ is in this class,” $B(x)$ denote ” $x$ has read the book,” and $E(x)$ denote ” $x$ passed the exam.” The premises are $\exists x\,(C(x) \land \neg B(x))$ and $\forall x\,(C(x) \to E(x))$ . We derive $\exists x\,(E(x) \land \neg B(x))$ .

\begin{array}{rll} 1. & \exists x\,(C(x) \land \neg B(x)) & \text{Premise} \\ 2. & \forall x\,(C(x) \to E(x)) & \text{Premise} \\ 3. & C(a) \land \neg B(a) \text{ for some } a & \text{EI from 1} \\ 4. & C(a) \to E(a) & \text{UI from 2} \\ 5. & C(a) & \text{Simplification from 3} \\ 6. & E(a) & \text{Modus Ponens from 4, 5} \\ 7. & \neg B(a) & \text{Simplification from 3} \\ 8. & E(a) \land \neg B(a) & \text{Conjunction from 6, 7} \\ 9. & \exists x\,(E(x) \land \neg B(x)) & \text{EG from 8} \end{array}

Fallacies

Definition 46 (Fallacy)

A fallacy is an argument form that appears valid but is not: the premises do not logically guarantee the conclusion, even though the reasoning may seem persuasive.

Two fallacies are especially common. Both arise from misapplying the conditional.

Affirming the Consequent. The argument ” $p \to q$ ; $q$ ; therefore $p$ ” is invalid. A counterexample: let $p = \bot$ and $q = \top$ . Then $p \to q$ is $\top$ and $q$ is $\top$ , but $p$ is $\bot$ .

Denying the Antecedent. The argument ” $p \to q$ ; $\neg p$ ; therefore $\neg q$ ” is equally invalid. With $p = \bot$ and $q = \top$ , both premises are satisfied but $\neg q$ is $\bot$ .

Both fallacies confuse an implication with its converse or its inverse (Lesson 1): $p \to q$ does not entail $q \to p$ , nor does it entail $\neg p \to \neg q$ .

Example 47

“If it rained, the pitch is wet. The pitch is wet. Therefore it rained.” This affirms the consequent. The pitch might be wet because the sprinklers were on. The converse “if the pitch is wet, then it rained” does not follow from the original implication.

Problem 60

Identify the fallacy in each argument and provide a counterexample (an assignment under which the premises are true but the conclusion is false).

(a) “If $n$ is divisible by $6$ , then $n$ is divisible by $3$ . The integer $9$ is divisible by $3$ . Therefore $9$ is divisible by $6$ .”

(b) “If $n$ is prime, then $n > 1$ . The integer $4$ is not prime. Therefore $4 \leqslant 1$ .”

Proof Techniques

With inference rules in hand, we turn to the practical matter of constructing proofs. A proof is a finite sequence of statements, each of which is an axiom, a premise, or a consequence of earlier statements by an inference rule. The form of the theorem often dictates the most effective strategy.

The building blocks of mathematical exposition have standard names. A theorem is a statement that can be shown to be true using definitions, axioms, other theorems, and rules of inference. An axiom is a statement accepted as true without proof (we met several in Lesson 1). A lemma is a “helping theorem,” proved in order to simplify the proof of a more substantial result. A corollary is a consequence that follows directly from a theorem. The term proposition is used for results considered less central than theorems. A conjecture is a statement proposed as true but not yet proved; Fermat’s Last Theorem was conjectured around 1637 and proved by Wiles in 1995, while Euler’s conjecture (an attempted generalisation) was conjectured in 1769 and disproved by counterexample in 1966.

The most common proof strategies for a conditional $p \to q$ are collected below. Each is developed in its own subsection.

\begin{array}{lll} \textbf{Strategy} & \textbf{Approach} & \textbf{Justification} \\ \hline \text{Trivial proof} & \text{Show } q \text{ is true} & q \text{ true} \implies p \to q \text{ true} \\ \text{Vacuous proof} & \text{Show } p \text{ is false} & p \text{ false} \implies p \to q \text{ true} \\ \text{Direct proof} & \text{Assume } p,\text{ derive } q & p \vdash q \;\implies\; \vdash p \to q \\ \text{Contrapositive} & \text{Assume } \neg q,\text{ derive } \neg p & p \to q \equiv \neg q \to \neg p \\ \text{Contradiction} & \text{Assume } p \land \neg q,\text{ derive } r \land \neg r & (p \land \neg q) \to \bot \;\implies\; p \to q \end{array}

The last two strategies are called indirect proofs, since they establish the conditional without directly constructing a chain from $p$ to $q$ .

Direct Proof

Definition 47 (Direct Proof)

A direct proof of a conditional statement $p \to q$ proceeds by assuming $p$ and deriving $q$ through a sequence of valid inferences. The assumption of $p$ is not asserted as fact; it is a hypothesis under which the argument operates.

This strategy reflects the Deduction Rule, a meta-logical principle: if assuming $p$ allows us to derive $q$ using valid inferences, then the conditional $p \to q$ is established. In a sense, the Deduction Rule is the bridge between the turnstile ( $\vdash$ ) and the conditional ( $\to$ ): the statement $p \vdash q$ (a syntactic derivation) becomes $p \to q$ (a logical truth).

Example 48 (Sum of Two Rationals)

If $r$ and $s$ are rational numbers, then $r + s$ is rational.

Proof

Assume $r$ and $s$ are rational. By Definition 27 (Lesson 2), there exist integers $a, b, c, d$ with $b \neq 0$ and $d \neq 0$ such that $r = \frac{a}{b}$ and $s = \frac{c}{d}$ . Then

r + s = \frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd}

Since $ad + bc$ and $bd$ are integers and $bd \neq 0$ , the fraction $\frac{ad + bc}{bd}$ satisfies Definition 27. Therefore $r + s \in \mathbb{Q}$ .

■

Example 49 (Product of Two Odd Integers)

If $m$ and $n$ are odd integers, then $mn$ is odd.

Proof

Assume $m$ and $n$ are odd. Since $m$ is not even, the Division Theorem (Theorem 9, Lesson 2) gives $m = 2j + 1$ for some integer $j$ . Likewise, $n = 2k + 1$ for some integer $k$ . Then

mn = (2j + 1)(2k + 1) = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1

Since $2jk + j + k$ is an integer, $mn$ leaves a remainder of $1$ when divided by $2$ , so $mn$ is not divisible by $2$ . By Definition 38 (Lesson 2), $mn$ is odd.

■

Problem 61

Prove directly that the product of a rational number and an integer is rational.

Problem 62

Prove directly that for all integers $a$ and $b$ , if $a \mid b$ , then $a^2 \mid b^2$ .

Hint. By Definition 37 (Lesson 2), $a \mid b$ means $b = qa$ for some integer $q$ .

Proof by Cases

When no single line of reasoning covers every possibility, it can be effective to partition the argument into exhaustive cases. If every case leads to the same conclusion, the conclusion holds unconditionally. This strategy corresponds to the disjunction elimination rule: if $p_1 \lor p_2 \lor \cdots \lor p_k$ is known and each $p_i$ implies $q$ , then $q$ follows.

Example 50 (Squares Modulo 3)

For every integer $n$ , the remainder when $n^2$ is divided by $3$ is either $0$ or $1$ .

Proof

By the Division Theorem (Theorem 9, Lesson 2), every integer $n$ satisfies exactly one of $n = 3k$ , $n = 3k + 1$ , or $n = 3k + 2$ for some integer $k$ .

Case 1. $n = 3k$ . Then $n^2 = 9k^2 = 3(3k^2)$ , so $n^2$ has remainder $0$ .

Case 2. $n = 3k + 1$ . Then $n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$ , so $n^2$ has remainder $1$ .

Case 3. $n = 3k + 2$ . Then $n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$ , so $n^2$ has remainder $1$ .

In all cases, the remainder is $0$ or $1$ .

■

Problem 63

Prove that for every integer $n$ , the remainder when $n^2$ is divided by $5$ is one of $0$ , $1$ , or $4$ .

Remark (Without Loss of Generality)

In a proof by cases, it sometimes happens that two cases are identical up to a relabelling of variables. We then handle one case and dismiss the other with the phrase “without loss of generality” (abbreviated WLOG). For instance, to prove by contrapositive that “if $x, y \in \mathbb{Z}$ and both $xy$ and $x + y$ are even, then $x$ and $y$ are both even,” we must show that if $x$ or $y$ is odd then $xy$ or $x + y$ is odd. Since the hypotheses are symmetric in $x$ and $y$ , we may assume WLOG that $x$ is odd; the remaining case follows by swapping $x$ and $y$ .

Proof by Contradiction

Definition 48 (Proof by Contradiction)

A proof by contradiction (Latin: reductio ad absurdum) establishes a proposition $p$ by assuming $\neg p$ and deriving a contradiction, that is, a statement of the form $q \land \neg q$ for some proposition $q$ . Since a sound proof system cannot derive a false conclusion from true premises, the assumption $\neg p$ must be false, so $p$ is true.

This technique is especially effective when the desired conclusion is a negation (” $x$ is not rational”) or when a direct approach offers no obvious path forward.

Example 51 (Rational Plus Irrational)

Let $r$ be a rational number and $a$ an irrational number. Then $r + a$ is irrational.

Proof

Suppose for contradiction that $r + a$ is rational. By Definition 27 (Lesson 2), there exist integers $p, q, m, n$ with $q \neq 0$ and $n \neq 0$ such that $r = \frac{p}{q}$ and $r + a = \frac{m}{n}$ . Then

a = (r + a) - r = \frac{m}{n} - \frac{p}{q} = \frac{mq - np}{nq}

Since $mq - np$ and $nq$ are integers with $nq \neq 0$ , $a$ is rational. This contradicts the hypothesis that $a$ is irrational. Therefore $r + a$ is irrational.

■

In Lesson 2, the interaction between rational and irrational numbers was discussed informally. The result above gives a precise instance: a rational shift can never send an irrational number to a rational one.

Problem 64

Let $x \in \mathbb{R}$ . Prove by contradiction that if $x$ is irrational, then $-x$ and $\frac{1}{x}$ are both irrational.

Example 52 (No Least Positive Real Number)

There is no least positive real number. That is, there is no positive real number $a$ such that $a \leqslant b$ for every positive real number $b$ .

Proof

Suppose for contradiction that a least positive real number $a$ exists: $a > 0$ and $a \leqslant b$ for every positive real number $b$ . Consider $\frac{a}{2}$ . Since $a > 0$ , we have $\frac{a}{2} > 0$ , so $\frac{a}{2}$ is a positive real number. But $\frac{a}{2} < a$ , contradicting $a \leqslant b$ for all positive $b$ .

■

Example 53 (Even Square Implies Even Root)

If $n$ is an integer and $n^2$ is even, then $n$ is even.

Proof

We prove the logically equivalent contrapositive: if $n$ is odd, then $n^2$ is odd. Assume $n$ is odd. Since $n$ is not even, the Division Theorem (Theorem 9, Lesson 2) gives $n = 2k + 1$ for some integer $k$ . Then

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1

Since $2k^2 + 2k$ is an integer, $n^2$ leaves remainder $1$ when divided by $2$ , so $n^2$ is odd. The contrapositive is logically equivalent to the original statement (Lesson 1).

■

Example 54 (Contrapositive: Parity of 3n + 2)

If $n$ is an integer and $3n + 2$ is odd, then $n$ is odd.

Proof

We prove the contrapositive: if $n$ is even, then $3n + 2$ is even. Suppose $n = 2k$ for some integer $k$ . Then

3n + 2 = 6k + 2 = 2(3k + 1)

Since $3k + 1 \in \mathbb{Z}$ , $3n + 2$ is even. The contrapositive is equivalent to the original statement.

■

Remark

The preceding proofs used the contrapositive rather than a direct contradiction. The distinction is worth noting. A proof by contradiction assumes the negation of the entire statement and derives an absurdity. A contrapositive proof assumes the negation of the conclusion and derives the negation of the hypothesis, which is simply a direct proof of the equivalent contrapositive. In practice, mathematicians often label both “proof by contradiction,” but the contrapositive route is frequently cleaner when hypothesis and conclusion are both conditionals.

The proof of the irrationality of $\sqrt{2}$ is the most celebrated “genuine” contradiction: the assumption leads to a statement that contradicts itself, rather than merely establishing a contrapositive. This fulfils the promise made in Lesson 2, where the irrationality of $\sqrt{2}$ was stated and its proof deferred.

Example 55 (Irrationality of √2)

$\sqrt{2}$ is irrational.

Proof

Suppose for contradiction that $\sqrt{2}$ is rational. By Definition 27 (Lesson 2), there exist integers $a$ and $b$ with $b \neq 0$ such that $\sqrt{2} = \frac{a}{b}$ , where $a$ and $b$ share no common factor. Squaring gives $2b^2 = a^2$ , so $a^2$ is even. By Example 52 above (even square implies even root), $a$ is even, say $a = 2c$ . Then $2b^2 = 4c^2$ , so $b^2 = 2c^2$ , and $b^2$ is even. By the same result, $b$ is even. But then $a$ and $b$ are both divisible by $2$ , contradicting the assumption that they share no common factor.

■

Theorem 15 (Pigeon-hole Principle)

If more than $N$ objects are distributed among $N$ containers, then at least one container holds two or more objects.

Proof

Suppose for contradiction that every container holds at most one object. Then the total number of objects is at most $N$ , contradicting the hypothesis that there are more than $N$ .

■

Problem 65

Prove by contradiction that there is no integer $n$ such that $n^2 + n$ is odd.

Hint. Factor: $n^2 + n = n(n + 1)$ . Consider the parity of $n$ and $n + 1$ .

Biconditional Proofs

A biconditional $p \leftrightarrow q$ is, by definition (Lesson 1), the conjunction $(p \to q) \land (q \to p)$ . To prove it, one must establish both directions: the forward implication and its converse. In practice, the two parts are labelled ( $\implies$ ) and ( $\impliedby$ ).

Example 56 (Characterisation of Odd Integers)

An integer $a$ is odd if and only if $a = 2b + 1$ for some integer $b$ .

Proof

( $\implies$ ) Suppose $a$ is odd. By Definition 38 (Lesson 2), $a$ is not even, so $2 \nmid a$ . The Division Theorem (Theorem 9) gives unique integers $b$ and $r$ with $0 \leqslant r < 2$ and $a = 2b + r$ . Since $r \in \{0, 1\}$ and $r = 0$ would give $2 \mid a$ , contradicting our assumption, we have $r = 1$ . Hence $a = 2b + 1$ .

( $\impliedby$ ) Suppose $a = 2b + 1$ for some integer $b$ . Then $a$ has remainder $1$ when divided by $2$ . By the Division Theorem, the remainder is unique, so $a \neq 2k$ for any integer $k$ . Hence $2 \nmid a$ , and by Definition 38, $a$ is odd.

■

Remark (Always Check the Converse)

A common error is to prove one direction of a biconditional and assume the other follows. Consider the equation $\sqrt{x - 3} + \sqrt{x + 4} = 7$ . Squaring both sides and simplifying produces $x = 12$ as the sole candidate. However, squaring can introduce extraneous solutions, so we must substitute back: $\sqrt{9} + \sqrt{16} = 3 + 4 = 7$ . Here the candidate is genuine. Contrast this with $x + \sqrt{x} = 0$ : squaring leads to candidates $x = 0$ and $x = 1$ , but $1 + \sqrt{1} = 2 \neq 0$ , so only $x = 0$ is a true solution.

Problem 66

Prove that an integer $n$ is even if and only if $n + 1$ is odd.

Example 57 (The Quadratic Formula)

Let $a, b \in \mathbb{C}$ . A complex number $\alpha$ is a root of the polynomial $x^2 + ax + b$ if and only if

\alpha = \frac{-a + \sqrt{a^2 - 4b}}{2} \quad \text{or} \quad \alpha = \frac{-a - \sqrt{a^2 - 4b}}{2}

This was stated without proof in Lesson 2. We now prove it as a biconditional.

Proof

( $\implies$ ) Suppose $\alpha^2 + a\alpha + b = 0$ . By the completing the square identity (Lesson 2),

\left(\alpha + \frac{a}{2}\right)^2 = \frac{a^2 - 4b}{4}

Since square roots of all complex numbers exist (Lesson 2),

\alpha + \frac{a}{2} = \frac{\sqrt{a^2 - 4b}}{2} \quad \text{or} \quad \alpha + \frac{a}{2} = \frac{-\sqrt{a^2 - 4b}}{2}

Subtracting $\frac{a}{2}$ gives the two stated values.

( $\impliedby$ ) Direct substitution of either value into $\alpha^2 + a\alpha + b$ and expanding yields $0$ .

■

Example 58 (Divisibility by 8 via Digits)

A natural number $n$ is divisible by $8$ if and only if the number formed by its last three base- $10$ digits is divisible by $8$ .

Proof

Let $d_r d_{r-1} \ldots d_1 d_0$ be the base- $10$ expansion of $n$ (Definition 32, Lesson 2). Write $n'$ for the number $d_2 d_1 d_0$ formed by the last three digits, and $n'' = n - n'$ . Then

n'' = d_r \cdot 10^r + \cdots + d_3 \cdot 10^3 = 1000(d_r \cdot 10^{r-3} + \cdots + d_3)

Since $1000 = 8 \times 125$ , we have $8 \mid n''$ .

( $\implies$ ) Suppose $8 \mid n$ . Then $n' = n - n''$ is the difference of two multiples of $8$ , so $8 \mid n'$ .

( $\impliedby$ ) Suppose $8 \mid n'$ . Then $n = n' + n''$ is the sum of two multiples of $8$ , so $8 \mid n$ .

■

Problem 67

Prove that a natural number $n$ is divisible by $3$ if and only if the sum of its base- $10$ digits is divisible by $3$ .

Hint. By the Division Theorem (Theorem 9, Lesson 2), $10 = 3 \cdot 3 + 1$ , so $10^k$ leaves remainder $1$ when divided by $3$ for every $k \geqslant 0$ .

Problem 68

Let $a, b \in \mathbb{R}$ with $a^2 - 4b \neq 0$ , and let $\alpha, \beta$ be the distinct roots of $x^2 + ax + b$ . Prove that there exists a real number $c$ such that $\alpha - \beta = c$ or $\alpha - \beta = ci$ .

Hint. Apply the quadratic formula and consider the cases $a^2 - 4b > 0$ and $a^2 - 4b < 0$ separately.

The Law of Excluded Middle

Theorem 16 (Law of Excluded Middle)

For any proposition $p$ , $p \lor \neg p$ is a tautology.

Proof

By the Complement axiom (Lesson 1), $\neg p \lor p \equiv \top$ . By the Commutativity axiom (Lesson 1), $\neg p \lor p \equiv p \lor \neg p$ . Therefore $p \lor \neg p \equiv \top$ .

■

The Law of Excluded Middle (LEM) asserts that every proposition is either true or false; no third possibility exists. In proofs, LEM allows us to split into the exhaustive cases $p$ and $\neg p$ even without knowing which actually holds. This is sometimes called non-constructive reasoning: the conclusion is established without determining which case obtains.

Example 59 (Even Product)

Let $a, b \in \mathbb{Z}$ . If $ab$ is even, then $a$ is even or $b$ is even (or both).

Proof

Suppose $ab$ is even. By LEM, either $a$ is even or $a$ is odd.

Case 1. If $a$ is even, the conclusion holds immediately.

Case 2. Suppose $a$ is odd. If $b$ were also odd, then by Example 48 (product of two odd integers), $ab$ would be odd. But $ab$ is even, a contradiction. Therefore $b$ is even.

In both cases, at least one of $a$ or $b$ is even.

■

Problem 69

Using the Law of Excluded Middle, prove that for all integers $n$ , $n(n + 1)$ is even.

Hint. By LEM, either $n$ is even or $n$ is odd. In each case, exhibit a factor of $2$ in $n(n + 1)$ .

Problem 70

Reflect on the proof of the preceding example (Even Product). Where was the Law of Excluded Middle used? Where was proof by contradiction used? What was the contradiction? Prove the same result twice more: once using contradiction without LEM, and once using LEM without contradiction.

Problem 71

Let $a$ and $b$ be irrational numbers. By considering the number $\sqrt{2}^{\sqrt{2}}$ , prove that it is possible for $a^b$ to be rational.

Hint. By LEM, either $\sqrt{2}^{\sqrt{2}}$ is rational or it is irrational. In each case, exhibit irrational numbers $a, b$ such that $a^b$ is rational. For the second case, examine $\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}$ .

Ex Falso Quodlibet

The principle ex falso sequitur quodlibet (“from falsity follows whatever you like”) states that from a contradiction, any proposition may be derived:

\frac{p \quad \neg p}{q} \quad \text{for every } q

Its validity rests on the tautology $(p \land \neg p) \to q$ : since $p \land \neg p$ is identically false, the conditional holds for every $q$ by vacuous truth.

Example 60 (Consequences of a Contradiction)

Suppose we accept the false premise $-1 = 1$ . Adding $1$ to both sides gives $0 = 2$ , a false consequence. Squaring both sides gives $1 = 1$ , a true consequence. From a single contradiction, both true and false statements follow. Once a contradiction enters, the proof system can no longer distinguish truth from falsehood, and every proposition becomes derivable.

We rarely invoke Ex Falso directly, but it is the logical foundation of proof by contradiction: if assuming $\neg p$ produces a contradiction with our true premises, then $\neg p$ cannot coexist with those premises, and $p$ must hold.

Proving Quantified Statements

The proof techniques developed above apply equally when the statement involves quantifiers. Two patterns arise directly from the quantifier rules (Universal Generalisation and Existential Generalisation).

Universally quantified goals. To prove $\forall x \in U,\, P(x)$ , fix an arbitrary element $c \in U$ , assuming nothing about $c$ beyond membership in $U$ , and prove $P(c)$ . Universal Generalisation then yields the universal claim. Every direct proof, proof by cases, or proof by contradiction of a “for all” statement opens by fixing such an element: “let $n$ be an integer”, “fix $r \in \mathbb{Q}$ ”, and so on. All the proofs in the preceding subsections follow this pattern.

Remark (A Common Error)

Consider the statement $\forall n \in \mathbb{Z},\, n^2 \geqslant 0$ . The following is not a valid proof: “Let $n$ be an arbitrary integer, say $n = 17$ . Then $17^2 = 289 \geqslant 0$ .” The writer has chosen a specific value, not an arbitrary one. This argument proves $\exists n \in \mathbb{Z},\, n^2 \geqslant 0$ , not the universal claim. A correct proof proceeds without naming $n$ : “Let $n \in \mathbb{Z}$ . If $n \geqslant 0$ , then $n^2 \geqslant 0$ since the product of two non-negative numbers is non-negative. If $n < 0$ , then $n^2 > 0$ since the product of two negative numbers is positive.”

Example 61 (Final Digits of Perfect Squares)

The base- $10$ expansion of the square of every natural number ends in one of the digits $0, 1, 4, 5, 6$ , or $9$ .

Proof

Fix $n \in \mathbb{N}$ and let $d_r d_{r-1} \ldots d_0$ be its base- $10$ expansion (Definition 32, Lesson 2). Write $n = 10m + d_0$ where $m \in \mathbb{N}$ . Then

n^2 = 100m^2 + 20md_0 + d_0^2 = 10(10m^2 + 2md_0) + d_0^2

The final digit of $n^2$ is therefore the final digit of $d_0^2$ . Since $d_0 \in \{0, 1, \ldots, 9\}$ , we compute:

0, \; 1, \; 4, \; 9, \; 16, \; 25, \; 36, \; 49, \; 64, \; 81

The final digits are $0, 1, 4, 9, 6, 5, 6, 9, 4, 1$ , all belonging to $\{0, 1, 4, 5, 6, 9\}$ .

■

Problem 72

Prove that for all real numbers $x$ and $y$ , if $x$ is irrational, then $x + y$ and $x - y$ are not both rational.

Hint. Suppose for contradiction that both are rational, and compute their sum.

Problem 73

Prove that every integer is rational.

Problem 74

Prove that every linear polynomial over $\mathbb{Q}$ has a rational root.

Hint. A linear polynomial over $\mathbb{Q}$ has the form $ax + b$ where $a, b \in \mathbb{Q}$ and $a \neq 0$ .

Problem 75

Prove that for all $x, y \in \mathbb{Q}$ , if $x < y$ then there exists $z \in \mathbb{Q}$ with $x < z < y$ .

Hint. Consider $z = \frac{x + y}{2}$ .

Existentially quantified goals. To prove $\exists x \in U,\, P(x)$ , exhibit a specific element $c \in U$ and verify $P(c)$ . Existential Generalisation then yields the existential claim. This is called a constructive existence proof: the witness is explicitly produced.

Example 62 (A Constructive Existence Proof)

Fix $a \in \mathbb{R}$ . The cubic polynomial $x^3 + (1 - a^2)x - a$ has a real root.

Proof

Define $x = a$ . Then

a^3 + (1 - a^2)a - a = a^3 + a - a^3 - a = 0

Since $a \in \mathbb{R}$ , the polynomial has a real root.

■

Example 63 (A Perfect Square Above a Perfect Cube)

There is a natural number that is simultaneously a perfect square and one more than a perfect cube.

Proof

Take $n = 9$ . Then $n = 3^2$ and $n = 2^3 + 1$ , so $n$ is a perfect square and one more than a perfect cube.

■

Example 64 (Sums of Cubes in Two Ways)

There exists a positive integer expressible as a sum of two cubes in two distinct ways.

Proof

Take $n = 1729$ . Then $1729 = 10^3 + 9^3 = 12^3 + 1^3$ . (This is the Hardy–Ramanujan number, after a celebrated anecdote between G. H. Hardy and S. Ramanujan.)

■

In a non-constructive existence proof, we establish that a witness must exist without identifying it. The $\sqrt{2}^{\sqrt{2}}$ exercise earlier is an example: LEM guarantees that one of two candidates works, but the proof does not determine which.

Disproving universal claims. To show $\forall x \in U,\, P(x)$ is false, it suffices to exhibit a single counterexample: an element $c$ with $\neg P(c)$ . This is an existence proof of $\exists x \in U,\, \neg P(x)$ .

Example 65 (A Counterexample)

The claim “every positive integer is the sum of two perfect squares” is false. The integer $3$ is a counterexample: the only sums of two squares not exceeding $3$ are $0 + 0 = 0$ , $0 + 1 = 1$ , $1 + 1 = 2$ , and $0 + 4 = 4$ , none of which equal $3$ .

Problem 76

Disprove the claim: for every integer $n \geqslant 2$ , $2^n + 1$ is prime.

Problem 77

Prove that there is an integer that is divisible by zero.

Hint. Recall Definition 37 (Lesson 2): $a \mid b$ means $b = qa$ for some integer $q$ .

Uniqueness. To prove $\exists!\, x \in U,\, P(x)$ (the unique existential quantifier, Lesson 3), first establish existence by producing a witness $c$ with $P(c)$ , then establish uniqueness by assuming $P(a)$ and $P(b)$ and deducing $a = b$ .

Example 66 (Unique Positive Square Root)

Every positive real number has a unique positive square root.

Proof

Fix $a > 0$ .

Existence. The number $\sqrt{a}$ is positive and satisfies $(\sqrt{a})^2 = a$ .

Uniqueness. Suppose $y, z > 0$ with $y^2 = a$ and $z^2 = a$ . Then $y^2 = z^2$ , so $(y - z)(y + z) = 0$ . If $y + z = 0$ , then $z = -y < 0$ , contradicting $z > 0$ . Therefore $y - z = 0$ , i.e., $y = z$ .

■

Problem 78

Let $n \in \mathbb{Z}$ . Prove that if $n^3$ is divisible by $3$ , then $(n + 1)^3 - 1$ is divisible by $3$ .

Hint. Expand $(n + 1)^3 - 1$ and use the hypothesis $3 \mid n^3$ .

Problem 79

(a) Prove that there is a real number which is irrational but whose square is rational.

(b) Prove that for each real number $a$ , the equation $x^2 + 2ax + a^2 = 0$ has exactly one real solution.

Problem 80

Prove that there is a unique natural number with exactly one positive divisor.

Remark (Mistakes in Proofs)

A chain of equalities is only as strong as its weakest step. Consider the “proof” that $-1 = 1$ :

\begin{aligned} -1 &= (-1)^1 \\ &= (-1)^{2/2} \\ &= \bigl((-1)^2\bigr)^{1/2} \\ &= 1^{1/2} \\ &= 1 \end{aligned}

The error is in the third step: the law $(x^a)^b = x^{ab}$ requires $x \geqslant 0$ . Similarly, squaring both sides of an equation can introduce extraneous solutions (as noted in the biconditional remark above). Each step in a proof must be a valid inference, not merely a plausible manipulation.

Quantifiers can also conceal errors. The formula $(p \to q) \lor (q \to p)$ is a propositional tautology (verify this by truth table). Substituting predicates $p(n)$ = ” $n$ is odd” and $q(n)$ = ” $n$ is prime,” one might reason: “for every $n$ , either oddness implies primality or primality implies oddness.” Yet neither $\forall n\,(p(n) \to q(n))$ nor $\forall n\,(q(n) \to p(n))$ is true. The resolution is that $\forall n\,[(p(n) \to q(n)) \lor (q(n) \to p(n))]$ is not the same as $[\forall n\,(p(n) \to q(n))] \lor [\forall n\,(q(n) \to p(n))]$ . The universal quantifier does not distribute over disjunction. The first formula is indeed true (for each fixed $n$ , one of the two conditionals holds), but the second is false.

Note (Hilbert Systems)

It is possible to build a far more economical proof system than the one developed in these notes. Hilbert and Frege showed that all of propositional logic can be axiomatised using only two connectives ( $\neg$ and $\to$ ), three axiom schemas, and Modus Ponens as the sole rule of inference. The price of such minimalism is longer proofs: what we accomplish in a few lines may require many more steps in a Hilbert system.

Natural Deduction

An alternative framework, called natural deduction (developed independently by Gentzen and Jaśkowski in the 1930s), organises inference rules into introduction rules (which establish a connective) and elimination rules (which extract information from it). The Conjunction rule is the introduction rule for $\land$ ( $\land$ I), and the two Simplification rules are its elimination rules ( $\land$ E $_1$ , $\land$ E $_2$ ). Addition is $\lor$ I, and Modus Ponens is $\to$ E. Both our current system and natural deduction are sound and complete for propositional logic.

In this framework, rules are combined into proof trees. Each leaf is an assumption, and each internal node applies an introduction or elimination rule. For instance, the tree

\frac{\dfrac{p \quad q}{p \land q}\;(\land\text{I}) \quad r}{(p \land q) \land r}\;(\land\text{I})

shows how to prove $(p \land q) \land r$ : first combine $p$ and $q$ by $\land$ I to obtain $p \land q$ , then combine that result with $r$ by a second application of $\land$ I.

Example 67 (A Natural Deduction Proof Tree)

We derive $p \land r$ from the premises $p$ , $p \to q$ , and $q \to r$ .

\frac{p \quad \dfrac{\dfrac{p \quad (p \to q)}{q}\;(\to\text{E}) \quad (q \to r)}{r}\;(\to\text{E})}{p \land r}\;(\land\text{I})

Reading from the leaves: $p$ and $p \to q$ yield $q$ by $\to$ E (Modus Ponens); then $q$ and $q \to r$ yield $r$ by a second $\to$ E; finally, $p$ and $r$ are combined by $\land$ I.

Problem 81

Write a proof tree whose conclusion is $(p \land q) \land (r \land s)$ . Then express “2 is an even prime and 3 is an odd prime” in the form $(p \land q) \land (r \land s)$ for appropriate propositions $p, q, r, s$ , and describe what your proof tree says about proving the statement.