Unit 3 Lesson 1

Reductio ad Absurdum

In this lesson, we introduce the first formal method of proof: reductio ad absurdum, or proof by contradiction. We see how the apparatus of negation, implication, and the Law of Non-Contradiction combine to yield a powerful technique for establishing mathematical truths.

Learning Objectives

  • State the principle of reductio ad absurdum rigorously
  • Justify the technique using the Law of Non-Contradiction and double negation
  • Apply reductio to prove statements about numbers, including the irrationality of \(\sqrt{2}\)
  • Identify the correct assumption when proving an implication by reductio
  • Distinguish a complete reductio from a proof that stops short of a contradiction

From Logic to Proof

Units 1 and 2 were devoted to constructing the apparatus of mathematical logic: propositions, predicates, quantifiers, the five connectives, equivalences, and the correspondence with sets. This apparatus was developed in service of a single goal — the central activity of mathematics: proof.

This unit examines three classical methods of logical reasoning. We begin with reductio ad absurdum, a technique whose Latin name means “reduction to absurdity.” In subsequent lessons we shall meet mathematical induction and the elementary methods of counting.

Reductio ad Absurdum

Reductio ad absurdum (or proof by contradiction) is the following method of proof. To establish a proposition \(P\):

  1. Suppose, for the sake of argument, that \(\neg P\) holds.

  2. From this supposition, deduce a contradiction — a proposition of the form \(Q \land \neg Q\) for some proposition \(Q\).

  3. Conclude that the supposition \(\neg P\) cannot hold; that is, \(P\) holds.

The supposition introduced in step (1) is called the assumption for contradiction. The reasoning in step (2) must employ only valid logical and mathematical steps. The conclusion in step (3) follows from the principles established in earlier units.

The Logical Justification

Why is reductio a valid method? The argument unfolds in three steps, each grounded in results already established.

By the Law of Non-Contradiction (Unit 1, Lesson 2; formalised in Unit 2, Lesson 1), no proposition of the form \(Q \land \neg Q\) can be true. Such a proposition is a contradiction: it is false in every row of every truth table.

The reasoning in step (2) above establishes the implication \(\neg P \to (Q \land \neg Q)\). An implication with a true hypothesis cannot have a false conclusion. Since the conclusion \(Q \land \neg Q\) is necessarily false, the hypothesis \(\neg P\) must also be false. That is, \(\neg \neg P\) holds.

By the Law of Double Negation (Unit 2, Lesson 3), \(\neg \neg P \equiv P\). Therefore \(P\) holds, as required.

The Irrationality of \(\sqrt{2}\)

The number \(\sqrt{2}\) is irrational. That is, there exist no integers \(p\) and \(q\), with \(q \neq 0\), such that

\[\sqrt{2} = \frac{p}{q}\]

This theorem, attributed to the Pythagorean school of ancient Greece, is the canonical illustration of reductio ad absurdum. Its discovery is said to have shaken the early Pythagorean conviction that all magnitudes are commensurable.

Proof — Irrationality of \(\sqrt{2}\)

Suppose, for contradiction, that \(\sqrt{2}\) is rational. Then there exist integers \(p\) and \(q\), with \(q \neq 0\), such that \(\sqrt{2} = p/q\). By reducing the fraction to lowest terms if necessary, we may assume that \(p\) and \(q\) share no common divisor greater than 1; equivalently, \(\gcd(p, q) = 1\).

Squaring both sides yields:

\[2 = \frac{p^2}{q^2}, \quad \text{equivalently,} \quad p^2 = 2q^2 \qquad (\ast)\]

Equation \((\ast)\) shows that \(p^2\) is even. We claim this forces \(p\) itself to be even. Indeed, if \(p\) were odd, we could write \(p = 2k + 1\) for some integer \(k\); then

\[p^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\]

which is odd. Contrapositively, if \(p^2\) is even, then \(p\) is even.

Write \(p = 2m\) for some integer \(m\). Substituting into \((\ast)\):

\[(2m)^2 = 2q^2 \quad\Longrightarrow\quad 4m^2 = 2q^2 \quad\Longrightarrow\quad q^2 = 2m^2\]

So \(q^2\) is also even, and by the same reasoning, \(q\) is even.

But now both \(p\) and \(q\) are divisible by 2, contradicting our earlier assumption that \(\gcd(p, q) = 1\).

The supposition that \(\sqrt{2}\) is rational has led to a contradiction. Therefore \(\sqrt{2}\) is irrational. \(\blacksquare\)

Reductio for Implications

A particularly common application of reductio arises when the proposition to be proved is an implication \(P \to Q\). To prove \(P \to Q\) by reductio, we must assume its negation. From Unit 2, Lesson 3, we know:

\[\neg(P \to Q) \;\equiv\; P \land \neg Q\]

The assumption for contradiction is therefore \(P \land \neg Q\): we suppose that the hypothesis \(P\) holds and the conclusion \(Q\) fails. From this supposition we derive a contradiction, and conclude \(P \to Q\).

This rule is decisive in practice: when proving an implication by reductio, one must assume both that the hypothesis holds and that the conclusion fails. Assuming only the negation of the hypothesis — or only the negation of the conclusion — is incorrect, as it does not negate the implication.

Example: There Is No Greatest Integer

Claim. There is no greatest integer. Equivalently: \(\neg \exists M \in \mathbb{Z},\; \forall n \in \mathbb{Z},\; n \leq M\).

Proof. Suppose, for contradiction, that there exists a greatest integer \(M\); that is, an integer satisfying \(n \leq M\) for every integer \(n\).

Consider the integer \(M + 1\). Since the integers are closed under addition, \(M + 1\) is itself an integer. Moreover, \(M + 1 > M\).

But this contradicts the defining property of \(M\), namely that no integer exceeds it.

The assumption fails. Hence there is no greatest integer. \(\blacksquare\)

The Anatomy of a Reductio Argument

Every reductio proof has the same five-part structure:

  1. State precisely the proposition to be proved.

  2. Suppose, for contradiction, that the negation holds. For an implication \(P \to Q\), the negation is \(P \land \neg Q\).

  3. Reason from this supposition using only valid logical and mathematical steps.

  4. Derive a contradiction — a proposition of the form \(Q \land \neg Q\).

  5. Conclude that the original proposition holds.

The discipline of reductio lies in step (4): the argument is incomplete until an actual contradiction has been derived. A surprising or unfamiliar consequence is not, in itself, a contradiction. Two facts that simply seem incompatible do not constitute a contradiction unless one is the formal negation of the other.

Connection to Computer Science

Computer programs that check the correctness of mathematical reasoning — used widely in software verification and security — often work by reductio. To verify a statement, the program assumes its negation and searches systematically for a contradiction. If one is found, the original statement is confirmed.

Exercise 1

For each implication to be proved by reductio ad absurdum, identify the correct assumption to make for contradiction.

a)

If \(a > b\) and \(b > c\), then \(a > c\).

What assumption should be made for the reductio?

b)

If \(n\) is even, then \(n + 1\) is odd.

What assumption should be made for the reductio?

c)

If \(x^2 = 0\), then \(x = 0\).

What assumption should be made for the reductio?

Exercise 2

For each argument, decide whether it is a valid reductio ad absurdum proof.

a)

Claim: There is no smallest positive rational number.

Proof: Suppose, for contradiction, that \(r\) is the smallest positive rational. Then \(r/2\) is also a positive rational, and \(r/2 < r\). This contradicts that \(r\) is the smallest. Hence no smallest positive rational exists.

b)

Claim: \(\sqrt{3}\) is irrational.

Proof: Suppose \(\sqrt{3} = p/q\) with \(\gcd(p, q) = 1\). Squaring, \(p^2 = 3q^2\), so \(p^2\) is divisible by 3. Hence \(p\) is divisible by 3. The proof is complete by contradiction.

c)

Claim: The equation \(x^2 + 1 = 0\) has no real solution.

Proof: For every real \(x\), \(x^2 \geq 0\), so \(x^2 + 1 \geq 1 > 0\). Hence \(x^2 + 1 \neq 0\) for any real \(x\).

d)

Claim: Every multiple of 6 is even.

Proof: Suppose, for contradiction, that some multiple of 6 is odd; let \(n = 6k\) be such a multiple. But \(6k = 2(3k)\), which is even by definition. This contradicts that \(n\) is odd. Hence every multiple of 6 is even.

Exercise 3

For each completed reductio proof, identify the precise contradiction.

a)

In the proof of the irrationality of \(\sqrt{2}\), we assume \(\sqrt{2} = p/q\) with \(\gcd(p, q) = 1\) and conclude that both \(p\) and \(q\) are divisible by 2.

What is the contradiction in the proof?

b)

In the proof that there is no greatest integer, we assume \(M\) is the greatest integer and consider \(M + 1\).

What is the contradiction in the proof?

c)

In the proof that there is no smallest positive rational number, we assume \(r\) is the smallest and consider \(r/2\).

What is the contradiction in the proof?

A student is asked to prove the following implication by reductio:

“If \(n^2\) is even, then \(n\) is even.”

The student writes:

Suppose, for contradiction, that \(n^2\) is not even — that is, \(n^2\) is odd. Then \(n\) must be odd, since the square of an even number is even. But this is not a contradiction… I am stuck.

Where did the student go wrong, and what should the assumption have been?

Analysis

The student went wrong at the very first step: they negated the wrong thing.

The implication has the form \(P \to Q\), where \(P\): “\(n^2\) is even” and \(Q\): “\(n\) is even.” In Unit 2, Lesson 3, we proved:

\[\neg(P \to Q) \;\equiv\; P \land \neg Q\]

The negation of the implication is therefore “\(n^2\) is even and \(n\) is odd” — not “\(n^2\) is odd.” The student assumed \(\neg P\) when they should have assumed \(P \land \neg Q\). With only \(\neg P\) in hand, they cannot derive a contradiction with \(Q\), because \(Q\) is no longer in play.

Let us redo the proof correctly.

Correct reductio. Suppose, for contradiction, that \(n^2\) is even and \(n\) is odd. Since \(n\) is odd, write \(n = 2k + 1\) for some integer \(k\). Then

\[n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\]

which is odd. But we assumed \(n^2\) is even. This is a contradiction. Hence the implication holds.

The methodological lesson: when proving an implication \(P \to Q\) by reductio, the assumption is always \(P \land \neg Q\). One must keep both the hypothesis (\(P\)) and the negated conclusion (\(\neg Q\)) in play, so that a contradiction can arise from their interaction.

  • Reductio ad absurdum proves a proposition \(P\) by supposing \(\neg P\), deriving a contradiction (a proposition of the form \(Q \land \neg Q\)), and concluding \(P\).

  • The justification rests on the Law of Non-Contradiction (no \(Q \land \neg Q\) is true) combined with the Law of Double Negation (\(\neg \neg P \equiv P\)).

  • To prove an implication \(P \to Q\) by reductio, the assumption is \(P \land \neg Q\), not merely \(\neg P\) or \(\neg Q\). This relies on the equivalence \(\neg(P \to Q) \equiv P \land \neg Q\) from Unit 2, Lesson 3.

  • A reductio proof is incomplete until a genuine contradiction has been derived. A surprising or unfamiliar consequence is not, by itself, a contradiction.

  • Classical applications include the irrationality of \(\sqrt{2}\), the non-existence of a greatest integer, and the non-existence of a smallest positive rational.