Jump to a key chapter
How to carry out proof by contradiction
To make this process clearer, let's think about the steps to achieve proof by contradiction:
Step 1: Take the statement, and assume that the contrary is true (i.e. assume the statement is false).
Step 2: Start an argument from the assumed statement and work it towards the conclusion.
Step 3: While doing so, you should reach a contradiction. This means that this alternative statement is false, and thus we can conclude that the original statement is true.
This may look tricky, so we will now look through some examples to get your head around this concept. These types of questions could all be in an exam, so it is important you are familiar with the style.
Proof by contradiction examples
Example 1: Proof of an infinite amount of prime numbers
Prove by contradiction that there are an infinite amount of primes.
Solution:
The first step is to assume the statement is false, that the number of primes is finite. Let's say that there are only n prime numbers, and label these from p1 to pn.
If there are infinite prime numbers, then any number should be divisible by at least one of these numbers.
Construct P, where we multiply all the prime numbers together and add 1, see above \(P = p_1p_2 ... p_n +1\). We then see that no prime will divide this number, as each of the primes divides P-1, and for a number to divide both P and P-1, the only possibility is one, which isn't prime. This means that P is a prime number, and as \(P > p_i \text{ for all } p_i\), this means there is a new prime, which means we now have a contradiction. This means that there must be an infinite number of prime numbers. QED
Example 2: Proof that 2 is irrational
Prove by contradiction that \(\sqrt{2}\) is irrational.
Solution:
Let us assume that \(\sqrt{2}\) is rational. This means that we can write \(\sqrt{2} = \frac{a}{b}\), with \(a, b \in \mathbb{Z}, b ≠ 0, gcd (a, b) = 1\). (Note - gcd stands for greatest common divisor). This means that \(\frac{a}{b}\) is a fraction in its lowest terms. Note here that this means that a and b cannot both be even, as then we would be able to cancel a factor of 2.
If \(\sqrt2 = \frac{a}{b}\), then \(2 = \frac{a^2}{b^2}\), which rearranges to \(a^2 = 2b^2\). This means that a² is even, which implies that a is also even.
(This above claim is easily verified. If a number is even, we can write it as 2k, with k as an integer. This squared equals 4k², which is also even. If a number is odd, then we can write it as \(2k + 1. (2k + 1)^2 = 4k^2 + 4k + 1 = 2 (2k^2 + 2k) +1\), which is odd. Thus, if a² is even, then so must be a.)
This means we can replace a with 2c, as a must be even. The value of c is unimportant, but it must be an integer.
Then, if \(a^2 = 2b^2\), we have \(4c^2 = 2b^2 \Rightarrow b^2 = 2c^2\). Following the same argument as above, this means b² is even, and in turn, b is even. Thus, we can write \(b = 2d, d \in \mathbb{z}\). This means that gcd (a, b) = gcd (2c, 2d) ≠ 1. (As the gcd will be a minimum of 2). This means there will not be a fraction in its lowest terms, and thus a contradiction.
We can now conclude that \(\sqrt2\) is irrational. QED
Example 3:
Prove there are no integers a and b such that
\(10a + 15b = 1\).
Solution:
Let us assume that we could find integers a and b that satisfy such an equation. We can then divide both sides by 5 to give \(2a + 3b = \frac{1}{5}\). If a and b are integers, and we multiply each by another integer (2 and 3 respectively, in this case), then sum them, there is no possible way that this could result in being a fraction, which is what the above condition requires. This leads us to a contradiction.
Thus, there are no integers a and b such that \(10a + 15b = 1\).
Example 4:
Use proof by contradiction to show that the sum of a rational number and an irrational number is irrational.
Solution:
Let us assume the sum of a rational number and an irrational number is rational. Let the rational number be denoted by a, and the irrational number denoted by b, and their sum is denoted by a + b. As a is rational, we can write it as \(a = \frac{c}{d}\), where d ≠ 0, and d and c integers, in the lowest possible terms. As a + b is rational, we can write \(a + b = \frac{e}{f}\), e, f ∈ ℤ, f ≠ 0, and the fraction in its lowest terms. Then we can write \(\frac{c}{d} + b = \frac{e}{f}\). This implies \(b= \frac{e}{f}-\frac{c}{d} = \frac{de-cf}{fd}\). As \(de-cf\) is an integer, and fd is also an integer, this implies that b would be able to be written as a rational number, which is a contradiction. Thus, the sum of a rational number and an irrational number is irrational.
Proof by contradiction - key takeaways
The steps for a proof by contradiction are:
Step 1: Take the statement, and assume that the contrary is true (i.e. assume the statement is false).
Step 2: Start an argument from the assumed statement and work it towards the conclusion.Step 3: While doing so, you should reach a contradiction. This means that this alternative statement is false, and thus we can conclude that the original statement is true.
The statement we are trying to prove must have only two possible outcomes.
Proof by contradiction is based on the logic that if the converse of a statement is always false, then the statement is true.
Learn with 0 Proof by Contradiction flashcards in the free StudySmarter app
We have 14,000 flashcards about Dynamic Landscapes.
Already have an account? Log in
Frequently Asked Questions about Proof by Contradiction
What is proof by contradiction?
Proof by contradiction is where we assume the negation of a statement, and then follow the logical steps to find a contradiction.
When do you use proof by contradiction?
Use proof by contradiction when it is difficult or impossible to prove a claim directly, but the converse case is easier to prove.
How do you do proof by contradiction?
Step 1: Take the statement, and assume that the contrary is true (i.e. assume the statement is false).
Step 2: Start an argument, starting from the assumed statement, and try to work towards the conclusion.
Step 3: While doing so, you should reach a contradiction. This means that this alternative statement is false, and thus we can conclude that the original statement is true.
About StudySmarter
StudySmarter is a globally recognized educational technology company, offering a holistic learning platform designed for students of all ages and educational levels. Our platform provides learning support for a wide range of subjects, including STEM, Social Sciences, and Languages and also helps students to successfully master various tests and exams worldwide, such as GCSE, A Level, SAT, ACT, Abitur, and more. We offer an extensive library of learning materials, including interactive flashcards, comprehensive textbook solutions, and detailed explanations. The cutting-edge technology and tools we provide help students create their own learning materials. StudySmarter’s content is not only expert-verified but also regularly updated to ensure accuracy and relevance.
Learn more