Proof by Contradiction: A Key Technique in Mathematical Thinking

Introduction to Mathematical Thinking. PROOF BY CONTRADICTION 1. You want to prove some statement ϕ 2. You start by assuming ¬ϕ 3. You reason until you reach a conclusion that is false/ - often by deductity both ψ 𝑎𝑛𝑑 ¬ψ 𝑓𝑜𝑟𝑚 𝑠𝑜𝑚𝑒 ψ. reg “ p,q have no common factors “ and “ p,q are both-even “ 4. A true assumption cannot lead to a false conclusion.5. Hence the assumption must be false. ¬ϕ 6. In other words, must be true. ϕ Prove that is irrational. 3 The main goal of this course is to learn how to think a certain way - it is not aboutgetting answers. Proof by contradiction is a good way to prove that something does not exist. Proving conditionals We want to prove a conditional ϕ ⇒ ψ. We know this is true if , is false, so we can assume is true. ϕ ϕ To prove it, we assume , and deduce . ϕ ψ For example, let x, y be variable for real numbers, and prove: [ x,y are rational ] [ x+y is rational ] ⇒ – Assume x,y are rational. Then there are p,q,n,m such that x=p/m, y=q/n.

Then 𝑥 + 𝑦 = 𝑝 𝑚 + 𝑞𝑛 = 𝑝𝑛+𝑞𝑚 𝑚𝑛 – Hence x+y is rational. Conditionals involving quantifiers are sometimes best handled by proving thecontrapositive. He is contrapositive. To prove , prove ϕ ⇒ ψ (¬ψ) ⇒ (¬ϕ) To prove: (𝑠𝑖𝑛Θ ≠ 0) ⇒ (∀𝑛ϵ𝑁)(Θ ≠ 𝑛π) The statement is equipment to: ¬(∀𝐴ϵ𝑁)(Θ ≠ 𝑛π) ⇒ ¬(𝑠𝑖𝑛Θ ≠ 0) In positive form: (∃𝑛ϵ𝑁)(Θ = 𝑛π) ⇒ (𝑠𝑖𝑛Θ = 0) We know this is true! This proves the desired result.The prove a biconditional , we generally constant two proofs, are of ϕ ⇔ ψ ϕ ⇒ ψ, 𝑡ℎ𝑒 𝑜𝑡ℎ𝑒𝑟 𝑜𝑓 ψ ⇒ ϕ Occasionally, it is easier to prove the two conditional. ϕ ⇒ ψ 𝑎𝑛𝑑 (¬ϕ) ⇒ (¬ψ) Proof by contradiction is a general method that works as follows. You want to provesome statement phi. Assume not phi. Reason until you reach a conclusion that'sfalse, often deriving both psi and not psi for some statement psi. For example, in theproof that the square root of two is irrational, we proved that p and q have nocommon factors, and yet we knew that p and q were both even. We have deducedtwo contradictory things: A true assumption cannot lead to a false conclusion. Proofby contradiction is a method for proving the truth of a statement by assuming theopposite. We begin with an assumption of not phi and reach a conclusion—a falseconclusion. Since our assumption led to a contradiction, we know that not phi mustbe false. Hence, phi must be true. In a proof by contradiction, the theta (or hypothesis) is the statement that youassume to be true at the start of your proof. The psi (or conclusion) is the statement

that you aim to prove false. Using truth tables, let's see how it works when youassume something and end up proving it false: That would amount to proving yourtheorem. In order to demonstrate that a statement is true, we can use a truth table. A truthtable contains four-member columns and rows. A row represents true values and acolumn represents false values. The truth table for theta yield psi, or thetaconditional psi, is composed of these four-member columns and rows. Here is what itlooks like: T, F, T, T. If we have carried out a proof that yields this particulararrangement of values (T, F, T, T), we can conclude that this statement is true; wecan erase those lines in our proof because they are no longer needed. The only true statement in the truth table for the implication symbol is here: we havea true antecedent, which means that this line is one of these three. We have a falseconsequent, which means that the only possibility is that psi is false. In other words,theta is false. So when you use a proof by contradiction to establish an assumptioncounter to what you're trying to prove and carry out some reasoning to deduce afalse conclusion—which isn't really a contradiction—you've established that this thingmust be true. Then the conclusion from having reached a false conclusion—the bigconclusion, the global conclusion—is that your original assumption must be false.The truth table analysis of proofs by contradiction can be difficult to grasp, but if yourevisit the original proof that the square root of two is irrational and consider it in lightof the idea behind proofs by contradiction generally and in light of truth table analysisspecifically, you should be able to understand why proofs by contradiction work sowell. Although the proof of the irrationality of the square root of three is somewhat simplerthan the proof of the irrationality of the square root of two, it can still be a challengefor beginners. The process used here is known as proof by contradiction, whichmakes use of a clear starting point in order to arrive at a contradiction. To obtain adirect proof of some statement phi, you have to generate an argument thatculminates in phi. But where do you start? The only way to proceed is to try to arguesuccessively backwards to see what chain of steps ends with phi. There are manypossible starting points but just one goal. And you have to end up with that goal, andthat can be difficult. Proof by contradiction, on the other hand, involves proving that agiven statement is false by showing that it leads to a contradiction. A proof bycontradiction often proves something stronger than ordinary proofs because it showsdirectly that a particular object does not exist or that certain equations do not havesolutions rather than just giving examples of such objects or equations. You begin byassuming that such an object does exist. And then you use that assumed object todeduce a false consequence of a pair of contradictory statements. The irrationality ofthe square root of 2 is a good example since that states the nonexistence of twonumbers p and q whose ratio is equal to root 2. Even though there is no cookiecutter template approach to constructing proofs, there are some guidelines. We just

met two.Proof by contradiction can be a useful method for proving an existencetheorem or statement about an object that does not exist. Proof by contradiction canalso be used in proofs by contradiction for other purposes as well. When you'reconstructing a proof, remember to follow some basic guidelines. Don't assume thatbecause you've used a certain method for one problem, it will work for all problems.Each new problem requires its own analysis.In general, you can prove a conditional statement of the form "if phi then psi" byassuming that "phi" is true and deriving "psi". Considering the conditional from adifferent perspective—namely that it's true when "phi" is false—yields a simple prooffor the validity of an argument with a false premise. This shows us how conditionalstatements capture genuine implication despite their strange definition. In all actual practical applications, you assume a hypothesis and then deduce aconclusion. This is called implication. It says that the conclusion follows from thehypothesis. For example, let x and y be variables for real numbers, and prove thefollowing: If x and y are rational, then x + y is rational. This is not a surprising result;this is nothing deep. The proof begins by assuming that x and y are rational. In this case, there existintegers p, q, n, and m such that x is p/m and y is q/n. By adding these two fractionstogether we obtain pn + qm / mn; hence x + y is rational. It is important to emphasizethat the entire proof consists of three steps: (1) assume x and y are rational; (2)reason from this assumption; (3) conclude that the sum is rational. To prove atheorem, one must declare the assumption, carry out the reasoning in a clear andunderstandable fashion, and then state the conclusion when you've reached it.Remember that proofs have two purposes: to convince yourself and others. It is bestto state at the outset what your assumption is or what your conclusion is. When you are writing a proof, remember that proofs have two purposes. One is toconvince yourself, and the second is to convince other people. When you write aproof, you must be sure to clearly state your assumptions and conclusions. And youmay know what you're doing if you don't mention what your assumption is or whatyour conclusion is. So it really is good, even for your own purposes, to write downwhat your assumptions are. But certainly from a communicative angle it's importantto begin by stating the assumption, then to lay out the reasoning in a simpleunderstandable fashion, and then to state the conclusion that you've reached. Consider the following expressions: r + 3, 5 times r, r + s, and r times s. In this quiz,I'm asking you to select the ones that you think are necessarily irrational. Unlike mostof the quizzes. The focus is on reasoning that you need to carry out in order to getthose answers. In general, rational numbers can be expressed as ratios of integers; irrationalnumbers cannot. The five answers we found to be necessarily irrational are 1, 2, and

5. In each case, you use the fact that a rational number is one that can be expressedas a quotient of two integers, and an irrational number is one that cannot be soexpressed. For example, to show that r+3 is irrational, you could use a strategy such as thefollowing: If r+3 was rational, then r would be rational. Similarly, you could use asimilar argument to show that if 5r was rational and could be expressed as a quotientof two integers, then so could r. Likewise, you could use an analogous argument forthe square root of r. Only two of these (3 and 4) are necessarily irrational. To showthat r+s is not necessarily irrational, you would need to find examples of irrationals rand s for which the sum is rational. For instance, let's say that r is the square root of2 and s equals 10—the square root of 2. Then r+s equals 10 (an integer). We know that the square root of 2 is irrational. And a very simple argument showsthat 10 must be irrational. In fact the argument you use to show that this number isirrational is a combination of the two arguments you used in parts 1 and 2. R and sare irrational, but their sum is rational. In this case, we could take r=square root of 2and s=square root of 2. R and s are both irrational, and yet r times s is 2, which isrational. Suppose we are trying to prove that for all natural numbers n, if the sine ofan angle isn't 0 then that angle can't be a whole multiple of pi. We might write this asif not ((the case that for all natural numbers n in N, if theta is not equal to n pi thensin(theta) isn't 0)). Well, there are two negatives in this statement, so let's clear themout and put this into positive form: Suppose that for some natural number n (N), if thesine of an angle isn't 0 then that angle can't be a whole multiple of pi. This is an example of proving a desired result by means of its contrapositive. Westart with the statement in positive form: there exists an integer n such that sin(theta)= 0, or equivalently, the sine of theta is 0. We then negate this statement and movethe negation inside the absolute value sign: not that sine theta is 0. This statement isequivalent to the original statement sin(theta) = 0, which we can prove using basictrigonometry. Since all whole number multiples of pi equal 0 when it comes to theirsines, we have proven our desired result. The contrapositive of a conditional is logically equivalent to the conditional itself, so ifwe prove the contrapositive, we have proved both sides of the biconditional. As anexample, consider proving that "If x is a multiple of pi, then sin(x) crosses the x-axis"by showing that "If sin(x) does not cross the x-axis, then x is not a multiple of pi."This latter statement is enough to prove that if something does not satisfy acondition, it does not satisfy a condition that logically guarantees its satisfaction.