Mathematics
Proof by Contradiction
Proof by contradiction is a method used in mathematics to establish the truth of a statement by assuming the opposite and then deriving a contradiction. It involves assuming the negation of what needs to be proved and then showing that this assumption leads to a logical inconsistency. This contradiction then proves the original statement to be true.
Written by Perlego with AI-assistance
Related key terms
1 of 5
7 Key excerpts on "Proof by Contradiction"
eBook - PDFDiscrete Mathematics
Mathematical Reasoning and Proof with Puzzles, Patterns, and Games
- Douglas E. Ensley, J. Winston Crawley(Authors)
- 2011(Publication Date)
- Wiley(Publisher)
140 Chapter 2 / A Primer of Mathematical Writing More Classic Proofs by Contradiction In Book IX of Euclid’s Elements, a series of proofs about prime numbers is given. ∗ In Greek mathematics all numbers represent geometric measurements, so it is fairly interesting that the notion of “prime number” was considered important at all. The following classic example of using “Proof by Contradiction” is Proposition 20 in Book IX of the Elements. Theorem 6 There are an infinite number of prime numbers. PROOF Suppose to the contrary that there are only a finite number of prime numbers. Then we can form the number x by multiplying all the primes together. Even though x is a large number, it will be evenly divisible by every prime num- ber. This means that the number x + 1 will leave a remainder of 1 when divided by any prime number. Hence, we have produced a number that is not divisi- ble by any prime number. This is a contradiction to the fundamental theorem of arithmetic (Theorem 1 in the previous section) that follows deductively from the assumption that there are only finitely many prime numbers. Hence, that as- sumption must be false, which means that there are, in fact, infinitely many prime numbers. There is a specific kind of Proof by Contradiction that is related to mathematical induction. Since we have already devoted two sections to mathematical induction, we will not discuss it much more here. We will just note that another way to express the principle of mathematical induction is to state that any nonempty set of positive integers will always have a smallest number in the set. This fact is called the well- ordering principle of the set of positive integers, and it is used in the following proof of a property that is fundamental to the study of number theory. Theorem 7 For integers a and b, define the set S a,b to be the set of all integers of the form au + bv, where u, v ∈ Z.
eBook - PDF- Charles Roberts(Author)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
The advantage of a Proof by Contradiction is that the statement R may be any statement whatsoever. However, when actually developing the proof, the disadvantage is not knowing in advance what statement R to select to produce the desired contradiction. The following example illustrates proving a theorem by the technique of contradiction. Deductive Mathematical Systems and Proofs 77 Example 2.2.1.5 Prove the following theorem by the method of contradic-tion. Theorem 2.11 Let n be an integer. If n 2 is an odd integer, then n is an odd integer. Solution Proof: Let P denote the statement “ n 2 is an odd integer” and let Q de-note the statement “ n is an odd integer.” We will prove this theorem by contradiction. Therefore, we assume P and ¬ Q. The negation of the state-ment Q is “ n is an even integer.” Thus, there is an integer k such that n = 2 k . Squaring and using the associative property of multiplication, we find n 2 = (2 k )(2 k ) = 2( k (2 k )) = 2 p where p = k (2 k ). Since the integers are closed under multiplication, p is an integer, and, consequently, n 2 is an even integer. The statement “ n 2 is an even integer” is the statement ¬ P. Thus, we assumed the statements P and ¬ Q are true and we deduced that the statement ¬ P is true. Hence, we reached the contradiction P ∧ ( ¬ P). Consequently, we have proven Theorem 2.11 by contradiction. Remark: Observe in this case that the statement R in the contradiction R ∧ ( ¬ R) is the hypothesis P. Although a direct proof, a proof by contraposition, and a proof by con-tradiction are all acceptable forms of proof, most mathematicians, order of preference for a proof is a direct proof, followed by a proof by contraposition, followed by a Proof by Contradiction. In the following example, the same statement is proven using each type of proof. Example 2.2.1.6 Prove the following theorem by (a) a direct proof, (b) a proof by contraposition, and (c) a Proof by Contradiction.
eBook - PDF- Scott A. Taylor(Author)
- 2023(Publication Date)
- American Mathematical Society(Publisher)
Since 2 is one more than an even number, it is not even by Lemma 4.1. Hence, if is not even, then 2 is not even, as desired. □ 4.3. Proof by Contradiction I make many more [errors] than my students do; only I always correct them so that no trace of them remains in the final result. ... Insight ... warns me that my calculations do not look as they ought to. —Jacques Hadamard 4 A Proof by Contradiction (or reductio ad absurdum) begins by asserting the nega- tion of what is to be proved, and then shows that the assumption produces a logical contradiction. Since the negation cannot be true, the statement itself must be true. 5 The mathematician G.H. Hardy, 6 described a Proof by Contradiction as “one of a math- ematician’s finest weapons”. He says “a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game”. Personally, I like a Proof by Contradiction, because it forces me to ask myself, “What if what I believe is wrong?” It gives me the opportunity to test the validity of my beliefs. A Proof by Contradiction should always begin by saying what kind of proof it is. Proof by Contradiction To show: is true. Structure of Proof: We prove the statement by contradiction and so assume that is false. ⟨ Sequence of tightly reasoned statements, each following from what has already been done and concluding with a contradiction. ⟩ Since we have encountered a contradiction, cannot be false. Hence, is true. □ Here is are two famous examples. For the first example we need the definition of prime number and a fact whose proof will be deferred. A number ∈ ℕ is prime if ≠ 1 and if whenever is a multiple of some ∈ ℕ, either = 1 or = . The fact 4 Jacques Hadamard (1865–1963) was an influential mathematician and campaigner for world peace. This quotation is from his book The Psychology of Invention in the Mathematical Field, Princeton University Press, 1945.
eBook - PDFDiscrete Mathematics
Proof Techniques and Mathematical Structures
- R C Penner(Author)
- 1999(Publication Date)
- WSPC(Publisher)
An amazing fact is that despite this lack of intellectual common ground, the reader and Pythagoras would agree on the fact that every triangle inscribes in a circle or on the verity of Pythagoras' Theorem itself. This perpetuity of mathematics is truly remarkable. B.2 Proof by Contradiction This subsection is dedicated to a discussion of the following method of proof. P R O O F BY CONTRADICTION To prove the implication P =» Q, assume that P is true, assume that ->Q is true, and prove that something a priori known to be true is false. That is, assume that we already know that some proposition R is true, and prove the implication (P A ->Q) => -iR. The logic of this method requires recalling from the definition of =£► that P => Q is false only when P is true and Q is false. Thus, P => Q is true unless these truth values are correct, so we must show that these truth values cannot be correct, B.2 Proof by Contradiction 33 that is, we must show that P A -Q does actually have truth value 1 and derive from this assumption that some proposition R is false, where R is already known to be true for some reason. The proof that R is false might, for instance, involve a chain of implications starting with P A ->Q and ending with -uR. The assumption P A ->Q therefore leads to the contradiction that R is true and -uR is true, which is impossible according to our definition of proposition. Thus, our assumption cannot have been correct, so it cannot be that P A -iQ has truth value 1, that is, P => Q cannot be false, so P => Q is true. The tricky point about a Proof by Contradiction is that we must find the proposition R. In some examples, the proposition R might be -uP (or it might be Q), and since we assume P (and we assume ->Q), R is indeed a priori false by assumption. In other examples, R amounts to a convention which arises in the course of proving that (P A ->Q) => -*R.
eBook - PDF- Daniel Ashlock, Colin Lee(Authors)
- 2022(Publication Date)
- Springer(Publisher)
Proof by Contradiction rests on the fact that after the initial assumption of the negation of the claim that we can logically arrive at a contradiction (usually of the form P ^ :P for some propo- sition P ). In the examples the contradictions were that 1 is greater than itself and that 1 is both an even and an odd number. 4.3 DIRECT PROOF Direct proofs are also sometimes called constructive proofs or proof by construction. A di- rect proof is simply a series of deductions that lead from the antecedent of the implication to 42 4. MATHEMATICAL PROOFS the consequent. That is all. Perhaps there are some tricky calculations, or a jumble of algebra to unscramble, but in a direct proof you assume all of the premises in the antecedent of your implication are true then demonstrate in a stepwise fashion that the conclusion must also be true. Generally this is done by carefully unpacking definitions. Example 4.6 Claim: The sum of two even numbers is an even number. Proof: Let m and n be any two even numbers. Then since m is even there exists an integer k such that m D 2k, likewise there exists an integer j such that n D 2j . Note that m C n D .2k/ C .2j / thus, m C n D 2.k C j /. Since m C n is a multiple of 2 it is an even number. Let us examine the proof. We first unpack the claim as an implication, “the sum of two even numbers is an even number” becomes “if m and n are even numbers then their sum m C n is an even number.” We assume the initial assumption (that we have two even numbers). The definitions are unpacked. The definitions are applied to the initial assumption. This leads to some algebra or calculation or other logically acceptable manipulation until it becomes clear that the conclusion is satisfied. We then for good measure specify that the conclusion is satisfied. This is the basic idea behind (most) direct proofs. Example 4.7 Claim: Using a 5-card poker hand from a standard pack of 52 cards.
eBook - PDF- Valentin Deaconu, Donald C. Pfaff(Authors)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
The typical daily project in mathematics is to discover a consequence of one or more hypotheses and, hopefully, to prove it. In practice, that’s what mathematics is all about. In this chapter, we discuss different methods of proofs, illustrating the rules of logic that we have learned in the previous chapter. We begin with the concepts of axiom, theorem, proof, and conjecture. We will discuss several examples of direct proofs, indirect proofs, and proofs by contradiction. We also illustrate proofs by cases, existence proofs, proofs by counterexample, and proofs by mathematical induction. More examples of proofs will appear in the subsequent chapters, after new concepts are introduced. 15 16 A bridge to higher mathematics 2.1 Axioms, theorems and proofs In constructing a mathematical theory, we often start with some statements called axioms or postulates which are accepted to be true, and using valid rules of logic we prove new true statements, the theorems. In the process, we may have to prove auxiliary results, called lemmas. A direct consequence of a theorem is called a corollary. You already have applied the Pythagorean theorem in geometry or the fundamental theorem of calculus many times. A proof is a deductive argument and it may be based on previously established statements. A proof could be straightforward, by just doing a computation. For example, π 0 sin xdx = 2 is a true statement, and becomes a theorem after we compute the integral using the fundamental theorem of calculus, π 0 sin x dx = − cos x π 0 = − cos(π) + cos(0) = −(−1) + 1 = 2. The statement “A triangle with two congruent angles is isosceles” is a proposition which becomes a theorem after we prove that two sides of the triangle are congruent. Sometimes a proof can be long and complicated, requiring smart ideas and tricks, connecting several areas of mathematics. One way or another, a proof should be based on valid arguments.
eBook - PDFHow to Read and Do Proofs
An Introduction to Mathematical Thought Processes
- Daniel Solow(Author)
- 2013(Publication Date)
- Wiley(Publisher)
10.3 READING A PROOF 119 Analysis of Proof. An interpretation of statements S1 through S4 follows. Interpretation of S1: Suppose that x > 0 is an integer with ax 2 + bx + b - a = 0. The author is assuming NOT B; that is, A1 (NOT B): x > 0 is an integer with ax 2 + bx + b - a = 0. This means that the contradiction or contrapositive method is used. However, on reading S4, you see that the author reaches the statement NOT A: B1 (NOT A): a|b, thus indicating that this is a proof by the contrapositive method. Interpretation of S2: Then x = -b±(b-2a) 2a . The author works forward from A1 using the quadratic formula to obtain the following: A2: x = -b± √ b 2 -4a(b-a) 2a = -b±(b-2a) 2a . Interpretation of S3: Because x > 0, it must be that x = 1 - b a . The author works forward by algebra from A2 to see that the two roots are x = -1 and x = 1 - b a . Because, from A1, x > 0, the author rules out the root x = -1 and correctly concludes that A3: x = 1 - b a . Interpretation of S4: But then b = (1 - x)a and so a|b. The author works backward from B1 by asking the key question, “How can I show that an integer (namely, a) divides another integer (namely, b)?” Using the definition to answer the question, the author needs to show the following: B2: There is an integer c such that b = ca. Recognizing the quantifier “there is” in B2, the author uses the construction method to produce the value of c. Specifically, the author works forward from A3 by algebra to solve for b, obtaining b = (1 - x)a, from which the author notes—without mentioning—that the desired value of c in B2 is c = 1 - x. Having reached NOT A, the contrapositive method is now complete, and so is the proof. Summary The contrapositive method, being a type of Proof by Contradiction, is used when the last statement in the backward process contains the keyword “no” 120 CHAPTER 10: THE CONTRAPOSITIVE METHOD or “not.” With the contrapositive method, you work toward the specific contradiction NOT A by 1.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
