00:00

everyone welcome back i’m dave in this episode um proof by cases what it is and

when to use it we’re going to look at proof by cases and when to use it

and so we’re going to first talk about how this episode is part of the series

logic and mathematical proof in-depth tutorials for beginners and this series

here has all the prerequisites that you need to get the most out of this video

that you can so we talked about propositional logic we talked about the

quantifiers we talked about inference rules and how to write proofs this the

topic of this episode right here is um proof by cases so first we’re going to

start off with an example then we’re going to look and

compare and contrast the different types of proofs and then we’re going to look

at some more examples and then we’re going to look at what i

call logical discourse what it is and how it works and then at the end we’re

00:01

going to talk about mathematical exposition so all these things are

great ideas and great topics for people who are just starting out learning how

to write proofs and so by now you should have learn watch the episode on direct

proof indirect proof and proof by contrapositive and so this uh episode

here will take us one step further and give us another type of proof that we

can use in our toolbox all right so um i’m excited and i’m ready to get started

[Music] okay so up first we’re going to look at

this problem right here proof by cases so let’s put this together here and

let’s look at this ethereum one and theorem two

and we have this theorem three here and i’m gonna go up here and i’m gonna say

this theorem three here is a complete set of logical possibilities r s and q

that is one of the statements is true and only one of the statement is true so

00:02

these are three proofs previously proven theorems and what we’re going to do in

this example right here is we’re going to now prove the theorem p implies a q so

you know this looks like typical things that we’ve seen before r implies not p

s implies not p um but this right here is kind of worded

in a way it’s kind of wordy but you know just for the first time you’ve seen it

um so what someone has proven in theorem three

is that one of these three statements has to has to be true

and if one of them is true then the other two are not true

so that was already proven and so now we’re going to prove this theorem here

and we’re going to see how to do a proof by cases all right so this is our

previously proven theorems and this is our next proven theorem

all right so here we go so let me move down here

and let’s go here with our premise first so p is our premise right here

and now i’m going to state by theorem three right here only one and only once

00:03

this is a shorter way of saying it r s and q

right one and only one so this is going to give us our cases we’re going to have

three cases here now what is the case we want to be true we want to be true

the q we want q to hold so let’s look and see

what happens with these other two here so in the first

in the previous episode where i talked about uh indirect proofs i talked about

how you had a destination that you were trying to go to and you were driving

along a road and someone told you that this road leads you there

and then you come across a fork in the road and then you don’t know what to do

you were told this road gets you there for sure so you know this road gets you

here but the question is how you know you have a question in here so what you

do is you try to go down this path right here and then you realize it’s a dead

end and so then you back up and then once you see that’s a dead end then you

back up right here and now you know this road right here has to connect so

00:04

that’s proof by indirect proof or proof by contradiction

proof by cases is different so this is when you have a splitting of two

indirect proof what if you have multiple right so now you get here to this

branch here and you have four different routes to go but you know this one right

here will get you here someone told you that whatever so you know that you can

get there so you’re taking this road and you’re taking this road and you get to

this fork right here so then you just say okay i’ll pick one i’ll pick the

leftmost one maybe that’s your strategy then you get to the dead end and then

dead end is usually some kind of contradiction or something and so then

you backtrack and then you try the next one you get another contradiction so

then you backtrack you get a contradiction or maybe you don’t get a

contradiction so then you come here but if you come here and you make it all the

way then you got to your destination and then you’re still left wondering what

about this one over here so that’s proof by cases we’re going to

check out all the possible cases and see that this q must happen

00:05

from the three different cases here so here we go

so um this will be case one we’re going to try out the r

now we can use theorem one r implies not

p so now we have theorem one and now i’m going to use modest bonus again there’s

an episode over the inference rules there um mp stands for modest opponents so

we’re gonna use steps three and four and now we can know now we know not p must

hold and so now we have p and not p and that’s a contradiction we can’t have

both of them this is just a straight up contradiction

and so what we can say is now is not r all right so what about the s now well

that’ll be our case two so case two we have theorem two

now we’re gonna use modest opponents again to get the not p

and now similarly we have the p and not p contradiction so this should say

00:06

uh one and ten not not t that should say one i think i just didn’t see that

um all right and so then twelve uh step twelve is

not s right and then step two here is you know by step two one and only one

that one does not work that one does not work so by step two q has to work

so how would we write that up in paragraph form so let me move up here so

we’re going to start off by assuming p just like we did

then by theorem three this is exactly there are exactly three cases to consider

so if r then we have not p by theorem one which is contrary to hypothesis we

get a we get a contradiction similarly s is contrary to hypothesis so

i just kind of summarize the step here because it really relies upon modest

ponens and theorem two so i just say similarly to theorem one right theorem

one and theorem two are similar but it’s just got an s in it so i just say

similarly s is contrary to hypothesis there hence we have q as needed so we

00:07

ruled out these two other cases and we said you know there’s two cases to con

there’s three cases to consider two of them don’t work the last one does work

here so this would be a nice proof that would summarize these 13 steps here

all right so there’s your first example of a proof by contradiction

and now let’s look at comparing different types of proofs all right so very good

so we’re going to look at something like this right here you might have seen

these type of arguments before in precalculus where you have

the statement like this if this equation is zero then x is one right so we have

uh three different ways and we which in which we can prove this now we can prove

this directly so we can start off by assuming this p right here this is a

mathematical statement right here it’s either true or false right assume this

is true then well we can factor and that implies that either this one is

00:08

zero or this one is zero and but we know that this one cannot be

zero right here because x is a real number right you cannot have x squared

plus one equals zero there’s no number you can square and add one to it and

then get back to zero right it just does not happen for real numbers right so it

must be the case that this one is zero and if this one is zero then that means

that x is one right there so this would be a direct proof of this mathematical

statement right here well we can do proof by contrapositive

so that would be x is not one if x is not one then this is not zero so here’s

how that proof would work assume x is not one all right that’s the negation of

the conclusion then x minus 1 is not zero just you know

if that’s true then that’s true also since x is real we know that this

right here is not zero also and therefore

00:09

it follows that this product is not zero and this product if you multiply it out

you get this right over here so upon multiplication we obtained that this

right here is not zero so there’s a whole lot of negations

there that’s proof by contradiction in this example

all of the negations really kind of cloud the real issue direct uh proof

would be better in this example here what about proof by contradiction

how would that work well we start with this

and then we assume for a contradiction that this right here cannot hold we’re

gonna get a contradiction because actually it must hold so um

well so if that’s not one then this is not zero

and if we multiply this out right here and that should be a three right here

so then this polynomial right here um is equal to just factor it out

and you know this is not zero so it must

be that this right here is zero but that is a contradiction because there’s no

00:10

way that x squared plus one is zero because x is a real number if you square

a decimal it’s still positive even if that decimal you started out with was

negative and then you’re going to add more to it and you’re never going to get

to zero right so that’s a contradiction so therefore this assumption right here

of x not being 1 is false so that that must mean that x mi x equals one is true

must be true all right so there’s three different uh

ways of proving it but you know i think this proof right here gives us the most

value um that’s just my opinion here this proof right here gives us the most

value it has all the essential arguments and i didn’t really need to appeal to

that many negatives negations right there so it really just depends upon

your statement what you’re trying to prove which of the three versions is better

and you know in this example all three were pretty straightforward to come by

now another question you might have is um which

00:11

can you combine these three arguments together and make a

longer shorter argument or something like that but

that’s not really what you can do your your proof needs to have a overall valid

structure to it um and so yeah so make sure that we

understand what you’re doing when you start writing your proof which route are

you taking um in your proof strategy when you’re trying to prove something

all right so here we go what type of proof is this

so here we’re given the four previously proven theorems theorem one two three

and four and we’re going to try to prove this

theorem here now which is simply stated as t

that’s a theorem we’re trying to prove and so i’m going to give you a proof and

your goal is to answer what type of proof is this here we go

conclusions justifications so i’m going to start off with a not t

that’s going to be my premise so that should already give you clues to what

00:12

type of proof this is now i’m going to use theorem 4 and i’m

going to use the contrapositive so now i have not t implies not s

and then now we have modest bonus right here and so we can conclude not s

and now we have theorem three i’m going to use the contrapositive and a double

negation all all combined together so theorem three says

not r implies s so the contrapositive is not s

implies the negation of the negation of r right and so i’m using the

contrapositive of this but i’m also using double negation right here because

the negation of the negation is just r right here all right so good so step five

so now we can use modest bonus and we have r now

and now we have by theorem two are implies p theorem two

modest posts again now we can conclude we have a p

00:13

and now i’m going to use theorem one theorem one says

not p and q right so they both both must be true and

so there we are so now i’m going to use simplification if i know they’re both

true well then i know that this one at least is true so that’s called the

simplification we covered that under the inference rules uh episode

and then now we have p and not p right so we have a p and we have a not p

so by uh step um seven and nine 7 and 9 or we could have um

well this is a contradiction p and not p we don’t need any steps

there that’s just a straight up contradiction p and not p

but uh i think we’re putting them together using seven and nine so i put

them together using seven and nine so yeah we should say seven and nine here so

00:14

seven and nine all right so now we have t

so we had a contradiction so we started off with not p sorry not t

and we got a contradiction and so we have to end up with t so this

is an indirect proof and steps one through ten show that

all right so there we go there is a uh another indirect proof for us there

all right what about this one right here um are there any cases in it um do we

need to use any uh by the way one to say that the overall structure of

the proof here is an indirect proof because i started with uh the negation

of what i wanted and i got a contradiction however inside of it we

did use contra positive so you can use contrapositive whenever you want but the

overall structure of the proof is an indirect proof

i just want to mention that because sometimes when you’re writing proofs so

00:15

your proofs may have 100 lines in it and your overall proof will have a strategy

if your overall proof may be by contra positive might maybe by cases so you may

have a case one in here you may have a case two in here you may have a case

three in here and you may have a hundred line long proof and you may have cases

in it now inside of each one of these cases it may be 20 lines long

and inside of one of these cases right here you might have a claim

and then ins that claim is proven by contradiction or uh contrapositive

so your overall structure of your overall proof will have a structure to

it a type of proof strategy but each inside of each of these parts you may

have sub proofs now a lot of times when your proof gets 100 lines long or longer

you want to break it up into smaller proofs and we’ll talk in the end

best ways to do that but this is just 11 lines all right so that’s it

00:16

all right so here we go with our next example here

all right so in this theorem we have theorem 1 theorem 2 theorem 3

and so here we go with this theorem right here let me get rid of that so not

q implies s and where that’s we’re going to try to prove right there

all right so here we go um i’m going to start off with not p

that’s my premise there so let’s see now i’m going to use theorem 1.

so notice i didn’t assume not s so my strategy on this proof is probably going

to be a direct proof i’m just going to start off with not q

and then my last step hopefully will be an s and then if i can combine all those

steps together then i have what i want right there so let’s see here

so i’m starting off with not q and then i’m looking at theorem one and

i’m looking at the contrapositive not q implies not p

so that’s theorem one the contrapositive of theorem one

00:17

now i’m going to use modest ponies here and i get not p

and now i’m going to use theorem 2 here not p implies r

so then i’m going to use modest bonus again to get r

and now i’m going to say by theorem 3 r implies s

so now i’m going to use modus ponens again and i get s

and actually that’s what we wanted isn’t it we we started with not q

and i used the theorems and modest bonus

together and i ended up with s and there were no other cases there were no other

branches so this is just a straight up direct proof um so this is steps um

one through seven gives us the implication here

now before we move on here i wanted to kind of refresh your memory on the

theorem that we covered in a previous um previous episode so this theorem was uh

we discussed the serum and why it’s true in a previous episode i just want to

00:18

refresh your memory on it and um yes let’s read it real quick suppose

that the statement r is a consequence of the premises p1 through p2 pk

and also suppose another statement is a consequence of the same premises right

here and r then s is a consequence of just p1 through pk

now that that’s you know a lot to take in so i want to kind of give an

illustration of of how you can use this theorem here

because right here i said steps one through seven so i want to really drive

home this uh idea here and make sure that you you know that we understand it

here so this proof has eight steps to it so let me come over here and and go one

through eight so let’s start here one two three four five six seven

and then eight good so now i’m going to um name this one

00:19

right here p1 because either because this theorem is stated in terms of p1

through pk so i’m going to call step number one p1

and whatever is here i’m going to call that p2 and so on p3

but now but let’s look at the end so suppose r is a consequence of these p’s

and then the s is the consequence of all the piece and the r so the s is

going to be the last statement here so so this s is different than that little

s this is just s is this whole last statement here so that’s going to be my

s here and the statement right before the the s is the r

and so in this example i have p4 p5 and p6 so i have

p1 through pk in this example it’s p1 through p6

and then i have an r and then i have an s and so now let’s read this theorem

again to make sure that we understand it in terms of this proof right here so

00:20

suppose that the statement r right here is a consequence of the premises right

here so these are previously proven statements right here

and so we can consider them premises when we’re looking at uh these ps and

this r and also suppose that another statement s is a consequence of these p’s

and the rs then the conclusion is this theorem says

must happen that s is a consequence of just these in other words s is the

consequence of just these so knowing that r is the consequence of all of these

and s is a consequence of all of these i now have that s

is just a consequence of just these so let’s think about this again so now i’ll

write p1 p2 p3 p4 p5 and i’ll have an r and i’ll have an s

and so what we’re saying here is that s is just a consequence of these six

00:21

statements here that’s applying the theorem to the proof here one time

now if we apply this theorem here again now that we know that r which has been

relabeled p six has been relabeled to r and this is still p5 p4 p3 p2 p1 but now

we can re reapply the theorem again and now say that this r is the consequence

of all of these and the s so now s is a consequence of just these five

and so we can continue this argument out finite number of times and our last one

will be p1 r and s and so now we’ll apply the theorem one

last time and we’ll say that all of these p’s was just one now in this in

this case so if if r is a logical consequence of p one

and s is a logical consequence of these two then the conclusion is s is just a

00:22

consequence of p1 in other words if you apply this theorem right here to just

this then we get p1 implies s which is exactly what i wrote down right

here so the p1 is the statement right here and the s was this whole statement

here uh sorry this whole statement here and so now we can say by steps so by

steps i really mean i’m applying this theorem here

and there would be like an illustration on how that argument works it’s

important that the proofs are finite number of times finite number of steps

and we apply this theorem here and that way we can know that the previous steps

gives us not q implies s which is what i wrote here and last step here so i hope

that refreshes your memory of this theorem and helps you illustrate how we

can take those steps there all right very good so now let’s look at

00:23

um what is logical discourse so logical discourse what is the pattern

what is the pattern in logical discourse so pattern goes like this

first we give a set of primitive undefined terms

for example in geometry you might say a point is undefined or a line is

undefined and then what we want to do is give a

set of axioms about how those points and lines

will behave with each other right you know you have some kind of intuition

about points being on lines not lines being on point right so you

want to have a set of axioms that illustrate or manifest your intuition

and these are unproven statements about the primitive terms so we make a set of

undefined terms we make a set of axioms then all of the terms of the discourse

all all of everything that gets generated afterwards are defined in

terms of the primitive terms or the previously defined terms which

00:24

were defined in terms of using the primitive terms

and then all other statements in the system are logically deduced so you have

to have an underlying logic from the axioms and these are called the

theorems of the system so this is what we’ve been

improving upon uh for thousands of years first starting perhaps with thales and

then euclid and other great names such as hilbert to name a few

all right so what is mathematical exposition though because you know this

is logical discourse and this is sort of how it runs technically but in practice

it runs a little bit different so what is mathematical exposition so we often

communicate by distinguishing different types of theorems so for example a

theorem is sometimes called result now if you’re reading textbooks or

taking courses or trying to communicate with other mathematicians

00:25

there’s usually a reference reference to the word theorem and so

but there’s other ways of mentioning other type of results right because you

can prove lots of different statements in mathematics so one of the first

things you might come across is something called a fact one plus one is

a fact no one would call that a theorem um otherwise there would be

you know no meaning to the word theorem right so proposition

no reference reference to the word theorem right so a proposition is a

minor theorem but it’s more important and more general than a fact

right but it’s not as prestigious as a theorem a lemma is often used in

a technical way which can be more uh can be it’s usually less

important than a theorem but it’s usually very important to help you prove

a theorem so stating limits before proving a different difficult

complicated theorem is usually helpful for example what if

00:26

you have a great theorem that you proved but it takes two 300 lines so you may

pull out the most important parts of that theorem and state them as limits

especially if you can apply those limits to other theorems so this is like

building a bunch of tools these limits right here

then then we have claims claims are often used when you’re writing a proof

because again your proof may have several hundred steps

and you know you may need a sub proof or a little claim and it’s kind of taken

into account its whole argument all by itself it may have a

different structure to its argument than the whole

than the whole proof so you may state a claim and usually you’re going to state

a claim when the result that you’re trying to prove is technical and it but

it’s not really worthy of making a limit out of it you don’t really see any

utility in it it’s just something that needs to be proven and you’re long proof

all right so kolari isn’t comes after a theorem right so you prove a big theorem

then a collar could follow usually that’s how it works not always but

00:27

so you have a result important enough to state on its own so theorem is usually

quite general it’s quite meaty it’s it’s like a landmark thing

then you may have special cases of your theorem so cholera is often a special

case but that special case is important in fact sometimes when you’re proving or

sometimes when you’re trying to solve a mathematical problem often is a very

specific type of problem that you’re trying to solve and in

the course of solving that problem you may have come across a generalization

which warrants a theorem so you may state a broad prestigious theorem then

as a special case of that theorem you can write out a collary which was a

solution to your problem that you started with that has its own interest

so that’s the difference between these different types of of

terms that you’re going to run across when you’re reading mathematical

exposition all right so um that’s it for uh this

00:28

video and um i hope you enjoyed it and i look forward to seeing you in the next

episode have a great day if you like this video please press this

button and subscribe to my channel now i want to turn it over to you math can be

difficult because it requires time and energy to become skills i want you to

tell everyone what you do to succeed in your studies either way let us know what

you think in the comments