Video 0-2: §0.1 Proof templates

0:00 <Untitled Chapter 1>

0:03 So, welcome back to Comp 526. Still unit zero, but now actual content. Uh even though not algorithms per se, but uh some proof techniques that we will um use or at least rely on implicitly in in the module. Uh some of you will have seen good deal of this uh but some others won't, and so it's kind of a quick run through what I think could be useful without going into very much detail. Uh some of the things will be practiced a bit more in the tutorials, so you will have a chance to uh practice that a bit more.

0:39 Learning Outcomes

0:42 I tried to put some some learning outcomes for each and every unit on the slides. Um and so here the idea is to know certain standard strategies. Uh this will become clear what I mean by proof strategies. It's just um a way to get started. It doesn't really help you to solve any particular problem, uh but it's it's a a scaffold or a template to start from. Uh and we'll look at the typical types of statements that we meet in in mathematics, discrete mathematics, and in computer science. Uh and particularly um mathematical induction is among those templates one that is particularly powerful because it gives you a totally different angle to prove things uh compared to the more direct ways, say. Um and then we'll we'll see how proofs connect to algorithms. There's two things that people want to prove about computer programs. Uh usually they want to prove that they terminate, that they eventually finish for a computation where this makes sense. Uh and they want to prove that it computes the correct result.

1:44 We won't obsess much with either in this class. Uh we'll often discuss more informally how uh how we can argue that a certain algorithm computes what we what we want it to compute and what we think it computes. Uh but I want to highlight how you could at least in principle do this. It's just a lot of effort and a lot of work, and most of the time um we will stay on a higher level. But I think it's insightful to learn on a small example how this would look like if you zoom in into all the nitty-gritty details. That's what I want you to take from this.

2:20 Outline

2:22 And that also reflects the the structure. We'll start from the basic proof templates, work our way up to induction, and then have a look at these applications. So, if we start from from nothing, uh you can ask what a proof is to start with. It's actually a very interesting question. Uh I might post them some some further pointers on Campuswire if you're interested. It's a it's a philosophical question if you come from from ancient Greece. Um They already uh asked this question. And you might have seen geometry proofs in school. That's usually the the first type of very formal uh way of of uh specifying proofs. And then I took till the mid of the 20th century to really nail it down uh what a proof is. I think now we have a definitive understanding, but who knows? Uh but I think it's very solid. The idea of a proof um is to have uh sorry for the pun of bulletproof statement uh a bulletproof argument that something is correct or something is true.

2:29 What is a formal proof?

3:26 And so uh while um we will in this class mostly convince other humans that a certain statement is true, which could be the topic of politics as well. Um we use this just as a as an excuse to not always go to all the details just because we won't get much uh further in this. Uh it just takes very much uh a long a long time to write all the details down. Uh but we want to write proofs for humans so that a qualified human can fill in all the missing steps. That's the idea. And the missing steps would be a sequence of statements that are derived from axioms. These are things that we accept as true, and well, we'll maybe see some examples. And and inference rules, which are uh very syntactic rules just operating on symbols, how to go from one correct statement to another correct statement. And if you can puzzle something together starting from axioms and only using the inference rules that are allowed, that is a formal proof.

4:33 Uh we won't usually um go down to this level. We'll use a little bit of um notation for this. And it's uh I'll keep it a bit informal here, but we use uh statements, and these uppercase letters represent a certain statement. I used examples here that are somewhat from the real world, but you'll see that it often has limits. So, most of the time when you want to prove something, it's more a statement about numbers or maybe about programs and algorithms. So, we can have different statements. Say, it rains, which is false at the moment, and the street is wet, which interestingly might be true depending on where you look. Uh if we have a statement, we can negate it. So, we can put this this negation sign in front of it, and we read this as not A. If you spell it out uh in English, you would say it does not rain, so you natural language has slightly different constructs, but we have the same conceptual ideas. You can take a statement, you can negate it by putting not in there in some way or another.

5:42 You can also take two statements and put an and between them. That means you require both of them to be true. Um you can do something similar, you can put an or between them. That means one of them can be true or both. So, that's um an important thing to point out here. If we say A or B, it's fine if A and B are true.

6:11 There is also um the exclusive or. Uh maybe in in English you would say either A or B. Uh there's no very standard notation for this. Uh but let's say we just write XOR, uh which stands for exclusive or. So, it's either A or B, but not both.

6:34 That's just for context. Um I don't recall that this pops up anywhere in our module. Uh more interesting are the things the the last two points. An implication is if A then B in natural language. Um but it's probably better to keep this in mind. Uh we'll come back to this in a second. Uh but implication means if A holds, then B has to hold. An equivalence between two statements sometimes also called a characterization. Uh in in English we say A holds if and only if B holds. So, uh you can also write this as an implication in both directions. A implies B and B implies A, then they are equivalent. Okay? Uh just quick hands, has anyone not seen this at all?

7:30 This type of operators and rules, etc. Everyone has seen it? Good, then um the next question is easy for you guys. Um I'll start it. Okay. So, you should be able to vote.

8:14 It was revealing the correct answer already. A few more people than 38 40 Yeah, sorry for spoiling this one uh as you've already seen if you were paying attention. Uh yes is correct.

9:17 Uh the more interesting part maybe uh why. So, the the trick about this statement is uh okay, unless you're believing in this weird conspiracy theory yeah, that you might have heard of, the flat-earthers. Uh I think most people believe the earth is not flat. So, that makes the statement kind of empty. Uh if the earth were flat, then maybe yeah, maybe ships fall off the rim and all sorts of weird things happen. But we don't really believe this is of any relevance uh because already the premise is false. Uh but the thing is these statements um of this form, implication A implies B. So, what we have is uh two statements. A, the Earth is flat. And B, ships fall off the rim.

10:09 And the statement we're concerned with is an implication. A implies B. That's what we claim. And if you remember from the last slide, this was the same as saying B or not A.

10:26 So, these two are are equivalent. Let's Let me write this with these uh three the equality sign with three things. It's not supposed to mean they're equal, it means they're they're equivalent. We could also say uh the the arrow that implies each other, but you have to be um a bit careful what is part of the statement and what is part of a statement about statements.

10:52 If you take a look at this, then uh we know A is false. So, this this or is already true because A is false. So, that's all we need. And it doesn't matter that B is um is probably also false. Right? So, the entire statement is true. Which means you can make any claims after an if then after the then if the if part is false. Okay?

11:16 Uh that's just how it is defined. An implication is defined to mean exactly this. And that's important for you because if you want to prove something, sometimes you have to uh use the fact that if A is already false, what you're trying to prove is is trivially true. Meaning you don't have to do anything else. So, you have to know that an implication has this meaning. You might not agree that this makes sense, uh but the rest of mathematics has decided this is the way to go, so you're you're kind of out of luck, I guess.

11:51 So, that's the first thing um to pay attention to. I think all the other notions If you look at all the other operators and their English language equivalent, they're doing what you intuitively expect them to do. Implication is the only kind of slightly tricky one.

12:12 All right. Uh with that setup, we can now look at some proof templates, where uh I called them strategies before. So, uh these are templates how you can structure a formal proof. And the idea of presenting them is to help you get started. The hard The tough part is then filling the template. Um but without the template, it's even tougher, so they still help.

12:36 Implications

12:38 There's different templates depending on the type of statement you try to prove. If the statement you try to prove is an implication, like we just had the example, there's uh there's these four different ways how you could go about with this. You could do a a direct proof, which means you assume that A is true and then you try to show with uh logical reasoning that B is also true. That would have failed in the previous example, because if we start with assuming the Earth is flat, uh you become a weird person, I guess.

13:16 Another option is um an indirect proof. So, um you start by assuming that the the B part, the conclusion, is false. Like in our case, uh ships don't fall off the rim. Okay, maybe we can live with that because there is no rim. And you can then derive that uh also A has to be false from that. So, if ships never fall off the rim, the Earth can't be flat. Maybe. It's a little shaky argument. Um but because not A was easy to prove if you're already convinced of that, uh this would be the way to go in this example. We assume not B. If you believe that if you believe whether ships can fall off the rim or not doesn't really make an uh a difference, you assume this here. This is your starting point of the proof. And assuming this, you want to show that A is not true, which we already believe, so that's the end of the proof for us.

14:12 Okay? Um something similar, but um slightly different in how you structure it. We'll see um more examples of this later in in the class. That's often a convenient thing to do. Uh try to derive a contradiction by assuming A is true, uh but what A would imply if the statement was true is not true.

14:40 Uh it's sometimes easier if you just um go back to the to the symbols. So, if A implies B, you could start with A and not B and try to bring this into a conclusion into a uh a contradiction. So, that's called proof by contradiction then. And something that's slightly um orthogonal to the other cases, you can do this in general in a sense, um you can distinguish different cases, and that's it's looks like in the formulas it doesn't look like it helps much, but often this additional assumption makes uh different arguments easier go through. So, you can say I'm not only assuming A, but I'm assuming A and C, some additional um assumption.

15:24 And those two together imply B. That's good, at least at least partway there. If you can also show that A and the negation of C also imply B, uh then you're you're actually done. You have distinguished two cases, and maybe the proof was different in the two cases, but taking the two proofs together proves the entire statement that A implies B.

15:48 Many puzzled faces. Uh this is all a bit dry, right? Um let's practice this a bit. Uh you read the question. I'll make sure that I don't reveal the answer this time before we get started.

15:53 Clicker Question

16:09 I opened the question already, but maybe before we dive into this, let me do the actual proof. And your task is to find out what proof template I was using there. That's the options. So, we have this uh innocent statement, if n squared is an even number, then n is also even. If you think about it, maybe try a few examples, seems true, right? How would you prove this? Well, one way to go about proving it is say, let's assume n is odd.

16:41 So, if n is odd, that means I can write n as uh in the form two times k plus one for uh some Well, let's be generous, some some integer k. We don't care about negative numbers for now. Okay?

17:04 Uh what does this mean? Well, that means if I take n squared, I can write n squared also in this form. And if I uh if I pull this out, So, you can write this again in this form.

17:40 And this is another uh integer. Whenever I start with an integer, I can take a square, multiply by two, and add another integer, I I will never get uh a fractional number. So, this means that n squared can also be written in the form two times an integer plus one, which means it's an odd number. Okay, great.

18:02 That's the statement we we're trying to prove. Okay, sorry about the End of proof. Uh something like this uh as straightforward as this might be something you do in some number theory discrete math 101 class.

18:26 You may have seen this proof before, or it may be obvious to you how this works, or it may not be so obvious, but I'm just asking you what proof template did we follow?

18:38 And so, you haven't voted on Slido yet. Now is the time to do that. So, we got 63 people on the last question. 20 more to go? If you don't have an idea, maybe this time it's fine to just guess.

19:25 So, again, remember uh I want to give you participation marks for answering all those questions, but it doesn't matter if you're right or wrong. Uh it's more just to make sure you're you're active.

20:02 I won't show the answer before I close it. Three, two, one. All right. Now we want to see Uh I stopped it, but uh what I actually wanted to do is um lock it. Sorry.

20:34 Not really. All right. Most of you got this right. Uh it was an indirect proof. Um but maybe it's it's insightful to still uh quickly highlight what A and B etc. was in this case.

20:59 Uh so shall we briefly highlight what A and B was? Uh if anyone feels comfortable shouting it out. The statement to prove was A implies B. Where can I find A?

21:22 Nice. Yeah, that's it. So that's A and that's B. And so this was a bit sneaky. I didn't say N is not even. I said N is odd, which is the same thing just uh to confuse you guys a bit. But that's the same as not B. And then we follow this implies again, same trick, not A. Odd is the same as not even.

21:47 Do we need to discuss a bit more? Confused? Uh oh, sorry. Yeah. Uh we can try to get both on one screen. Oh, not on your screen.

22:08 So you didn't see what I was writing. That's the confusion. So that was the proof and here's my nice way of marking A and B and not A and not B, etc. Okay? So the confusion was more that I wasn't showing my screen and not that you're not following the proof.

22:43 You should tell me if I'm doing nonsense. All right. That was all about implications. There's many other types of statements we sometimes want to prove. Uh one example is equivalences. So these characterizations um but these can conveniently be reduced to the case we've just covered because an equivalence is just two implications taken together. So uh indeed the typical proof template for proving an equivalence is showing both their both implications separately.

22:47 Equivalences

23:17 Uh sometimes a direct proof showing the equivalence is works works as well, but it's usually easier, just a little more to write, to do the two implications. So it's actually nothing new. Um sometimes we want to make statements about sets. For example, that uh one set is a subset of another. So here R is a subset of S in case you haven't seen this symbol before, but I I hope you have. Uh again we can reduce this to something we already know. It's just an implication saying that whenever I take an element in X, this implies that this same element is also in the other set S. Okay? So in a sense, it's just uh a hidden implication.

23:28 Set Inclusion and Equality

24:04 And similarly, if you have two sets and you want to show that the two sets are equal that's a hidden equivalence. Um which you could you could prove like this. If X is in R, that's equivalent to X is in S, and then you can prove both implications. Another way to arrive at the same thing, uh set equivalence is the same as saying one set is contained in the other and vice versa, and then you also get both implications. Okay, looks like everything's really an implication and there's nothing new under the sun.

24:36 Uh I'm I'm running fast through these, but stop me if if something's unclear. I think these are these are not your problem.