Indirect Proof

Indirect arguments are useful when a negated statement gives a concrete restriction that the original conclusion does not. Two common methods are proof by contrapositive and proof by contradiction. Their relationship was introduced in Converse, Inverse, and Contrapositive; here the focus is choosing assumptions carefully and finishing actual proofs.

We use classical logic. A contradiction must be a specific conflict with a hypothesis, definition, or established fact. Being unable to continue a calculation is not a contradiction. MIT’s introductory proof notes provide further examples of how assumptions support a proof [1][1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf.

Choose the starting assumptions before calculating

Method for proving $P\to Q$	What to assume	What to establish
Direct	$P$	$Q$
Contrapositive	$\neg Q$	$\neg P$
Contradiction	$P$ and $\neg Q$	A contradiction $\bot$

Domain restrictions remain active in every row. For a universal theorem, a contradiction proof assumes a counterexample exists and chooses one satisfying the hypothesis while violating the conclusion. For a nonexistence theorem, assume an object with the forbidden properties exists. Write the full negation, including its quantifiers, before manipulating symbols.

The two indirect methods can overlap: one may prove a contrapositive using a contradiction. Their names describe the organization of the argument, not mutually exclusive categories.

Contrapositive: use a workable representation

PropositionParity of a polynomial

For every integer $x$, if $x^2-6x+5$ is even, then $x$ is odd.

Starting from the evenness of the polynomial gives little immediate information about $x$. The negation of the conclusion is more useful: for integers, “not odd” means “even,” which supplies the representation $x=2a$.

Proof

We prove the contrapositive. Let $x=2a$ with $a\in\mathbb Z$. Then

$$\begin{aligned} x^2-6x+5&=4a^2-12a+5\\ &=2(2a^2-6a+2)+1. \end{aligned}$$

The bracketed quantity is an integer, so the polynomial is odd and therefore not even. This proves the contrapositive, hence the original statement.

This proof never assumes that the polynomial is even. A contradiction proof would assume both that it is even and that $x$ is not odd, then obtain a number that is simultaneously even and odd.

Contradiction: name the incompatible facts

PropositionThe square root of two is irrational

The positive real number $\sqrt2$ is not rational.

The assumption of rationality produces a fraction, while choosing lowest terms gives a property that divisibility can contradict. We use the already established parity fact that an integer with an even square is even.

Proof

Suppose $\sqrt2=p/q$, where $p,q$ are positive integers with no common divisor greater than one. Such a lowest-terms representation can be chosen for any positive rational number. Squaring gives

$$p^2=2q^2.$$

Thus $p^2$ is even, so $p$ is even. Write $p=2r$ with $r\in\mathbb Z$. Substituting and simplifying yields

$$4r^2=2q^2, \qquad q^2=2r^2.$$

Consequently $q$ is even as well. Both $p$ and $q$ are divisible by $2$, contradicting the lowest-terms condition. Therefore $\sqrt2$ is irrational.

Merely finding a representation with an even numerator and denominator would not be a contradiction: $2/2$ is a perfectly valid fraction. It conflicts specifically with the choice of a coprime numerator and denominator. Naming that conflict is what completes the proof.

A finite-list contradiction

PropositionThere are infinitely many primes

The prime numbers cannot be exhausted by a finite list.

We use the elementary fact that every integer $N>1$ has a prime divisor. One justification is to take its least divisor $d>1$; if $d$ were composite, a smaller divisor greater than one would divide $N$, contradicting minimality.

Proof

Suppose all primes form the finite list $p_1,\ldots,p_m$. The list is nonempty because $2$ is prime. Set

$$N=p_1p_2\cdots p_m+1.$$

Since $N>1$, choose a prime divisor $q$ of $N$. It must appear in the supposedly complete list, so it also divides the product $p_1\cdots p_m$. It would then divide the difference $N-p_1\cdots p_m=1$, which no prime does. This contradiction proves the claim.

The constructed $N$ need not be prime. The proof needs only a prime divisor outside the list. Replacing that statement by “the product plus one is always prime” would introduce a false claim.

Common logical slips

Negating “both $a$ and $b$ are odd” gives “at least one is not odd,” not “both are even.” Negating “$a\ge8$ or $b\ge8$” gives both strict inequalities $a<8$ and $b<8$. Integer assumptions may then sharpen each to a bound of $7$; the same sharpening is invalid for real numbers.

Also distinguish proving a claim from proving its converse. Showing an even integer has an even square does not establish that an even square has an even integer root. When unsure, write $P,Q$ explicitly and compare the assumed statement with the target before continuing.

Exercises

ExerciseAn irrational square root with a justified divisor step

Prove $\sqrt5$ irrational. First explain why $5\mid t^2$ implies $5\mid t$ for integers $t$.

Show solution

Solution

The possible remainders of $t$ modulo $5$ are $0,1,2,3,4$, whose squares have remainders $0,1,4,4,1$. Thus only remainder zero can give a square divisible by $5$.

If $\sqrt5=p/q$ in lowest positive terms, then $p^2=5q^2$, hence $p=5k$. Substitution gives $q^2=5k^2$, so $q$ is also divisible by $5$. This contradicts coprimality. The residue argument supplies the divisibility fact instead of silently assuming it for every integer divisor.

ExerciseNo least positive rational

Prove that there is no smallest positive rational number.

Show solution

Solution

Suppose $r\in\mathbb Q$ is positive and no positive rational is smaller. Then $r/2$ is rational and satisfies $0<r/2<r$, contradicting minimality. No lowest-terms representation is needed here. Equivalently, the construction proves directly that every positive rational has a smaller positive rational.

ExerciseKeep both assumptions in a contradiction proof

Prove by contradiction that if an integer $n$ has an even square, then $n$ is even. Identify the pair of incompatible facts.

Show solution

Solution

Assume $n^2$ is even and $n$ is not even. Integer parity makes $n$ odd, so write $n=2k+1$. Then $n^2=2(2k^2+2k)+1$ is odd. The contradiction is that $n^2$ is both even and odd. If the proof instead starts only from odd $n$ and concludes odd $n^2$, it is a direct proof of the contrapositive.

ExerciseClosure produces the contradiction

Prove that the sum of an irrational real number and a rational number is irrational.

Show solution

Solution

Let $r\notin\mathbb Q$ and $s\in\mathbb Q$. Suppose $t=r+s$ is rational. Then $r=t-s$ is rational, because rational numbers are closed under subtraction, contradicting the choice of $r$. Explicitly, if $t=a/b$ and $s=c/d$ with nonzero integer denominators, then

$$t-s=\frac{ad-bc}{bd}\in\mathbb Q.$$

This argument does not establish that the sum of two irrational numbers is irrational; $\sqrt2+(-\sqrt2)=0$ refutes that different claim.

ExerciseNegate a conjunction correctly

For integers $a,b$, prove that odd $ab$ implies both $a$ and $b$ are odd.

Show solution

Solution

The contrapositive assumes at least one factor is even. By symmetry, call it $a=2k$ with $k\in\mathbb Z$. Then $ab=2(kb)$ is even. The case where $b$ is even has the same argument with names exchanged, so the entire contrapositive is proved.

ExerciseA linear expression

For integer $n$, prove that if $3n+2$ is even, then $n$ is even.

Show solution

Solution

Prove the contrapositive. If $n=2k+1$, then $3n+2=6k+5=2(3k+2)+1$ is odd, with $3k+2\in\mathbb Z$. Therefore the original implication holds.

ExerciseThe integer domain is doing work

For integers $a,b$, prove that $a+b\ge15$ implies $a\ge8$ or $b\ge8$. Does the statement remain true for real $a,b$?

Show solution

Solution

Assume the negation of the conclusion: $a<8$ and $b<8$. Because these are integers, each is at most $7$, so $a+b\le14<15$. This proves the contrapositive. For real numbers the statement is false: $a=b=7.5$ gives sum $15$ but neither reaches $8$.

From negation to induction

Use a contradiction when the negated target gives an object or extremal condition that cannot exist. Use a contrapositive when the negated conclusion has a convenient representation. For statements indexed by natural-number size, the more useful information may be the truth of smaller instances; that is the subject of Mathematical Induction.

References

1. [1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf ↩