Video 0-2: §0.2 Proof templates, random shuffle motivation

0:02 After this bit of motivation, why we want formal statements of formal proofs, I want to give you a few uh specific examples of what formal statements are and how we can prove them, which often follows their structure. So, we'll look at uh at that first.

0:20 At some level, um we'll have to talk about what a proof is and uh if you want to be very precise, you need a specific um logical system where the proof is formulated in, and then it it comes down to a sequence of statements. The proof system gives you axioms. These are things that are undoubtedly true, and uh where you don't have to prove that they are true, and from those and some inference rules, you have to derive the statement you want to prove. That is what a formal proof is. Uh in many cases, we'll confine ourselves to have a little bit um shortcuts in there. So, it will often be enough for us to convince a human expert. But the uh assumption there is that if it's needed, you can always fill the fill the shortcuts in with steps in such a formal system. And only if if you do that, you get a bulletproof statement proof.

1:28 So, let's let's do a few uh concrete examples um for statements and also to make this more concrete. So, suppose I have I have these two statements. Statement A is it rains, and statement B is the street is wet. These are my my two primitive statements in this case, and let's suppose for the for the sake of this slide that this is completely unambiguous. So, there's no uh we're in Britain, so there's often drizzle where it's not clear, is that rain or not? So, let's let's pretend uh the statement is is definitely either true or false. And the same for this one. Uh no debates about a puddle on the side and the rest is dry. Let's pretend it's it's completely black and white. Then we can take such a statement, we can negate it, not A, so it does not rain if you formulate it in proper English, not it rains. You can take two statements and put an and between them, which means they both have to be true. You can put an or between them, which means either of the two can be true or both. It's not an exclusive or.

2:29 A or B could be it rains or the street is wet or both. Just want to be clear about that. And the more interesting cases are implications and equivalence. If I write A implies B with this arrow, you should you should read it in English as if they then be. But really it's formally equivalent to this. And that that's um that's important an important distinction that I'll I'll come back to, but I have a slide or question for you to to try that. So just to plug in uh the statement then would be if it rains, then the street is wet.

3:10 An equivalence is is basically an implication in both direction. A implies B and B implies A. Which we often uh in English abbreviate as A holds true if and only if B holds true. And you'll see me use this abbreviation sometimes just because it's quicker to write. It's not a typo. If with double F stands for if and only if. All right? Good. Wake up time. Uh Wake up time for the phone as well.

4:09 I don't want to influence you straight away too much. Okay, that's a fair share of people who have voted. So, I'll show you the two bars. And uh it's it's not equally distributed, but there's a fair amount of people for both answers or even all three.

5:05 So, resist the temptation to change your votes. Take it as the average of the room. And in this case, the statement is true. And let's unpack this a bit. Now, uh just to be clear, I'm not a a flat-earther, right? This is not where this is where this is getting at.

5:26 The statement has has two parts. Uh there's the Let me do it more schematic. So, there's the if then part, which means we're talking about an implication. And so, it it will uh in the end be a formal statement that has this arrow in the middle. And then we have two parts. The Earth is flat, and ships can fall over the rim. Let's give these names again, A and B.

5:53 So, the uh implication if if we define the statements A and B, then the statement is A implies B. Now, that hasn't helped us so much yet. Uh but remember what we said, an implication formally, if if you have to check it uh in detail, it should you should replace it with not A or B. So, we can also write this as not A or B.

6:19 Uh so, uh okay, I don't I haven't invented a a symbol for this is the same. Sometimes people use the equivalent symbol an equal with three things for saying two formulas are equivalent.

6:34 But if you unpack that again into English, it means an or statement, ships can fall over its rim or the Earth is not flat. One of those is true, that's fine and that's good enough. And let's suppose the Earth is not flat and then not A is true, that means the whole statement is true. In particular, my point here is to hammer hammer in that statement, if you have an implication and the premise, the A statement in the if part is false, the whole thing is true no matter what garbage you claim in the rest. Okay? That's just how it's defined uh and this is This is useful for implications. It makes sense to define it that way, but it's often something people find a bit unintuitive when you first see it.

7:31 So, the first type of rule template that we'll look at is for implications. Uh the others, if you if you have to prove an and statement or an or statement, it's usually quite clear what to do. If you have an and statement, you have to prove A and B separately, one after the other. If you prove or, then you have to work your way through that the two are somehow uh one one of them is true. Um but implications are a bit more interesting. And there's different ways to approach them. You can go for a direct proof, which just means you try to go with all your axioms, but you add A, and then you try to derive B from that.

8:14 This is what you can always try, but often this is uh this is not as easy to do. Sometimes it's useful to flip things around and do an indirect proof, or also called proof by contraposition. That's what That follows again from the logical replacement. So, remember A implies B was the same as not A or B. Now, if I uh if I double negate A, um I can I can rewrite this as And then it again becomes an implication, namely the not B implies not A. Right? I'm I'm using the same same recipe here, but with negations. So, those two statements are the same. A implies B or not B implies not A. And sometimes it's easier to go the other way around.

9:22 That's by contraposition. Uh a close relative is proof by contradiction. That's where you assume the statement is is true, and you try to derive something contradictory from it. Um so, you assume that A and not B are both true. Remember, this is uh that's kind of that's kind of the negation of that. Uh and you try to arrive at a at a contradiction. And we'll see some some examples of this in the in the class later.

9:57 And then another um another interesting template I wanted to list is if the implication has a specific form. Uh sometimes you can you can split cases by adding another thing. So, if you're trying to prove A implies B, you can add another condition C and check if adding that to A helps, but then you also have to add the negation of C. You have to prove it for both cases, but it can still be easier to split them up because you have more to work with.

10:26 I will see see lots of examples of that in the in the module. And the important bit is that it's exhaustive. You have to you have to do both cases C and not C. And of course, you can have more than two can add more than one statement.

10:46 Let's see how far you you already have seen this. So, here's a slightly longer question. I'll have to give you a bit for that.

12:51 All right, while you were thinking, I spelled out the proof a bit more how you may do this in some intro math class. Uh just just to uh I don't know if you have to go in detail. Uh it's probably clear. Um What does it mean that n is an odd number? It means there's another number which is also a natural number, an integer, so that n is 2 * k + 1. It's not divisible by 2. And then using that, you can calculate what n squared is, and you find again it has the pattern of an odd number, namely 2 * an integer + 1. And so n squared is odd as well.

13:32 So not a hard proof um but the the question that we're getting at here is what kind of proof template did we use? And most people may most people got this right. Uh Yeah, 130 140 was where we've been before. Okay, a few more people joined late. That's fine.

13:53 Well, again, don't don't vote for the right answer now. That's kind of Yeah. Or or do if you please, but um it's not going to not going to help anyone much. So this is a an example of an indirect proof. Why? Well, the original statement was again an if-then thing.

14:21 And then um we tried to prove A implies B. But what we actually did is we uh show that if n is odd, then n squared is odd. And uh that is not B. That is not A. With the slight twist that instead of saying not even, I replaced that with odds in this case. I hope that wasn't a trick question, but uh we negated the statement. In this case, there's just these two options. Goody. All right, so far so basic, right? Um if you have to prove a statement of this if and only if form, you actually already know what to do because it's it's two implications ended together. So you just prove the two implications separately. And almost always that's the most convenient way to go about it. It's maybe not the shortest proof, but it's the the easiest easiest route.

15:25 And sometimes you have statements that include sets. Uh Sets are the ubiquitous data type in in math, and so formal statements about algorithms are also formulated in in set theoretic terms.

15:38 A typical statement for sets could be that some set R is a subset of another set S. Again, subset in this sense means uh R and S can also be the same. What that means is again, you're just proving an implication, namely if an arbitrary element x is in R, then it is also in S. Um and uh if you want to prove that two sets are equal, that's an inclusion in both directions. Two sets are equal if S is a subset of R and R is a subset of S, then R and S are the same set. So again, everything kind of boils down to proving implications.