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

0:00 <Untitled Chapter 1>

0:04 good with the uh terminology said let's have a look at a few proof templates and these go step by step through different kinds of statements any statement has a different template that you can apply or a set of templates the most interesting one are the most interesting type of statement is the implication just because it's uh it pops up in different other statements and it's just the most commonly found one so if we try to prove a implies B we can just try a direct proof we we start from a remember um approve is axioms and inference and and statements derived by inference rules from previous statements if we prove an implication we start with the axioms and a that's also something we can start from and so a direct proof would try to derive B by following through these steps starting from a and the axioms that's the obvious thing to do but you can also do slightly different things you can reformulate the statement first if you go back to this equivalence then you find that a implies B is logically exactly the same as not B implies not a and sometimes it's more convenient to do such an indirect proof or fancially called proof by contraposition because you swap these two things around

0:09 Implications

1:33 before I could start with with a and try to prove B now I can kind of go from B to a but I have to negate things so I start with the negation of what I want to prove and try to show the negation of what I start with so we could try yeah we'll see examples later

1:56 slightly related but a little different in um the way you carry out things is approved by contradiction so you assume that the statement you're trying to prove is not true and that comes down to assuming that a is true but B is not true so if a were true and the implication is true then that would imply B so we're assuming something that we don't believe and then you try to derive a contradiction from that so you try to arrive at a point where you have I don't know x equals five is one thing but you could also show x equals seven and so these two things contradict each other which means one of the premises must have been wrong that's another way to show implications that's often is laughing well maybe this is something about human nature I don't know it's often easier to do fine contradictions uh than direct proofs I don't know yep

3:17 create is used by contradiction you can assume notice those are not easy it's true I should have noticed implies of India is full so if not as recruitment is the indication is false so you know that if not else in Christ but you don't think that something is possible report like X and with X so sure sure

3:48 and the application is also called then the left hand side was before so fourth Enterprise ports is valued for three implied forces yeah exactly okay so uh I mean to summarize this a bit unfairly you can apply proof by contradictions to all kinds of statements by just negating what you try to prove and try to arrive at the contradiction uh it's just for implications usually

4:15 um well it's it's maybe less obvious um and often effective um yeah let's uh let's try it again get through some of these uh these things because there's a few things I want to touch on later

4:36 another thing that's very versatile and often helpful is to distinguish cases it just happens that sometimes it's easier to make your problem harder instead of doing one proof you do two but each of them is easier so you have some other condition C and you can have a and C or you can have a and not c those two together are everything you can have with a uh but sometimes the arguments get easier if you have additional ammunition I'm sure we'll find some examples later in the module for this um the important bit here is that it has to be an exhaustive case distinction you have to cover all possibilities that looks super obvious when I write it like this in in terms of these logical formulas it's much easier to lose some case when you're folding this up into a big proof so it can help to spell out explicitly I'm looking at let's do a case distinction I'm looking at this case now this case now and there should be a last case everything else then you have covered everything

5:49 let's do another quick example just to see if this made sense to you guys oh come on so you take your time I'll just start writing some things thank you

8:14 all right I think we have is there anyone still voting gonna lock it uh never mind I mean you can you could cheat and change your answer but uh you don't gain anything from it uh so it's it's an indirect proof if we do this um come back to it uh I thought it's helpful to actually do the Fool Proof just to show you a quick example so it's not a super important statement for algorithms but well so if if n is odd that means we can write n as 2 times K plus 1 for some natural number k that's the definition of art at the end of the day and depending how you formulate it so this this n0 is just the natural number is zero one two and so on uh and then if if we have that knowledge about n we can have a look at what N squared looks like and then that's just a little bit of um uh algebra arithmetic depending oh you want to phrase it and we arrive at something where

9:23 N squared has the same form so that's some number K Prime the important bit about this is that K Prime is 2 K squared plus 2K if K is an integer then this K Prime will also be an integer we're just doing operations that stay in the integers so that one again is a natural number and that implies N squared is odd because we've written the number in the shape that is required for odd numbers to exist two times something plus one right

9:58 um apart from the usual type of miscalculations when I do this on the spot that's the proof that is meant in this question and if we want to highlight why this is an indirect proof we can split up the individual parts so that's our statement a that's the statement B now we showed n is odd implies N squared is odd that's the same as not be it's just slightly hidden because I I change from odd to even but for in for integers it's either what is any integer is either odd or even so not even means odd as odd as it sounds

10:06 Clicker Question

10:50 and that's not a right so we showed the implication not B implies not a and that's uh an indirect proof uh questions so far foreign that's what I mean by templates right you start with a statement like this and maybe it's obvious for you if you think about a few examples writing down a rigorous proof is actually quite challenging even for these very simple ones or maybe exactly for these simple ones and having the right proof templates at hand you could just go through them and often one of them is is applicable and here this turned the task into a simple computation because we could take the knowledge and this art get some tangible thing out of it write it as 2K plus one and then do something with that knowledge

11:47 other types of statements that we will often meet um are these and this will be I'll go through these quicker because they're usually falling back to what we already know if we want to prove that a if and only if B this equivalence we know that that's actually just two implications so it means we have to prove two implications separately and most of the time that's the easiest way to go about it it makes the proof twice as long maybe at least at least logically but usually it's much easier to prove an implication than to directly prove an equivalence so whenever you see an equivalence and you're asked to prove it your automatism should click in and say okay I have to do to these two things prove to implications instead

12:33 Set Inclusion and Equality

12:38 apart from combinations of logical statements we'll often talk about sets and other kinds of mathematical objects that reduce the sets at the end of the day and one of the simplest is we can have a set of some objects s and another set and we may want to say we may want to prove that R is a subset of s right if you know this symbol I I hope that's the the subset relation it means every element in R is also an s you can rephrase that as an implication um if you want to be picky we should have a 4X for all X in front of this we'll talk about these weird quantifiers in a second so you can you can rephrase a statement about sets as an implication and we know how to deal with implications don't we uh we can also sometimes want to prove that two sets are equal but s equals R is the same as s is contained in R and R is contained in s so again we can go back to implications all the way through and we know how to deal with those that's my assumption for now