"...when you have eliminated the impossible, whatever remains, however improbable, must be the truth?" Sherlock Holmes in The Sign of the Four by Sir Arthur Conan Doyle. Holmes was a wonderful detective and he would also have been excellent at carrying out proofs by contradiction, as this is exactly the process we use. To complete a proof by contradiction, we start by assuming the opposite is true. If we show that the consequences of this are impossible, our original statement must be true. This is a challenging topic in the course. The page will prepare you well.
On this page, you should learn to
- Carry out proof by contradiction to show irrationality of roots, like \(\sqrt{3}\)
- Carry out proof by contradiction to show that there are an infinite number of primes
Print from here
Here is a quiz to prove that if the square of a positive integer is odd, the number is odd
Prove that if the square of a positive integer, n² is odd, then the number n is odd
This is a contradiction n² = 2(2k²) n = 2k, where k is an integer Hence, if n² is odd, then the number n is odd n² is even n is even n² = 4k²
Let n be a positive integer, where n² is odd
Assume the opposite, that
\(\implies\)
\(\implies\)
\(\implies\)
\(\implies\)
You could carry out this proof using a deductive proof, but if the exam question asks you to do a proof by contradiction, then you must do a proof by contradiction!
Here is a quiz to prove that \(\sqrt{5}\) is irrational
Complete the following to prove that \(\sqrt {5}\) is irrational
a is divisible by 5 a is divisible by 5 This is a contradiction 5b² = a² a² is divisible by 5 5b² = (5n)² b² = 5n² b is divisible by 5 a and b are divisible by 5
Assume that \(\sqrt {5}\) is rational
\(\sqrt {5}=\frac{a}{b}\quad a,b\in\mathbb{Z}, b\neq0\)
\(\implies\) \(5=\frac {a²}{b²}\)
\(\implies\)
\(\implies\)
\(\implies\)
\(\implies\) a = 5n
Substitute this in 5b² = a²
\(\implies\)
\(\implies\) 5b² = 25n²
\(\implies\)
\(\implies\) b² is divisible by 5
\(\implies\)
This means that both
\(\implies \frac{a}{b}\) has a common factor of 5
\(\implies \sqrt {5}\) is irrational
There are other ways to prove that \(\sqrt{5}\) is irrational, buut this technique is one that you can use for other roots of prime numbers. This quiz is something you can practise several times!
Here is a quiz to prove that there are infinitely many primes
Complete the following to prove that there are an infinite number of primes
be divided by p2, or p3, ... or pn
there are an infinite number of primes
(p1 x p2 x p3 x ...x pn) + 1
This is a contradiction that p1 , p2 , p3, ..., pn contains all the primes
p1 , p2 , p3, ..., pn
another prime or divisible by another prime not in our list of primes
by p1 (it leaves a remainder of 1)
finite number of primes
Assume that there are a
We can list all the primes:
Let N =
N cannot be divided
N cannot
N must be
\(\implies\)
Hence,
This is Euclid's classic proof. You should learn how to do this by heart.
a) Use a deductive proof to prove that even x even = even
b) Similarly prove that odd x odd = odd
c) Hence, use proof by contradiction to prove that \(log_25\) is irrational
Hint
Full Solution
Prove by contradiction that a rational number + an irrational number = irrational number.
Hint
Full Solution
Prove by contradiction that the length of the hypotenuse of a right-angled triangle is less than the sum of the other two sides.
Hint
Full Solution
How much of Proof by Contradiction have you understood?
Twitter 
Facebook 
LinkedIn