1.4c Proof by Contradiction

Proof by Contradiction

A proof by contradiction is a logical argument that establishes the truth of a given proposition $P$ by assuming the negation $\neg P$ and demonstrating that this assumption leads to a contradiction of two conclusions, $R$, thereby implying that $P$ must be true, such that
$\neg P⟹\neg R\wedge R.$

Examples

There are infinitely many prime numbers.

We proceed by contradiction. Assume there is a finite number of $k$ prime numbers, $p_1,p_2,\dots ,p_k$. Then, there is a numbeot be prime since it is larger than any prime number. Since every natural number greater than $1$ is either prime or has a prime divisor (proven in 2.5a), then there is a prime number $p\in \{p_1,\dots ,p_k\}$ such that $p\mid n$, which is our statement $R$.

However, by the same logic $p$ must also divide $r=p_1{p}_2{p}_3\dots p_n$. Then, as proven in 2.1, $p\mid n-r$. But $n-r=1$! Since the only positive number that divides $1$ is $1$, $p=1$ is not prime. This is our statement $\neg R$.

Since we have proven $R\wedge \neg R$, we have a contradiction!

$\sqrt{2}$ is irrational.

We proceed by contradiction. Assume that $\sqrt{2}$ is rational. By the definition of rational numbers, there exist some $a,b\in \mathbb{Z}$ with no common factors other than $1$ for which $\sqrt{2}=\frac{a}{b}$ (this is our $R$).

It follows that $2=\frac{a^2}{b^2}⟺a^2=2b^2$. Since $2b^2$ is a multiple of $2$, it is even, and so is $a^2$. This means that $a$, too, is even (proven in 2.2). Hence, there is some $q\in \mathbb{Z}$ for which $a=2q$. We have that $b^2=2q^2$. Since $q$ is an integer, so is $q^2$, and since $b^2$ is even, so is $b$. As such, both $a$ and $b$ are even.

However, if $a$ and $b$ are even, then they share a common factor of $2>1$. This is our statement $\neg R$, and we have a contradiction since $\neg R\wedge R$ holds.