Proof by Contradiction

Proof by contradiction – or the contradiction method – is different to other proofs you may have seen up to this point. Instead of proving that a statement is true, we assume that the statement is false, which leads to a contradiction. What this requires is a statement which can either be true or false. If it is not, then we cannot use proof by contradiction.

Get started

Millions of flashcards designed to help you ace your studies

Sign up for free

Review generated flashcards

Sign up for free
You have reached the daily AI limit

Start learning or create your own AI flashcards

StudySmarter Editorial Team

Team Proof by Contradiction Teachers

  • 6 minutes reading time
  • Checked by StudySmarter Editorial Team
Save Article Save Article
Contents
Contents
Table of contents

    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.

      Proof by Contradiction Proof by Contradiction
      Learn with 0 Proof by Contradiction flashcards in the free StudySmarter app

      We have 14,000 flashcards about Dynamic Landscapes.

      Sign up with Email

      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. 

      Save Article

      Discover learning materials with the free StudySmarter app

      Sign up for free
      1
      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
      StudySmarter Editorial Team

      Team Math Teachers

      • 6 minutes reading time
      • Checked by StudySmarter Editorial Team
      Save Explanation Save Explanation

      Study anywhere. Anytime.Across all devices.

      Sign-up for free

      Sign up to highlight and take notes. It’s 100% free.

      Join over 22 million students in learning with our StudySmarter App

      The first learning app that truly has everything you need to ace your exams in one place

      • Flashcards & Quizzes
      • AI Study Assistant
      • Study Planner
      • Mock-Exams
      • Smart Note-Taking
      Join over 22 million students in learning with our StudySmarter App
      Sign up with Email