>> Hello and welcome to this introductory screencast on proof by contradiction. So far we've seen two different techniques for proving conditional statements. One method is called the direct proof. This is where we assume the hypothesis of the statement we're trying to prove and through a combination of mathematical and logical steps arrive at the conclusion. This is a style of proof you first use in this course and revisited in Section 3.1. The other method is proved by contraposition and a proof by contraposition remember instead of proving the conditional statement we're given we prove its contrapositive instead. This works because a conditional statement and its contrapositive are logically equivalent and so proving one amounts to approving the other. We say that these are two methods of proof, but actually they are just two instances of the same method. Namely they're both direct proof. In both cases we are assuming the hypothesis of some conditional statement whether it's the original statement or its contrapositive and then working forward to arrive at a conclusion, but the method of proof we're about the study is radically different from these, but it still begins with this understanding of a simple point of logic. Given any statement P the statement P and its negation not P have opposite truth values. For example if P is the statement n is an even integer then not P is a statement n as an odd integer and the statement and its negation are completely opposed and very especially note that if not P is false then P is true. The simple observation that if the negation of P is false then P is true gives us a new way to prove a statement. Namely instead of proving that the statement given to us is true we can try to prove that this negation cannot be true. If we can prove that the negation of a statement must be false, then the original statement must be true. This style of proof is called proof by contradiction. It is very powerful and very useful. Here's how proof by contradiction flows. First, we assume for the sake of argument that negation of the statement that we want to prove is true. This will involve actually writing out what the negation says. Then we begin to work with the negation by performing mathematical and logical steps to restate it. At some point in this process we should arrive at a conclusion that is in direct contradiction to something we know is already true. The thing we contradict could be a known fact, a previously proven result or even one of the assumptions we are making in the proof. When we reach the contradiction, we have reached an impasse that forces us to back up and take stock of what we assumed. We reach the contradiction by assuming that the negation of our statement is true, but since we reached the contradiction that assumption must have been mistaken. Therefore, the negation is false and as we know if the negation of the statement is false the original statement is true. Now we'll see several examples of this proof technique and action throughout the screencast here but let's start with the simple situation now. We're going to prove by contradiction the following statement for all positive integers and an n, n squared minus n squared is not equal to 1. Note that the word positive is necessary there in the condition. If we remove that part of the condition and allow any integers at all, then this equation certainly does have solutions. For example, m equals 1 and n equals 0 will make it work and remember that 0 is not positive. So we really do mean positive integers here. The first step in the proof is to assume that the negation of the statement we want to prove is true. Now the statement we want to prove is a universally quantified statement. So its negation must be an existentially quantified statement. Its negation would say there exist positive integers m and n such that m squared minus n squared is equal to 1. So let's assume that this is true. Well, what can we do with it? On the left side of the equation, we could factor and get m plus n times m minus n equals 1. That's a valid mathematical step. Now since m and n are integers both m minus n and m plus n are also integers by the closure of the set of integers under addition and subtraction another valid mathematical step. Well, we know from arithmetic that the only way to multiply 2 integers together to get 1 is for both of those integers either to be equal to 1 or both of them equal to minus 1. This is another valid step; it's a fact of arithmetic. Let's consider those two cases separately. The thing to watch here is where we end up when we proceed from this point through valid logical and mathematical steps. Now in the first case if both m plus n and m minus n are equal to 1, we can take those two equations and add them together to get 2m equals 2 and that means that m equals 1, but since m minus n is equal to 1 that means that n equals 0. Now notice all of these are valid mathematical steps. However, we reached a contradiction at this point because early in the proof we had assumed that n is a positive integer. We started off assuming that n was positive and now we're arriving at the conclusion that n is not positive but rather equal to 0. Now both of these statements cannot be true. N cannot be both positive and not positive at the same time and so we have a contradiction. Now what does this mean for us? Well, how do we get here? We got to this contradiction by assuming that there existed positive integers solutions to that equation in the first place. Remember that was the negation of the statement we wanted to prove, but since assuming that negation led us to a contradiction, the negation must be false and if the negation is false then the original statement must be true. So what about the second case if both m plus n and m minus n are equal to 1 or equal to minus 1, then add the two equations together again and you'll get 2m equals negative 2. So m is equal to negative 1, but since m minus n is equal to negative 1 it follows that n equals 0. Now these are all valid mathematical steps, but we have a contradiction again. We assumed early on that n was positive and now we're concluding that it isn't and it can't be both. So in both of these cases, we arrive at a contradiction. We got to the contradiction by assuming that the negation of the statement we wanted to prove was true, that that assumption is wrong, and so the negation must be false. If the negation is false, the original statement must be true and that ends the proof. So there must not be any positive integer solutions to this equation after all. So, to recap a proof by contradiction works by first assuming the negation of the intended statement is true then arriving at a contradiction of some sort through a combination of valid, logical and mathematical steps and then finally concluding that the negation can't be true because of the contradiction. Therefore, the negation is false, therefore, the original statement that we wanted to prove is true in the end. In the next two screencasts, we're going to see several examples of these and I encourage you to watch and work along with them. Thanks for watching,