Skip to main content
Engineering LibreTexts

3.3: Proof by Contradiction

  • Page ID
    9674
  • A sequence of statements that can be proved from those assumptions, and suppose that we derive a statement that we know to be false. When the laws of logic are applied to true statements, the statements that are derived will also be true. If we derive a false statement by applying rules of logic to a set of assumptions, then at least one of the assumptions must be false. This observation leads to a powerful proof technique, which is known as proof by contradiction.

    Suppose that you want to prove some proposition, p. To apply proof by contradiction, assume that ¬is true, and apply the rules of logic to derive conclusions based on this assumption. If it is possible to derive a statement that is known to be false, it follows that the assumption, ¬p, must be false. (Of course, if the derivation is based on several assumptions, then you only know that at least one of the assumptions must be false.) The fact that ¬is false proves that is true. Essentially, you are arguing that must be true, because if it weren’t, then some statement that is known to be false could be proved to be true. Generally, the false statement that is derived in a proof by contradiction is of the form ∧ ¬q. This statement is a contradiction in the sense that it is false no matter what the value of q. Note that deriving the contradiction ∧ ¬is the same as showing that the two statements, and ¬q, both follow from the assumption that ¬p.

    As a first example of proof by contradiction, consider the following theorem:

    Theorem \(\PageIndex{1}\)

    The number \(\sqrt{3}\) is irrational.

    Proof

    Proof by contradiction:

    • Assume for the sake of contradiction that \(\sqrt{3}\) is rational.
    • Then \(\sqrt{3}\) can be written as the ratio of two integers, \(\sqrt{3}=\frac{m^{\prime}}{n^{\prime}}\) for some integers \(m^{\prime}\) and \(n^{\prime}\).
    • Furthermore, the fraction \(\frac{m^{\prime}}{n^{\prime}}\) can be reduced to lowest terms by canceling all common factors of \(m^{\prime}\) and \(n^{\prime} .\) So \(\sqrt{3}=\frac{m}{n}\) for some integers \(m\) and \(n\) which have no common factors.
    • Squaring both sides of this equation gives \(3=\frac{m^{2}}{n^{2}}\) and re-arranging gives \(3 n^{2}=m^{2}\)
    • From this equation we see that \(m^{2}\) is divisible by \(3 ;\) you proved in the previous section (Exercise 6\()\) that \(m^{2}\) is divisible by 3 iff \(m\) is divisible by \(3 .\) Therefore \(m\) is divisible by 3 and we can write = 3for some integer k.
    • Substituting \(m=3 k\) into the last equation above gives \(3 n^{2}=(3 k)^{2}\) or \(3 n^{2}=9 k^{2}\) which in turn becomes \(n^{2}=3 k^{2} .\) From this we see that \(n^{2}\) is divisible by \(3,\) and again we know that this implies that is divisible by 3.
    • But now we have (i) and have no common factors, and (ii) and have a common factor, namely 3. It is impossible for both these things to be true, yet our argument has been logically correct.

    • Therefore our original assumption, namely that \(\sqrt{3}\) is rational, must be incorrect.

    • Therefore \(\sqrt{3}\) must be irrational.

    \(\square\)

    One of the oldest mathematical proofs, which goes all the way back to Euclid, is a proof by contradiction. Recall that a prime number is an integer n, greater than 1, such that the only positive integers that evenly divide are 1 and n. We will show that there are infinitely many primes. Before we get to the theorem, we need a lemma. (A lemmais a theorem that is introduced only because it is needed in the proof of another theorem. Lemmas help to organize the proof of a major theorem into manageable chunks.)

    Lemma 3.2

    If N is an integer and N > 1, then there is a prime number which evenly divides N.

    Proof

    Let be the smallest integer which is greater than 1 and which evenly divides N. (exists since there is at least one number, namely itself, which is greater than 1 and which evenly divides N. We use the fact that any non-empty subset of N has a smallest member.) I claim that is prime, so that is a prime number that evenly divides N.

    Suppose that is not prime. We show that this assumption leads to a contradiction. Since is not prime, then, by definition, there is a number between 2 and − 1, inclusive, such that evenly divides D. But since evenly divides N, we also have that evenly divides (by exercise 5 in the previous section). That is, is an integer greater than one which evenly divides N. But since is less than D, this contradicts the fact that D is the smallest such number. This contradiction proves that is a prime number.

    \(\square\)

    Theorem 3.3

    There are infinitely many prime numbers.

    Proof

    Suppose that there are only finitely many prime numbers. We will show that this assumption leads to a contradiction. 

    Let \(p_{1}, p_{2}, \ldots, p_{n}\) be a complete list of all prime numbers (which exists under the assumption that there are only finitely many prime numbers). Consider the number Nobtained by multiplying all the prime numbers together and adding one. That is,

    \[N=\left(p_{1} \cdot p_{2} \cdot p_{3} \cdots p_{n}\right)+1 \nonumber\]

    Now, since \(N\) is larger than any of the prime numbers \(p_{i},\) and since \(p_{1}, p_{2}, \dots, p_{n}\) is a complete list of prime numbers, we know that cannot be prime. By the lemma, there is a prime number \(p\) which evenly divides \(N .\) Now, \(p\) must be one of the numbers \(p_{1}\), \(p_{2}, \ldots, p_{n} .\) But in fact, none of these numbers evenly divides \(N,\) since dividing \(N\) by any \(p_{i}\) leaves a remainder of \(1 .\) This contradiction proves that the assumption that there are only finitely many primes is false.

    \(\square\)

    This proof demonstrates the power of proof by contradiction. The fact that is proved here is not at all obvious, and yet it can be proved in just a few paragraphs.

    It is easy to get a proof by contradiction wrong however. In one of the pen- casts of this course we treat a commonly-made mistake when using proofs by contradiction: youtu.be/OqKvBWxanok.

    Exercises 

    1. Suppose that \(a_{1}, a_{2}, \dots, a_{10}\) are real numbers, and suppose that \(a_{1}+a_{2}+\cdots+a_{10}>100 .\) Use a proof by contradiction to conclude that at least one of the numbers \(a_{i}\) must be greater than 10 .

    1. Prove that each of the following statements is true. In each case, use a proof by contradiction. Remember that the negation of → is ∧ ¬q.

      1. a)  Let be an integer. If \(n^{2}\) is an even integer, then is an even integer.

      2. b)  \(\sqrt{2}\) is irrational.

      3. c)  If is a rational number and is an irrational number, then is an irrational number.

        (That is, the sum of a rational number and an irrational number is irrational.)

      4. d)  If is a non-zero rational number and is an irrational number, then rx is an irrational

        number.

      5. e)  If and are both rational, then is rational.

    2. The pigeonhole principle is the following obvious observation: If you have pigeons in pigeonholes and if k, then there is at least one pigeonhole that contains more than one pigeon. Even though this observation seems obvious, it’s a good idea to prove it. Prove the pigeonhole principle using a proof by contradiction.