Proof by Contradiction

Hello. In the previous lesson, you proved implications by contraposition: rather than starting from $P$, you assumed $\neg Q$ and established $\neg P$. Proof by contradiction is closely related, but it has a different logical shape and a broader range of uses.

This lesson develops the method carefully: you will learn how to negate the entire statement you want to prove, derive a genuine impossibility from that negation, and write the final conclusion precisely. We will use parity first, then a classic irrationality proof that will connect directly to later number theory.

---

The central idea: rule out the alternative

Suppose your goal is to prove a statement $S$. A proof by contradiction begins by temporarily assuming that $S$ is false:

$$\neg S.$$

You then reason rigorously from that assumption, together with definitions and established facts. If this leads to an impossibility, the assumption $\neg S$ cannot be true. Therefore $S$ must be true.

A contradiction must be a real logical conflict, not merely something surprising or inconvenient. Typical contradictions include showing that:

• one integer is both even and odd;
• a quantity is simultaneously equal to two unequal values;
• an integer is equal to a noninteger;
• a supposedly reduced fraction has a common factor;
• an object both belongs and does not belong to a specified set.

The basic written structure is:

Proof. Suppose, for the sake of contradiction, that [the negation of the statement] holds.
Then [deduce consequences using definitions and known results].
But [state the impossibility and why it is impossible].
Therefore the assumption was false. Hence [the original statement] is true. $\square$

The phrase “for the sake of contradiction” signals that the assumption is provisional. You are not claiming it is true; you are testing its consequences.

---

A first proof: no integer is both even and odd

Consider the claim:

$$\text{No integer is both even and odd.}$$

This is a universal negative statement. More explicitly, it says that every integer fails to have the two properties simultaneously:

$$\forall n\in \mathbb{Z},\neg (n\text{ is even}\wedge n\text{ is odd}).$$

To negate it, reverse the quantifier and remove the inner negation. Its negation is:

$$\exists n\in \mathbb{Z},(n\text{ is even}\wedge n\text{ is odd}).$$

So a contradiction proof must begin by assuming there is a particular integer that is both even and odd.

Theorem. No integer is both even and odd.

Proof. Suppose, for the sake of contradiction, that there exists an integer $n$ that is both even and odd.

Because $n$ is even, there is an integer $a$ such that

$$n=2a.$$

Because $n$ is odd, there is an integer $b$ such that

$$n=2b+1.$$

Since both expressions equal $n$,

$$2a=2b+1.$$

Rearranging gives

$$2(a-b)=1.$$

The left-hand side is even, since it is twice the integer $a-b$. But the right-hand side is odd. This is impossible.

Therefore our assumption was false. No integer is both even and odd. $\square$

Notice the architecture of the proof:

1. The negation supplied a witness, the alleged integer $n$.
2. Each of the two assumed properties supplied an algebraic representation of $n$.
3. Equating the representations forced an impossibility.

This pattern will recur throughout number theory: assume an exceptional object exists, unpack its defining properties, and show that those properties cannot coexist.

---

A deeper example: proving that $\sqrt{2}$ is irrational

A number is rational if it can be written as a ratio of integers:

$$r=\frac{a}{b},$$

where $a,b\in \mathbb{Z}$ and $b\ne 0$. Any rational number can be expressed in lowest terms, meaning its numerator and denominator have no common positive divisor other than $1$. In symbols, we can arrange that

$$\gcd (a,b)=1.$$

The theorem is:

$$\sqrt{2}\text{ is irrational.}$$

A direct proof would require somehow showing that no fraction can equal $\sqrt{2}$, which offers no natural starting point. Contradiction turns this negative-looking statement into something concrete: assume that one reduced fraction does equal $\sqrt{2}$.

Theorem. $\sqrt{2}$ is irrational.

Proof. Suppose, for the sake of contradiction, that $\sqrt{2}$ is rational. Then there exist integers $a$ and $b$, with $b\ne 0$ and

$$\gcd (a,b)=1,$$

such that

$$\sqrt{2}=\frac{a}{b}.$$

Squaring both sides gives

$$2=\frac{a^2}{b^2}.$$

Multiplying by $b^2$, we obtain

$$a^2=2b^2.$$

Thus $a^2$ is even. From the parity result proved in the previous lesson,

$$a^2\text{ even}⟹a\text{ even}.$$

Therefore there exists an integer $k$ such that

$$a=2k.$$

Substitute this into $a^2=2b^2$:

$$(2k{)}^2=2b^2.$$

Hence

$$4k^2=2b^2,$$

so, after dividing by $2$,

$$b^2=2k^2.$$

Thus $b^2$ is even, and therefore $b$ is even as well.

We have shown that $2$ divides both $a$ and $b$. But this contradicts the assumption that

$$\gcd (a,b)=1.$$

Therefore the supposition that $\sqrt{2}$ is rational is false. Hence $\sqrt{2}$ is irrational. $\square$

The contradiction does not simply restate the assumption in opposite language. It appears “far away” from the starting point: an alleged rational representation in lowest terms is forced to have a common divisor. That is one reason contradiction is powerful. It permits you to pursue consequences until a hidden incompatibility emerges.

Two details are essential:

• We chose a representation in lowest terms before beginning the algebra. Without that condition, finding that both $a$ and $b$ are even would not itself be contradictory.
• The earlier theorem that an even square has an even root did real work. Proof by contradiction does not replace established results; it creates a situation in which those results can be applied decisively.

---

Contradiction for an implication

For an implication

$$P⟹Q,$$

the statement fails only in one circumstance: $P$ is true and $Q$ is false. Therefore,

$$\neg (P⟹Q)$$

is logically equivalent to

$$P\wedge \neg Q.$$

This tells you exactly what to assume when proving an implication by contradiction: assume the hypothesis and assume the conclusion fails.

Consider the claim:

$$\text{If }3n+2\text{ is even, then }n\text{ is even.}$$

To prove this by contradiction, assume there is an integer $n$ for which the hypothesis holds but the conclusion does not.

Proof. Suppose, for the sake of contradiction, that there exists an integer $n$ such that $3n+2$ is even but $n$ is not even. Since $n$ is an integer and is not even, $n$ is odd. Thus there exists an integer $k$ with

$$n=2k+1.$$

Then

$$\begin{array}{rl}3n+2& =3(2k+1)+2\\ & =6k+5\\ & =2(3k+2)+1.\end{array}$$

So $3n+2$ is odd. But our assumption said that $3n+2$ is even. This is a contradiction.

Therefore no such integer $n$ exists. Hence, if $3n+2$ is even, then $n$ is even. $\square$

This example sits near the boundary between contradiction and contraposition. A contraposition proof would assume that $n$ is odd and prove that $3n+2$ is odd. The algebra is the same. The distinction is in the proof’s logical setup:

Method	What you assume	What you establish
Direct proof	$P$	$Q$
Contraposition	$\neg Q$	$\neg P$
Contradiction	$P\wedge \neg Q$	An impossibility

In many elementary parity problems, either contraposition or contradiction works. As proofs become more sophisticated, contradiction often becomes preferable because the contradiction may involve a new property that is neither $\neg P$ nor $\neg Q$, as in the reduced-fraction contradiction for $\sqrt{2}$.

---

Choosing the method and writing it reliably

The decision chart captures an important initial distinction: a universal claim that is false is disproved by one valid counterexample, whereas a true universal claim requires proof. Once you have decided to prove a statement, choice of method is strategic rather than mechanical.

Contradiction is especially promising when:

• the claim says that no object with certain properties exists;
• the negation gives a useful witness, such as a particular integer, fraction, graph, or solution;
• assuming the opposite creates two conditions that seem incompatible;
• a “minimal,” “largest,” or “lowest terms” choice is likely to be undermined by the consequences of the assumption.

Before finalizing a proof by contradiction, check these points.

1. Negate the whole target statement.
   If the target is an implication, include both the hypothesis and the failure of the conclusion. If the target says “there exists,” its negation says “for every”; if it says “for every,” its negation says “there exists.”

2. State the assumption explicitly.
   Do not merely write “Suppose not.” Your reader should know precisely what “not” means in the present context.

3. Use definitions rather than intuition.
   In the parity proof, “even” became $2a$, and “odd” became $2b+1$. In the irrationality proof, “rational” became a reduced quotient $a/b$.

4. Name the contradiction.
   Write why the final outcome is impossible: perhaps an integer is both even and odd, or two supposedly coprime integers are both divisible by $2$.

5. Reject only the temporary assumption.
   The conclusion is not “we found something false,” but rather “the negation of the theorem cannot hold; therefore the theorem holds.”

A contradiction proof is not an invitation to assume whatever is convenient. Its rigor comes from assuming exactly the negation of the target, then ensuring every subsequent step follows validly.

---

Key takeaways

To prove a statement $S$ by contradiction:

$$\text{assume }\neg S,$$

derive an impossibility, and conclude that $S$ is true.

For an implication,

$$P⟹Q,$$

a contradiction proof assumes

$$P\wedge \neg Q.$$

The proof that no integer is both even and odd illustrated how contradictory definitions can force an algebraic impossibility. The proof that $\sqrt{2}$ is irrational showed a more substantial pattern: assume a carefully normalized object exists, then prove that it violates its own defining condition.

Next, you will turn to mathematical induction, a method designed for proving infinitely many statements indexed by the positive integers.