Okay, we are going to look now at proving, we'll look at some examples of proving the contrapositive. So you'll remember how to form the contrapositive. You start with an implication. If you have P implies Q, then you can see, so if P then Q, that is equivalent to the statement that not Q implies not P and why is that the case? Because the only time that P implies Q is false is when P is true But Q is false Right.
So if Q is false Then we're fine as long as P is not true. In other words as long as P is false as well So that's why these things are the same And we can use that actually to make some of the things that we want to prove quite a bit easier. So let's just see how that works with some examples.
So proving the contrapositive. So recall that p implies q is The same statement, equivalent to the statement that Q implies not P. So I think let's have a look at an example to see how sometimes proving the contrapositive can make things easier. So this one we're going to be working over the integers. And here's the statement we're going to make.
So, prove. So every multiple of 3, so all the multiples of the number 3 in the integers, is the sum of 3 consecutive integers. integers right so what is what are the consecutive integers well they've just got to have a difference of one between them so so anything of the form and I'll say X X plus 1x plus 2 Okay, very good.
Right, so that's what we're trying to do. Let's just see what it looks like. So translating the statement into predicate logic.
We're going to say, for all x in z, so that's going to be all of the possible things I might be interested in, I want to prove that if x is a multiple of 3, okay, so how do we write that? Well, x is a multiple of 3, if I can write it as......is... 3y. So if there exists y such that x equals 3 times y, so that's what it means to be a multiple of 3. If that's true, then there exists a z.
such that you can get your x as the sum of these three consecutive numbers. So it exists as z such that x is equal to z plus z plus 1 plus z plus 2. Okay, so spread out over a few lines there. Anyway, there exists a y such that x is equal to 3y implies that there exists a z such that x is equal to z plus z1 plus z2.
Okay, so we're going to prove the contrapositive. So the contrapositive... is. Remember that when you've got quantifiers and you take not of them, you need to swap the quantifiers over and then you can swap the things inside. So we want, this is p, this is q, so we want not q implies not p.
So the contrapositive is for all x in z, not of this, well that is for all z, x is not equal to this thing so this now is supposed to imply that the not of this so the not of this is again you've got to move the quantifier through so it's for all y Not of this. x is not equal to 3y. Okay, so we've turned it into the contrapositive, but the same thing, as I was saying last time, holds. If you want to do this, then you take x in z, and then you assume that this is not true. You assume that this holds, so that this is not true, and then you try and prove that this is true.
So, proof. Take x in z. And then we're saying that for all z this is not true. So then, for all z, again an integer, x is not true. not equal to and I'm just going to simplify this statement because I've got three z's here and then three so X is not equal to 3 Z plus 3 So that implies that for all z in z, x is not equal to 3z plus 1. Just factorising that.
Okay, so we can probably see what the issue is going to be now. So, if I'm never allowed to write x in this form for x, type of Z then I can't write it in this form for Y either because if Z plus 1 is an integer then so is Y so I can say now in particular for any So for all z in z, x is not equal to and now you just substitute that in and you get 3y as required. Okay, so sometimes it turns out to be easier to prove the contrapositive, and it's only just with a little bit of practice that you can see that.
Let me just give you one more example, it's probably a bit easier even. Another example, number two. So this will be over the reels.
prove that a real number is irrational implies that 1 over it is true so a real number let's say X is irrational I'm just sorry. Prove that if a real number x is irrational, then the real number 1 over x is irrational. Okay. So we're saying that this is really the statement i.e. for all x and we're over the reals x is a rational number, x is not a rational number implies that 1 over x is not a rational number.
Okay, so perhaps what's nice about this one is that we're going to get not in to become in when we take the contrapositive. Okay, so the contrapositive is... So you take, you've got these two implications, you take not of each of them and then swap them over. The contrapositive is, for all x, 1 over x is a rational number.
That implies that x is a rational number. OK. So, take x in the reals, always the same, take an x, just imagine you fixed it in your head, and then assume that this is true, and assume that 1 over x is in Q. Right, well what does that mean? That means that there exist two integers, one over the other, and one over x is expressed as that.
Then there are integers. a and b such that 1 over x is equal to a over b. Okay. Well, we know how to turn 1 over x into x, don't we? If we've got it written as a fraction, we just have to multiply, we just have to swap the fraction over.
So if we've got this, it follows that x is just equal to b over a. It's also rational. And that's what we had to prove. So we're done. So the contrapositive in that case, the reason it was good is because as soon as...
Try to say something is irrational. It's like saying that there aren't any integers you think of. that it's not going to work it's much better in this case to say well there are I can just sort of fix the integers because it is in the rational numbers and so I I know I can then work with it that's why that one works in any case it just as a postscript if you wanted to know why this does work just observe b over a with 1. So I just get, if I just say that 1 over x times x equals 1. We know that's true by the definition of 1 over x. And 1 over x is a over b.
And if I put b over a here, then I can cancel from the top and the bottom. Because that's how I make fractions behave. And so these two are the same, and we have 1 over x is a over b, so from that you can get that x is b over a.
Right, proved by contradiction next time.