Proof By Cases (What Is It And When To Use It)

Video Series: Logic and Mathematical Proof (In-Depth Tutorials for Beginners)

(D4M) — Here is the video transcript for this video.

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

About The Author
Dave White Background Blue Shirt Squiggles Smile

David A. Smith (Dave)

Mathematics Educator

David A. Smith is the CEO and founder of Dave4Math. His background is in mathematics (B.S. & M.S. in Mathematics), computer science, and undergraduate teaching (15+ years). With extensive experience in higher education and a passion for learning, his professional and academic careers revolve around advancing knowledge for himself and others. His work helps others learn about subjects that can help them in their personal and professional lives.

Let's do some math together, today!

Contact us today.

Account

Affiliates

About Us

Blog

© 2022 DAVE4MATH.com

Privacy Policy | Terms of Service