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