Okay, so in this lecture we are going to do proof by contradiction and I'm going to give you a quick description and then three examples. So we did proof by contrapositive last time. This is similar in a way but different as you'll see.
Let me just outline the difference and that way I can... explain what proof by contradiction is so it's going to be proved by contradiction but let me just remind you what proof by contrapositive was so it's sort of similar if you like to proving the contrapositive In that we're not going to prove the statement we're interested in directly, we're going to use a negation to get there. So for proving the contrapositive, we noticed that if you need to prove an implication, so that was, so this was, If you want to prove, if you've got two propositions, P and Q, so if you want to prove that whenever P is true, it follows that Q is true, you may as well prove, so it is equivalent to prove, to prove that not Q.
So when is this not true? It's not true when this is true and this is false. So whenever this is false, as long as we can prove this is false as well, then it will be the same statement.
So not Q implies not P. So these two things are the same. Proving something by contradiction is an even more general kind of thing because it doesn't...
actually require an implication exactly but so for proved by contradiction we note that if you want to prove though to prove a statement P It suffices to prove that not P implies false. Why is that true? Because the only time that this can be true, if this is false, Is it this is false as well because if we so if this is true because if it's true if we haven't screwed up the logic then the only way this can work is if It must be that Not of this is true So not of not p, i.e. p.
Okay, that's the principle, so let's just see some examples. And I will start with the most famous example, which is the proof that there are infinitely many prime numbers. So let's prove there are infinitely many. prime numbers.
Okay, so this is my p, is that there are infinitely many prime numbers. So I'm going to assume that it's false. So let's assume that there are not infinitely many prime numbers. In other words, that there are finitely many. So, proved by contradiction, assume that There are Only finitely many primes.
So, because it's the natural numbers, I can just put them all in a list of ascending order. So, say... P1, P2, all the way up to some number PR.
So this is my finite list of primes. So now, consider the natural number. Where I just take all of these things, all these prime numbers, and I multiply them together, and then I add 1. So I'll call it n is the product of all these. So p1 times p2 times pR. Okay, so that's some natural number.
And then I'm going to make it even bigger. I'm just going to add 1 to it. Okay, so I'm, you know, all those things multiplied together, and then I add 1. Okay, well, this number is divisible by p1.
So when I add 1 to it, it can't be divisible by p1 as well. You know, if you take the number, if you take the prime 3, and you take any multiple of it, so, I don't know, 15, when you add 1 to it, You get 16, that's no longer divisible by 3. And the same will be true for all of these primes. So this is not divisible by any of the primes, because it's one more than a multiple of it.
OK. So, okay, so this number here is not divisible by any prime pi, but it's one bigger than a multiple of them. So definitely bigger than all the primes pi. But this number is bigger than all of the primes.
Okay, well if it's bigger than all the primes then it certainly can't be prime because it's bigger than them So it's not prime so it is divisible by a prime. So it's divisible by a prime So it's not divisible by any prime and it's divisible by a prime. So that's a contradiction. So we proved that two statements that are one thing that's the two things that are completely opposite have to be true together. And we know that that is false.
So this is a contradiction. So. The theorem is proved.
And then a nice QED symbol at the end to clear. Okay, let's look at the next most famous example. The square root of 2 is irrational. So example 2, the square root of 2 is irrational.
So to say that the square root of 2... A rational number, as we know, is one that you can express as a over b for two integers a and b. So if we want to prove this by contradiction, we have to assume that it is rational. That gives us an a over b, and then we can go from there.
So prove. assume that it's not true. Then the square root of 2 is equal to a over b for some integers a and b.
Right, well, we may as well assume that these integers don't have any factors in common, because if they did, we could just cancel them out. It's a perfectly reasonable thing to do. So we can assume, so we may as well assume that A and B have no factors in common.
Okay, fair enough. Now let's see where we can go from there. So let's just muck about with this equation and see what happens. I'm going to suggest the first thing we do is try and make it something about the integers that we can think about.
So if I square both sides, then we'll get something like that. we have, so squaring both sides, 2 equals a squared over b squared. And then multiplying up by b squared, we get that 2b squared equals a squared.
Right, so that tells me that a is even, because I've got 2 times some integer which says that a squared has to be even. So a squared is even, and well, we've seen before that if you take the square of an odd number, you get an odd number. So if a were odd, I'd get a squared is odd. So actually, a can't be odd.
It has to be even. a is even. Okay, therefore, a is 2 times c for some other integer c. Also an integer. So let's sub that back in here.
Hence, 2b squared equals 2c, or squared. And this I can expand, and I get 4c squared. Thus, cancel the 2. I get b squared is 2c squared.
But that means that b squared, for exactly the same reason, b squared is even, so b is even. But this is now a contradiction, because I'd assumed that a and b had no factors in common. But I've shown that a is even and b is even, so they're both even.
So they do have a factor in common. A and B do have a factor in common, namely 2. This is a contradiction, so the theorem is proved. OK?
Seems a bit weird to think that, you know, just the fact that... Factors, not having factors in common is, you know, a big enough deal for something not to be, for two things not to be, to be the source of the contradiction, but in fact that is what it is here. Okay, and then the last example I'm going to do, so example 3 is just going to be this one.
Log to the base 2 of 3 is irrational. Okay, so how does this go? Exactly the same way. Assume it's false.
So remember what log2 base2 of 3 means. This is the power that I have to raise the base to in order to get 3. So it is the solution to 2 to the a equals 3. then log 2 of 3 is equal to a over b for a and b integers. All right, so now I can take 2 to the power of both sides, and then I'll get, so since this is the thing, that I have to raise 2 to in order to get 3, that tells me that 2 to the a over b is equal to 3. And because 3 is... bigger than 2, that tells me that a over b has to be a positive number.
Okay, so a over b is a number that is bigger than 1, in fact, because 2 to the 1 is 2. and I need to be bigger than that. If I take both sides here to the power b, I get 2 to the a, so the 2 to the a over b to the b is just 2 to the a. is 3 to the b and this is going to be a contradiction because the left hand side here has to be an even number and the right hand side has to be an odd number so b has to be at least at least one a has to be at least one if this is going to be true so but the right hand side is odd and left hand side is even and this is a contradiction so the theorem is proved okay and there will be more opportunities to practice that in the tutorial