P4 1.1 - Proof by contradiction

Proof by contradiction

To prove a statement by contradiction, assume its negation, derive a consequence that conflicts with a known fact or an assumption, and conclude that the negation is impossible. Therefore the original statement is true.

Worked example 1: an even square

Prove by contradiction that if $n^2$ is even, then the integer $n$ is even.

Plan. Keep the even-square assumption and suppose that $n$ is odd.

Assume $n^2$ is even but $n=2k+1$, where $k$ is an integer. Then

The bracket is an integer, so $n^2$ is odd, contradicting its assumed evenness.

Answer. The assumption that $n$ is odd is impossible; therefore $n$ is even.

Check. The contradiction concerns the same quantity, $n^2$: it was assumed even and proved odd. No special value of $n$ was used, so the argument covers every integer satisfying the premise.

Worked example 2: an odd square

Prove by contradiction that if $n^2$ is odd, then the integer $n$ is odd.

Plan. Assume the square is odd but the integer is even, then calculate the square's parity.

Assume $n^2$ is odd and $n=2k$ for an integer $k$. Then

which is even. This contradicts the assumption that $n^2$ is odd.

Answer. $n$ cannot be even; hence it is odd.

Check. Every integer that is not odd is even, so the assumed case was the complete negation of the conclusion. The algebra establishes a conflict with the retained premise.

Watch out

To prove “if $P$, then $Q$”, do not assume “not $P$ and $Q$”. That describes a different situation. In Example 1 the contradictory assumption is “$n^2$ even and $n$ odd”.

Coprime integers

Integers $a,b$ are coprime if their only common positive factor is $1$. A fraction in lowest terms has coprime numerator and denominator. If both were even, $2$ would be a common factor, contradicting that choice.

Worked example 3: irrationality of square root of two

Prove by contradiction that $\sqrt2$ is irrational.

Plan. Assume a lowest-terms rational representation, square it, and use parity to force a common factor.

Assume $\sqrt2=a/b$, with positive coprime integers $a,b$. Squaring gives

Thus $a^2$ is even, so $a$ is even. Write $a=2k$, for an integer $k$. Substituting gives

So $b^2$, and hence $b$, is even too. Then $a,b$ have the common factor $2$, contradicting their being coprime.

Answer. A rational representation is impossible, so $\sqrt2$ is irrational.

Check. The contradiction requires both numbers to be even. One even numerator would not conflict with a fraction being in lowest terms. Every parity step follows from an exact integer equation, not a decimal approximation.

Worked example 4: adapting the parity argument

Prove by contradiction that $\sqrt{2/3}$ is irrational.

Plan. Assume a coprime fraction, clear the denominator, and again force both integers to be even.

Assume $\sqrt{2/3}=a/b$, with positive coprime integers $a,b$. Then

The right side is even. Since $3$ is odd, $a^2$ must be even: an odd $a^2$ would make $3a^2$ odd. Hence $a=2k$, for an integer $k$, and

Thus $b$ is even as well, contradicting coprimality.

Answer. $\sqrt{2/3}$ is irrational.

Check. The critical odd-factor step can be checked algebraically: if $a=2j+1$, then $3a^2=12j^2+12j+3=2(6j^2+6j+1)+1$, which is odd. It therefore cannot equal the even integer $2b^2$. The proof does not assume irrationality of another root.

Watch out

“The numerator and denominator are even” is possible for an unreduced fraction, such as $2/4$. State coprimality at the start; otherwise you have not explained why evenness is impossible.