okay so in this uh lecture we are going to do uh Pro by contradiction and I'm going to give you a quick description and then uh three examples uh so we did Proof by contrapositive last time this is similar in a way uh but um different as you'll see let me just um outline the difference and that way I can um uh explain uh what proof by contradiction is so uh it's going to be proofed by contradiction but let me just remind you what proved by contrapositive was so um so it's sort of similar if you like uh to um proving the contrapositive uh in the we're not going to prove uh the statement we're interested in directly um we're going to Pro we're going to use a negation uh to get there um so for pro proving the Contra positive we noticed that if you need to prove an implication so uh so that was so this was um uh 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 um you may as well prove uh so it is equivalent to prove to prove that uh 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 uh then it will be uh the same statement so not Q implies not P so these two things are the same um proving the uh a proving by by contradiction is an even more General uh kind of thing because it doesn't actually require a an implication um exactly um but uh so uh for proof by contradiction um we note that um if you want to prove uh so to prove a statement p uh it suffices uh to prove that uh not P implies false why is that true because um the only time that uh this can be true if this is false is if 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 uh then the only way this can work is if uh it must be that uh not of this is true so not of not p i a p okay that's the principle so let's just see some examples and I will start with um the most famous example uh 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 were not infinitely many primals in other words that there are finitely many so proved by contradiction um assume that there are 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 um so uh say um P1 P2 all the way up to some number P so this is my final list of primes so now consider uh the natural number where I just take all of these things all these prime numbers and I multiply them together and then I add one so I'll call it n is the product of all these so P1 * P2 * time p r uh okay so that's some natural number and then I'm going to make it uh even bigger I'm just going to add one to it okay so I'm all those things multiplied together and then I add one okay well uh this number is divisible by P1 so when I add one to it it can't be divisible by P1 as well you know if you take the number uh if you take the prime three and you take any multiple of it so I know 15 right when you add one to it you get 16 that's no longer divisible by three uh and the same will be true for all of these primes so this uh is not divisible by any of the Primes because it's one more than a multiple of it okay so okay so this number here is not divisible by any Prime Pi um but it's one bigger than uh the a multiple of them so definitely bigger than all the Primes Pi so um 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 uh one thing that's uh the two things that are completely opposite have to be true together uh and we know that that is false so uh this is a contradiction so uh the theorem is proved is proved okay and then a a nice QED symbol at the end to uh make that clear okay let's look at the next most famous example uh the square < TK of two uh is irrational so example two uh um the square Ro TK of two is irrational so to say that the square root of two is a rational number as we know is one that you can express as uh 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 and then that gives us an A over B and then we can go from there so prove Pro uh assume uh uh that it's not true then uh the square root of 2 is equal to A over B for some integers a and B right well um we may as well assume that these integers don't have any factors in common right because if they did we could just cancel them out it's perfectly reasonable thing to do so we can assume um 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 um let's just muck about with this equation and see what happens um I'm going to suggest the first thing we do is try and make it something about the integers that we can uh we can think about so if I Square uh both sides uh then we'll get something like that so um uh we uh we have uh so squaring both sides 2 = A2 over b^2 okay and then multiplying up by b ^ 2 um we get um that uh 2 b^2 = A2 right so that tells me that a is even because I've got two times some integer which says that uh a s has to be even uh so a s is even and well uh we' seen uh before that if you take the square of an odd number you get an odd number um and uh so if a were odd uh I'd get a squ is odd so actually uh a can't be odd it has to be even so a is even okay uh therefore uh a is 2 * C for some other integer C also an integer so let's sub that back in here hence 2 b^2 = 2 C all 2 uh and this I can expand and I get 4 c^2 um uh thus uh cancel the two I get b^2 is 2 c^ 2 but that means that b^ s for exactly the same reason b^2 is even so B is even but this was 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 uh they do have a factor in common A and B do have a factor in common namely two this is a contradiction so the theorem is proved okay seems a bit weird to think that you know just the fact that uh factors not having factors in common is you know a big big enough deal uh for something not to be um uh for two things not to be uh to be the source of the contradiction but in fact that is uh what it is here okay uh and then the last example I'm going to do um so example uh three is just going to be this one uh log to the base 2 of three is irrational okay so how does this go exactly the same way assume it's false so remember remember what log 2 log to base 2 of three means this is the power that I have to raise the base to in order to get three so it is the solution to 2 to the a = 3 okay but anyway um then uh log 2 of 3 is equal to A over B for A and B integers all right so now I can take um two uh to the power of both sides and then I'll get so um since this is the thing that I have to raise two to in order to get three that tells me that uh 2 to the A over B is equal to three okay and um because uh three is bigger than two that tells me that A over B has to be a positive number okay so um A over B uh is a number that is bigger um than uh one in fact because 2 to the 1 is two and I need to be bigger than that uh if I take two to if I take both sides here to the power B I get uh 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 uh an even number uh and the right hand side has to be an odd number so B has to be at least at least uh one a has to be at least one if this is going to uh be true so um uh but the right hand side is odd and the left hand side is even and this is a contradiction so the theorem is proved okay and there will be more uh opportunities to practice that uh in the tutorial