Introduction to Mathematical Thinking.
PROOF BY CONTRADICTION 1. You want to prove some statement ф 2. You start by assuming neg ф 3. You reason until you reach a conclusion that is false/ – often by deductity both ψ and neg ψ from some ψ. 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 neg ф must be false. 6. In other words, ф must be true. Truth analysis or proof contradiction what can we conclude from theta Rightarrow ψ a proof of where ψ is false? theta ψ theta Rightarrow ψ T T T T F F F T T F F T Prove that sqrt3 is irrational. 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 ф Rightarrow ψ. 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 ] Rightarrow [ 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 x+y = p/m +p/n = pn+qm/mn – Hence x+y is rational. Let r, s be irrational numbers. Say which of the following are necessarily irational. ✓ 1. r+3 ✓ 2. 5r x 3. r+5 r=sqrt2, 5=10-sqrt2 x 4. r5 r=sqrt2, 5=sqrt2 ✓ 5. sqrt r logocal reasoring! Conditionals involving quantifiers are sometimes best handled by proving the contrapositive. He is contrapositive. To prove ф Rightarrow ψ, prove (negψ) Rightarrow (negф) To prove: (sin theta ne O) Rightarrow (forall n in N) (theta ne n π) The statement is equipment to: neg(forall A in N) (theta = n π) Rightarrow neg (sin theta ne O) In positive form: (exists n in N) (theta = n π) Rightarrow (sin theta = O) We know this is true! This proves the desired result. The prove a biconditional ϕ ⇔ ψ , we generally constant two proofs, are of ф ⇒ ψ, the other of ψ ⇒ ф Occasionally, it is easier to prove the two conditional. ф ⇒ ψ, and (neg ф) ⇒ (neg ψ) Proof by contradiction is a general method that works as follows. You want to prove some statement phi. Assume not phi. Reason until you reach a conclusion that’s false, often deriving both psi and not psi for some statement psi. For example, in the proof that the square root of two is irrational, we proved that p and q have no common factors, and yet we knew that p and q were both even. We have deduced two contradictory things: A true assumption cannot lead to a false conclusion. Proof by contradiction is a method for proving the truth of a statement by assuming the opposite. We begin with an as sumption of not phi and reach a conclusion—a false conclusion. 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 you assume 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 you assume something and end up proving it false: That would amount to proving your theorem. In order to demonstrate that a statement is true, we can use a truth table. A truth table contains four-member columns and rows. A row represents true values and a column represents false values. The truth table for theta yield psi, or theta conditional psi, is composed of these four-member columns and rows. Here is what it looks like: T, F, T, T. If we have carried out a proof that yields this particular arrangement of values (T, F, T, T), we can conclude that this statement is true; we can 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 have a true antecedent, which means that this line is one of these three. We have a false consequent, 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 assumption counter to what you’re trying to prove and carry out some reasoning to deduce a false conclusion—which isn’t really a contradiction—you’ve established that this thing must be true. Then the conclusion from having reached a false conclusion—the big conclusion, 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 youre visit the original proof that the square root of two is irrational and consider it in light of the idea behind proofs by contradiction generally and in light of truth table analysis specifically, 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 simpler than the proof of the irrationality of the square root of two, it can still be a challenge for beginners. The process used here is known as proof by contradiction, which makes 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 that culminates in phi. But where do you start? The only way to proceed is to try to argue successively backwards to see what chain of steps ends with phi. There are many possible starting points but just one goal. And you have to end up with that goal, and that 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 by contradiction often proves something stronger than ordinary proofs because it shows directly that a particular object does not exist or that certain equations do not have solutions rather than just giving examples of such objects or equations. You begin by assuming that such an object does exist. And then you use that assumed object to deduce a false consequence of a pair of contradictory statements. The irrationality of the square root of 2 is a good example since that states the nonexistence of two numbers p and q whose ratio is equal to root 2. Even though there is no cookie cutter template approach to constructing proofs, there are some guidelines. We just met two.Proof by contradiction can be a useful method for proving an existence theorem or statement about an object that does not exist. Proof by contradiction can also be used in proofs by contradiction for other purposes as well. When you’re constructing a proof, remember to follow some basic guidelines. Don’t assume that because 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” by assuming that “phi” is true and deriving “psi”. Considering the conditional from a different perspective—namely that it’s true when “phi” is false—yields a simple proof for the validity of an argument with a false premise. This shows us how conditional statements capture genuine implication despite their strange definition. In all actual practical applications, you assume a hypothesis and then deduce a conclusion. This is called implication. It says that the conclusion follows from the hypothesis. For example, let x and y be variables for real numbers, and prove the following: 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 exist integers p, q, n, and m such that x is p/m and y is q/n. By adding these two fractions together we obtain pn + qm / mn; hence x + y is rational. It is important to emphasize that 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 a theorem, one must declare the assumption, carry out the reasoning in a clear and understandable fashion, and then state the conclusion when you’ve reached it. Remember that proofs have two purposes: to convince yourself and others. It is best to 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 to convince yourself, and the second is to convince other people. When you write a proof, you must be sure to clearly state your assumptions and conclusions. And you may know what you’re doing if you don’t mention what your assumption is or what your conclusion is. So it really is good, even for your own purposes, to write down what your assumptions are. But certainly from a communicative angle it’s important to begin by stating the assumption, then to lay out the reasoning in a simple understandable 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 most of the quizzes. The focus is on reasoning that you need to carry out in order to get those answers. In general, rational numbers can be expressed as ratios of integers; irrational numbers 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 expressed as a quotient of two integers, and an irrational number is one that cannot be so expressed. For example, to show that r+3 is irrational, you could use a strategy such as the following: If r+3 was rational, then r would be rational. Similarly, you could use a similar argument to show that if 5r was rational and could be expressed as a quotient of two integers, then so could r. Likewise, you could use an analogous argument for the square root of r. Only two of these (3 and 4) are necessarily irrational. To show that r+s is not necessarily irrational, you would need to find examples of irrationals r and s for which the sum is rational. For instance, let’s say that r is the square root of 2 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 shows that 10 must be irrational. In fact the argument you use to show that this number is irrational is a combination of the two arguments you used in parts 1 and 2. R and s are irrational, but their sum is rational. In this case, we could take r=square root of 2 and s=square root of 2. R and s are both irrational, and yet r times s is 2, which is rational. Suppose we are trying to prove that for all natural numbers n, if the sine of an angle isn’t 0 then that angle can’t be a whole multiple of pi. We might write this as if not ((the case that for all natural numbers n in N, if theta is not equal to n pi then sin(theta) isn’t 0)). Well, there are two negatives in this statement, so let’s clear them out and put this into positive form: Suppose that for some natural number n (N), if the sine 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. We start 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 move the negation inside the absolute value sign: not that sine theta is 0. This statement is equivalent to the original statement sin(theta) 0, which we can prove using basic trigonometry. Since all whole number multiples of pi equal 0 when it comes to their sines, we have proven our desired result. The contrapositive of a conditional is logically equivalent to the conditional itself, so if we prove the contrapositive, we have proved both sides of the biconditional. As an example, 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 a condition, it does not satisfy a condition that logically guarantees its satisfaction.
