Proof By Contrapositive (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 uh proof by
contrapositive what it is and when to use it
is all about the contrapositive writing proofs so um i’m excited to see you and
i can’t wait to get started but first i want to mention here logic and
mathematical proofs in-depth tutorials for beginners so this episode is part of
the series and the link is below in the description and um the prerequisites for
this video is in the series so in this series we cover uh
propositional logic we cover predicate logic uh you know quantifiers and we
also introduce how to write proofs we talk about inference rules and in our
previous episodes we talked about direct proof and
indirect proof in our last episode so this episode we’re going to talk about
proof by contrapositive and so let’s see what’s in this site inside this episode
today proof by contrapositive we’re going to do a first example then we’re

00:01
going to talk about some rules of writing proofs and we’re going to do
some more examples yeah so i can’t wait to get site started and
let’s let’s go ahead and get started [Music]
all right so first up is what is a proof by contrapositive
um so let’s talk about that proof by contrapositive um [Music]
so i first want to review uh what we talked about last time so last time we
talked about um indirect proofs or proof by contra contradiction
and we talked about how that relies upon this tautology right here and so we
talked about what an indirect proof is um and and how it’s structured
and we also talked about these two theorems here
so we have this theorem here if p is odd then p squared is odd and so here’s the
proof that we went through right here so p is odd and there exists an integer k

00:02
hence p squared which is odd and so we went through that proof here slower and
and we tried to understand how this is a direct proof
and then in the la and the next theorem here we talked about if p squared is
even then p is odd um and so we went through this proof here also
so when we went through those uh you know proofs right there in the uh
previous episode we did a lot slower and we talked about what the difference
between a direct proof and indirect proof is
but i wanted to mention the connection between all of this right here and the
contrapositive so if we look at this theorem here here’s one way to prove it
here’s one way right here we can say assume for contradiction and so this is
an indirect proof right here now if we look at the contrapositive of this
theorem right here we could say the contrapositive right here would be if p is
and we’re looking for the negation of is even so now we’ll say is odd then

00:03
p squared is and then we’re looking for the negation of this right here so this
is the contrapositive of this theorem right here is odd
and you can see that that’s this theorem up here exactly
so you could prove this theorem is true simply by looking at the contrapositive
and then we could use this proof up here which is a direct proof
or if you’ve had already proven this then you could say this theorem is true
it’s just the contrapositive of this theorem up here without having to repeat
the proof but that’s the connection between these two statements and so i
wanted to mention that before we go on and talk about that so in a previous
video if you’re not if you’re not able to keep up so or not able to understand
this make sure and go back and look at the episode the previous one indirect
proof where we talked about all this and if you don’t even know what uh
the contrapositive is then we have a video for that also so we talked about
uh implication and when we talked about propositional logic and we talked about

00:04
the contrapositive which would be not q implies not p so that’s the
contrapositive of an implication right there
so in any case um yeah check out the previous series uh check out the
previous episodes uh to make sure that you’re ready to to rock and roll with
this video right here all right so let’s go ahead and look at um an example of a
proof by contrapositive here so um here we’re gonna go with this
theorem right here we’re gonna say a b and c are integers and we’re going to say
prove that if a this energy right here a does not divide b times c
then a does not divide b so that’s what we want to try to prove now
this has a lot of negations in it it says does not does not
right so if you’re if you don’t have any intuition or if you have better
intuition about what it means to say it does divide then you may want to rewrite
this uh so that it’s you know it’s the contra positive right so proof by contra

00:05
positive that’s exactly what we’re gonna do
so we’re gonna assume let me move out of the way over here um let we’re gonna
assume that a divides b right so that’s the the negation of the conclusion so
we’re going to start with that right there’s assume a divides b
now we know what this right here means because we have a definition for it
we’re going to say there exists an integer k such that b is equal to a
times k and then if we multiply both sides by c right here
then we have this right here where k c is an integer so i just use
associativity of the integers right here where and this right here is an integer
so therefore we have that a divides b times c
and so this would be a proof of this theorem over here using the contrapositive
and um you know i think that you may write it like you may say it
like this but i think it’s more intuitive to write a proof that looks
like this right here all right so what are the three golden

00:06
rule rules for writing a proof so um the first one the first thing i want to
mention is excuse me whenever you’re writing a proof
it must be technically valid and it must
be sound so not only the inference rules that you’re using
you know you make sure you have a valid argument and make sure that every step
in your proof is justified so if you have those two things then you can talk
about a proof now that’s not what i really talking
about golden rules right that’s the just
a technical part so the golden rules are there’s three of them so the first one
is be creative so now be creative but not at the expense of
the other two rules that i’m saying so if you can somehow enlighten your readers
then creativity can make math fun interesting um etc so number two

00:07
and this goes towards number one you want to be creative but exactly how well
you want to develop your intuition um not only your intuition but the reader’s
intuition about what should follow next about how the theorem is important how
is it a theorem as opposed to a fact or proposition
um and then you should know your audience and i think that that one’s the
most important is these first two uh go towards number three which is know your
audience right who are you writing for are you writing for other research
mathematicians and you’re a research mathematician then your proof will look
a lot different than if you’re say a student in your writing for your
fellow students or if you’re writing for a just a general pop popular article on
mathematics right you want to know your audience and once you know your audience
then you can try to be creative and then you can try to develop your intuition
here so i think these are the three golden rules for writing uh proof um in fact

00:08
these um you know uh can be not just for mathematics or
not just proofs but these are three good rules just for writing anything
in any case let’s do a proof by contradiction uh sorry proof by
contrapositive now so um here’s going to be our example
here assume the following we’re going to assume this axiom right here
and we’re going to assume that p implies not y
and we’re going to assume axiom two not p implies r and then we’re going to um
we have a previously proven theorem p implies not z we have theorem two
x implies either q or z theorem 3 says r implies either x or y
and now this is the theorem we want to prove now we want to prove that not q
implies not p you can see the negations right here so
if if one of them was negated or both of them

00:09
that’s sometimes a clue that you want to use contrapositive but not always
sometimes you’ll have just a q implies a p
and then you still may want to use the contrapositive so it really comes down
it boils down to looking at your proof and trying to write the best proof
possible so often you will when you first write a proof you will revise it
and revise it just like you write anything else all right so here we go
so even though i’m going to show you one draft of this proof this you know this
proof that you know when you’re first starting out proofs are hard and you
want to come up with multiple drafts until you
get the hang of it and then after a while you can start proving this with one
draft and you can start kind of seeing how to go
all right so here we go proof by contrapositive so i’m going to start
with the negation here so the negation of the negation of p is just p so that’s
going to be my premise so that right there kind of suggests that i’m using

00:10
proof by contrapositive all right so um now axiom one so action one says p
implies not y and then i’m going to use modest
opponents here to come up with the not y not y must be true now okay
um so that stands for modest bonus and now i’m going to use law of excluded
middle i’m going to say q or not q here so
i’m trying to prove not q or sorry we’re
we’re doing the contra positive which is p implies q
so i’m trying to end with q in my proof we started with p we’re trying to end
with q now i’m going to use a lot of excluded
middle and so right now i’m going to say well what’s so wrong with using the not
q that’s going to be my premise now now if that’s my premise because i want the
q here’s why we want the q so i want to get a contradiction now so here’s my
premise and let’s see if we can get a contradiction or not all right so i’m
going to use axiom 2 i have not q so i’m going to use axiom2 not q implies

00:11
r and then i use modest bonus and i get r now so now let’s see here
i’m going to look at theorem three theorem three says r implies
x or y so there’s theorem three and now i have modest bonus again and i’m going
to say x or y and so now i don’t know which one i should use
because there’s no x and y’s up here so you know like here i had a choice um
and i chose the one i don’t want trying to show it’s a dead end so that i could
end with the one that i do want but here
we just have an x or y and we don’t know at this point so i’m going to just
choose one i’m going to choose x first and we’ll have to come back and look at
the y here right so let’s choose the x now i’m looking at steps three and nine
i have a not y and i have an x or y and so if you’re familiar with the
disjunctive syllogism then that’s an inference rule and so we can conclude

00:12
that x holds and so now i don’t need to do the or
all right so now what about theorem two here so theorem two says either q or z
and so then we have x and we have x implies so now we have modest bonus q or z
now i want to end with q so but what’s wrong with the z so this
is an or here so at this point we just know one of them is true or it’s an or
maybe both but but at least you know so let’s try to get what’s wrong with z so
z is my premise now and now i’m going to look at this um
theorem 1 here and this is theorem one here and i just write the contrapositive
out and i’m also using double negation right so the negation of the negation of
z z and then the negation of p so that’s the
contrapositive so i have these two now so 13 and 15 give us um

00:13
not p from modest bonus and so i have p right here and i have not p right here
so that’s a contradiction so in fact this z choice right here
doesn’t work out leads to a contradiction so we have to say not z right
z led to a contradiction so not z has to be true so that’s by indirect proof
and so then now i have here q or z and i have the negation of z so i can
use the disjunctive syllogism and so now i get q right here
and so now i can say we have q and that’s the negation of the negation of q
and so by steps let’s see here uh 5 and 19 right so we haven’t we have q or the
negations and by 5 we have not q right in other words we have not q and we have
the negation of not q and both of those can’t be true that’s a
contradiction so we’re going to have to end up with the q

00:14
so we have refuted this right here in all possible cases and so this q
then must follow right here so it all split right here for the first time
and we used our premise here and we used this right here and we had multiple
cases to look at and you can deal with the multiple cases different ways i
chose to use a disjunctive syllogism and i used it multiple times but in either
case you have to rule out all possible cases so this is proof by contrapositive
here we prove that p implies q we started with p
we ran through all the possible cases and we had enough theorems and enough
tools to do it so then we were able to end with q so we showed p p implies to q
and the contrapositive is what we wanted to prove which is not q implies not p
all right so very good so let’s get started on the next thing here okay

00:15
so we’re going to write a proof now and we’re going to assume uh p let me
move down here we’re going to prove this theorem right
here and this time we’re just going to write a paragraph proof
so i’m going to assume p so i’m using proof by contrapositive i’m going to
assume p and then by axiom 1 we have the y we have the negation of y
now remember as i mentioned in the previous episodes when we start writing
the paragraph proofs we’re going to remove references to our inference rules
all right so assume for a contradiction not p
so when the overall structure of this proof is proof by contra positive but
inside the proof i’m going to use a proof by contradiction so i’m going to
say what’s so wrong with not q right so by axiom 2 that gives us r
and then by theorem 3 we have x or y in case we have x
right so we’re looking at x or y well let’s see what’s wrong with that one in

00:16
case we have x then by theorem two we have a q or z
um but we already have not q so we have to have z then okay by theorem two if
you have x you either have q or z but we already
have not q right so then we have to have z right there so that’s where i’m using
the disjunctive syllogism right there now not p follows by theorem one
because z implies not p the contrapositive of theorem one and so
this contradiction shows right we have a contradiction because we have not p and
we have p so hence y follows so we we started with the x here a
branch here x or y and we chose the x and we got a contradiction therefore the
y must follow yet now we have y and not y
and so in fact we cannot have this not q right here so we have to have the q
um so this contradiction right here this this assumption right here leads to

00:17
this contradiction right here so therefore in fact we have to have that um
q here all right very good so um you know there’s uh different ways of
proving this right here this was one way with 20 21 steps here
there are different ways did you have to use proof by contrapositive uh usually
the answer is no you don’t have to but sometimes you may want to sometimes it
may be more intuitive or maybe you may give a more creative argument using
proof by contrapositive positive so right now let’s see if we can go and
write a slightly different proof here so um let me see if we can get that
going here so i’m going to um show you a different way perhaps and
so how would we start this uh proof here let me move up here um

00:18
and then so what i’m going to do is i’m going to start off with
step number one here is going to be um got to get a good marker here so step
number one here is going to be not q and that’s going to be my premise
so i’m just going to try to go directly here i’m not going to do the
contrapositive so i’m going to start with this my premise here
okay so now i’m going to use the axiom one i’m going to say y implies the not p
or sorry p implies not y i’m just going to use it straight up so axiom one
actually sorry that doesn’t really help does it right so i want to use not q
implies r and this is axiom 2. so axiom 1 doesn’t help us at all because we have
a q right now right so i’m going to use axiom 2

00:19
and there it is and so now i’m going to use modest bonus and i’m going to get r
so i’ll say 1 and 2. okay now where can we go from r so we have
r implies x or y so let’s try that x or y and that’s theorem three
um and then now we can say are our implies so now we have x or y modest bonus
and then three and four and now we have um let’s see here we can
use the let’s go with the x first so i’ll say premise
and for step seven here i’m going to use um theorem [Music] two

00:20
if we have x then we have q or z right so let’s write that down x implies q or z
and that’s theorem two all right very good um so now let’s look at
uh modest bonus again so we’ll say q or z
so modest bonus and then we have um six or seven six and seven
all right so there could be the first eight steps are we going to get there
faster than you know 21 well let’s go one more step here nine
we have q or z so let’s go with q as our
premise now remember we’re trying to end our proof with not p um
and here we have q or z so i’m going to say q
and then all right let’s go up here to step 10. now we have a contradiction
because we have not q and q and so i’ll stay i’ll say that the
justification is steps um one and nine and then number 11 here

00:21
we’re going to say now we’re going to say z
so we tried q contradictions so let’s try z now um so we’ll say here step 8. so
now we have z implies not p and that’s theorem one contrapositive
contra positive right theorem one that says theorem one right there and
then that’s z implies not p so if z z implies not p so step 13 would be not p
and so this will be modest bonus 11 and 12. and step 14 would say
that we have not q so not q implies not p and this will be steps

00:22
um 1 through 13. right we have steps 1 through 13 here so
we have q implies not p which is exactly what we wanted are we done
is there anything else to do here um well let’s go with 15 here did we do
both choices on this we did q we got a contradiction we did z we got what we
wanted um here we did the x ah we didn’t do the
y case yet we chose the x and we went when we went we got what we wanted but
what about the y’s so now y is going to be the premise here
so what’s the case if we have x we got what we want what’s the case if we have
y well let’s see what we’re going to get so we have y is the premise now and now
i’m going to use um axiom one the contrapositive y implies not p
so we’ll just say axiom one contra positive 17 here

00:23
we have modest ponies so now we have not p so modest ponies
and we have 15 and 17 and step 18 here we have not q implies not p
and that’s why steps um 1 through 17 1 through 17 is good
all right so this could be an alternate proof here
the overall structure was not proof by contra positive
um but i did use contrapositive of some of the uh statements up here
so there we go there’s that proof there and let’s see here
yeah so that’s it for this episode right here so i hope that you enjoyed this
video if you did subscribe and like and i’ll
see you in the next episode where we’re going to talk about proof by cases so

00:24
i’ll see you then [Music] i’ll see you then 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