proof by contradiction – JDM Educational

Proof by contradiction is useful for proving statements by assuming the opposite. This assumption gives us an equation, inequality, or statement to work with to derive the contradiction. So, what is proof by contradiction? Proof by contradiction has 3 steps: 1. Write out your assumptions in the problem, 2. Make a claim that is the opposite of what you want to prove, and 3. Use this claim to derive a contradiction to your original assumptions (a contradiction is something that cannot be true, given what we assumed). Of course, we don’t need to use proof by contradiction (an indirect method of proof) for every theorem. For some statements, we can use a direct proof, such as proof by induction. In this article, we’ll talk about proof by contradiction, what it is, and how it works. We’ll also look at some examples to make the concept clear. Let’s get started. What Is Proof By Contradiction? Proof by contradiction is an indirect method of proof. With a proof by contradiction, we assume the opposite of what we want to prove. In turn, this assumption leads to a statement that contradicts what we already know to be true. For example, your friend is either at home or not at home. If you assume that he is at home, this might lead you to go to his house. If you find nobody there, then you know that your initial assumption was incorrect. So, your friend is not at home. Why Does Proof By Contradiction Work? Proof by contradiction works because we are splitting a situation into two possible cases: 1. the one we want to prove, and 2. the alternative. In other words, if the only two possibilities are A or B, and we disprove A, then we know B must be true. For example, for any natural number N, we know that N is either even or odd. This is because: the even numbers are integer multiples of 2 (such as 2, 4, 6, 8, etc.), andthe odd number are the rest of the whole numbers (such as 1, 3, 5, 7, etc.) So, if you can prove that a whole number is not even, then you know it is odd. Likewise, if you can prove that a whole number is not odd, then you know it is even. Every integer is either even or odd (a multiple of 2 or not). When To Use Proof By Contradiction Proof by contradiction is useful when direct methods (such as mathematical induction) will not work. Proof by contradiction is useful because it can give you an equation, inequality, or statement that you can use to help you prove something (by deriving a contradiction). We will see some examples in the proofs by contradiction that follow. What Is An Example Of Proof By Contradiction? Some examples of statements where we can use proof by contradiction include: N Is Odd If N2 Is OddThere Are Infinitely Many Prime Numbers√2 Is Irrational Example 1: Proof By Contradiction That N Is Odd If N2 Is Odd Remember that every whole number is either even or odd. So, if we can show that a whole number is not even, then it must be odd. If we can prove that N cannot be even when N2 is odd, then we know it falls into the second category: the set of odd numbers. To show this, use proof by contradiction to assume the opposite: that N is even if N2 is odd. In that case, we can write: N = 2K [our assumption, which we want to prove false] where K is a whole number. Now that we have an equation to work with, let’s begin to derive a contradiction: N = 2K [our assumption]N2 = (2K)2 [square both sides of the equation]N2 = 4K2N2 = 2(2K2) [4 = 2*2] From the equation in this last line, we can see that N2 is even (K is an integer, so K2 is also an integer, as is 2K2 and 2 times an integer is an even number). However, this contradicts our initial statement that N2 was odd. So, it cannot be true that N is even when N2 is odd. Thus, N is even whenever N2 is even. Example 2: Proof By Contradiction That √2 Is Irrational Remember that every real number is either rational or irrational. Since √2 is a real number, it must either be rational or irrational. If we can prove that √2 is not a rational number, then we know it falls into the second category: the set of irrational numbers. To show this, use proof by contradiction to assume the opposite: that √2 is rational. In that case, we can write: √2 = p / q [our assumption, which we want to prove false] Where p and q are integers, with q nonzero and p / q reduced as much as possible. That is, gcd(p, q) = 1 (p and q share no common factors). Now that we have an equation to work with, let’s begin to derive a contradiction: √2 = p / q [our assumption](√2)2 = (p / q)2 [square both sides of the equation]2 = p2 / q22q2 = p2 [multiply by q2 on both sides to clear the denominator] From the equation in this last line, we can see that p2 is even (q is an integer, so q2 is also an integer, and 2 times an integer is an even number). Since p2 is even, this also means that p is even (remember: if p2 is odd, then p is odd, which we proved in Example 1 above). Now that we know that p is even, we can write the equation: p = 2m for some integer m. Substituting this equation for p into our equation relating p and q gives us: 2q2 = p2 [the equation we derived above]2q2 = (2m)2 [since p = 2m]2q2 = 4m2q2 = 2m2 [divide by 2 on both sides] From the equation in this last line, we can see that q2 is even (m is an integer, so m2 is also an integer, and 2 times an integer is an even number). Since q2 is even, this also means that q is even (remember: if q2 is odd, then q is odd, which we proved in Example 1 above). Now that we know that q is even, we can write the equation: q = 2n for some integer n. However, this contradicts our initial statement that p / q was reduced as much as possible. In particular, p and q share a common factor of 2 (since they are both even): p / q = 2m / 2n = m / n So, it cannot be true that √2 is rational. Thus, √2 is irrational. Example 3: Proof By Contradiction That There Are Infinitely Many Prime Numbers There are infinitely many prime numbers. That is, no matter how many prime numbers we write out in a list, we can always find more to add to the list. Every whole number is either prime or composite. There are infinitely many numbers in both sets. To show this, we will use proof by contradiction. First, assume that there are only finitely many prime numbers (let’s say there are N of them), and write them in a list, labeling them with subscripts from 1 to N: p1, p2, … , pN [this is the list of all prime numbers] Then, take the product P of all of the prime numbers on our list (all N of them): P = p1 x p2 x … x pN Finally, add 1 to this number to get a total of P + 1 (which is just another positive integer). Since P is a product of every prime number in our list, then P + 1 is larger than any number on the list. Thus, P + 1 is not on the list, and so it is not prime. Since P + 1 is not prime, it must be composite. Therefore, P + 1 is the product of some of the prime numbers from our list. This means that there must be some prime number pi in our list so that P + 1 divided by pi has a zero remainder. However, P + 1 divided by any prime in our list will have a remainder of 1, since: (P + 1) / p1 = (p1 x p2 x … x pN + 1) / p1 = p2 x … x pN + 1 / p1(P + 1) / p2 = (p1 x p2 x … x pN + 1) / p2 = p1 x p3 x … x pN + 1 / p2…(P + 1) / pN = (p1 x p2 x … x pN + 1) / pN = p1 x p2 x … x pN-1 + 1 / pN No matter which prime pi we divide by, we always get a remainder of 1. So, P + 1 is not divisible by any prime number pi on our list. This implies that either: P + 1 is prime, which is a contradiction (we said P + 1 is not prime, since it is not on the list), orP + 1 is composite and is a product of other primes that were not on our list, which is also a contradiction (we said our list contained all of the possible prime numbers). Due to this contradiction, we conclude that there is no such finite list of prime numbers. So, there must be infinitely many prime numbers. Thus, we can never run out of primes. Note: due to the Fundamental Theorem of Arithmetic, it is also true that every integer greater than 1 is either prime or has a unique prime factorization. That means that there is only one combination of prime numbers (raised to the proper powers) that will result in a given integer product. Conclusion Now you know a little more about proof by contradiction, what it means, and how it works. You also have some examples to work with so that you can try writing some proofs of your own. I hope you found this article helpful. If so, please share it with someone who can use the information. Don’t forget to subscribe to my YouTube channel & get updates on new math videos! ~Jonathon