Proof by contradiction

What you’ll learn

• Construct a proof by assuming the negation of the required result.
• Identify the precise contradiction and close the argument.

Understand the idea

A contradiction proof begins by assuming the desired conclusion is false. Follow that assumption through valid deductions until it conflicts with a known fact or with the assumption itself. The impossible consequence means the initial negation cannot hold, so the original statement is true.

For irrationality proofs, assume the number is a fraction $p/q$ in lowest terms, with integer numerator and non-zero denominator. A common strategy forces both numerator and denominator to share a factor. For infinitely-many-primes arguments, assume a complete finite list and construct a number whose prime divisors cannot be on that list.

Key formulae

$$\neg P\Rightarrow\bot\quad\Longrightarrow\quad P$$

$$\gcd(p,q)=1\quad\text{for a fraction in lowest terms}$$

$$N=p_1p_2\cdots p_n+1\Rightarrow N\equiv1\pmod{p_i}$$

Worked example

Prove that $\sqrt3$ is irrational. You may use the fact that $3\mid n^2$ implies $3\mid n$.

1. Assume $\sqrt3=p/q$ in lowest terms, with integers $p,q$ and $q\ne0$.
2. Squaring gives $p^2=3q^2$, so $3$ divides $p$. Write $p=3k$.
3. Then $9k^2=3q^2$, so $q^2=3k^2$ and $3$ also divides $q$.
4. This contradicts the assumption that p and q have no common factor.

Answer: Therefore $\sqrt3$ is irrational.