00:00

hi everyone welcome back i’m dave in this episode indirect proof what it

is and when to use it we’ll learn about indirect proofs and of when to use them

and so in this video we’re going to uh first mention that this episode is part

of the series logic and mathematical proofs in-depth tutorials for beginners

and in this episode i’m first going to contrast and compare the indirect verse

the direct proofs and then we’re going to give lots of examples of the indirect

proofs now this video like i said is part of the series and so in the previous

episode what we’ve covered so far is we’ve covered propositional logic

we gave an introduction to it we gave an introduction to quantifiers and we also

talked about inference rules and then in the last episode we talked about um

writing direct proofs and so as i promised in the previous episode we’ll

00:01

compare the difference between the two versions and so we’re going to start

with that first and so let’s get started [Music]

okay so up first we’re going to talk about what are indirect proofs

indirect proofs are sometimes called proof by contradiction and so yeah let’s

get started and see and see what i mean by that so here we’re going to talk

about indirect proofs and that they’re valid arguments and they’re based upon

this tautology right here so proof by contradiction

or an indirect proof right shows that the negation of the statement you wish

to prove implies the pos impossible so an indirect proof is a proof where there

are exact exactly two possible choices and one of them must hold and then so

for for example we can say p or not p so for example suppose you’re trying to

prove the implication q implies p so as we talked about in our previous

00:02

episode we start with q which is our premise

now we want to show p and so we will come up with some steps

and we’ll show p holds and we’ll have a justification for every step over here

that’s very important and we’ll use inference rules to go and come up with

these steps here now it may happen that it may be

difficult to get to p or there may be a quicker easier route to get to p by

assuming not p so somewhere in here we may say not p

and then we may do some more steps and then we may get a contradiction

and so then this would be a conclusion then we would be able to

conclude that p holds right because we know that this is a tautology here now

if you’re wondering that about that so in the previous episode we talked about

tautology so we have true false and then false true and then we have p or not p

00:03

and so we have an or we have an or and this is a tautology so p or not p p

or not p if you can see that right there nope all right so p not p p or not p

and true false false true true true now also a tautology is the p and not p

and so let’s look at that so true false true false

and then this is an and so this would be

false and false so this is uh based upon these two

this is a tautology and this right here is a contradiction so in other words if

i want to show q implies p i start off with q

then i’m going to go down this road here i like to i like to think about it as a

dead end road i’m going to start off with not p now we don’t know if it’s a

dead end or not so we’re going to go down it so we’re going to go down not p

because we know one of these two must hold is this is a tautology so we know

00:04

that one of these must hold so we go down this road and we get to a dead end

we get to a contradiction and then once you know that then you can

say now that p holds right because and this contradiction is because you cannot

have both of them right here so it’s important that both of these are

tautologies right here all right and so then we’re going to say

so to prove that p holds we’re going to disprove that not p holds by getting a

contradiction so if you’re um thinking about this a little bit here’s

the way i like to think about this so i’m going along a road and i’m getting

to some destination right here and i’ve been told that this is the road to get

to it and i and i’ve been told that there is one route along this road here

that gets it to it and then so i get confused when someone when i’m driving

along and i see a fork in the road and so now i’m confused because i was told

that this is the road and it’s the path that’s going to get me there and so now

i’m wondering which way do i go so i start off here to the left and i go

00:05

down it and i get to a dead end and so then so that dead end means you know we

have a contradiction so then i come back here and i’m and i’m right here now so

now i’m known going this way towards my destination and i come back here and i

realize well someone told me that this road does take me there i know that for

sure but this was the dead ends right so now

i know that this must be the road right here that goes on and gets me to my

destination and so that’s kind of the idea behind a proof by contradiction there

now um let’s look at some more um serious examples here though

so let’s look at this theorem here so we’re going to look at this theorem here

first and we’re going to contrast to compare

the direct approach versus the indirect approach okay so if n is odd then n

squared is odd now i’m assuming you know what odd means i’m assuming that you

know that every integer and by integer i mean 0 plus or minus 1

plus or minus 2 plus or minus 3 and so on but i’m assuming you know what odd

00:06

means and i’m assuming that you know that every integer must be even or odd

so first we’re going to start off here with this proof and we’re going to say

suppose n is odd all right so that means there exists an integer k

so that if i divide by 2 i get remainder 1.

now if i square both sides so i get n squared is 4k squared plus 4k plus 1

which is odd so this is odd because this we got a remainder 1 out here when we

divide this by 4. so as this is odd so so this is an example of

a direct proof we start with our hypothesis here and we end up with our

uh conclusion that we need right here and nowhere did we make use of this

tautology right here in our proof so let’s compare that to this part right

here if n squared is even then n is even

right so this is a different theorem but this this theorem i’m going to prove it

00:07

by using the indirect method so proof suppose n squared is odd um

so suppose n squared here is even is what i want to say right there

so suppose n squared is even let me update that here real quick

all right so suppose n squared is even and now i’m going to

oops sorry now i’m going to assume for a contradiction that n is odd i want to

end with n is even so like up here in this proof we want to start with this

right here and we want to end our proof with n squared is odd so hence n squared

which is odd right so that’s how we did that proof there this is going to be an

indirect proof so i’m going to start off with my hypothesis

and now i’m going to say to somebody i’m

using the indirect method and one way to do that is to say assume for a

00:08

contradiction in other words i’m looking for a contradiction that n is actually

not even but odd so i’m going to go down the path that maybe n is odd

all right so let’s do that so assuming n is odd

now knowing that n is odd i can divide it by two and get remainder one in other

words their existing integer k such that n is equal to two k plus one

now if i square both sides here i get n squared is odd now i’m assuming that

hence n squared is even which is what we assumed and

this statement right here says it’s odd and so this is a contradiction it cannot

be both in and on so this path that we went down that where n is odd led me to

n squared is odd but we’re assuming n squared is even so those two cannot go

together so if i assume this is true now it cannot happen that n is odd so

therefore n must be even so this is like going down the path here

00:09

where say i’m going down this path and here’s the path right here represented

by n squared is even and then i’m going to come to a

fork in the road here and this fork right here which is what i’m going to go

down first and it says right here i’m looking for a fork in the road suppose n

is odd so that’s this path down here now i go down this path and i go down this

path a little bit and i get n squared is

odd and then i get n squared is even and odd so when i went down that path i get

a contradiction right there so then i have to back up and now say i’m going

down this path here and that’s this one right here therefore n is even so the

path of n is odd led me to a contradiction so therefore the path

where n is even that has to now be my path here so i just like to visualize it

like that that helps me understand proofs better

especially when the um you know the mathematics is much more difficult than

this but in any case uh this is the direct approach and this is the indirect

00:10

approach here now this is phrased in terms of number theory of course in

direct proofs as well as direct proofs is a proof technique that you can use in

various mathematical subjects number theory topology analysis geometry whatever

all right so let’s do an example here so this example here is going to say

given the two previously proven theorems

right so we have this theorem one that’s

already been proven and this theorem two that’s already been proven and we don’t

know i’m not saying what the q’s and the

r’s and the p’s are they can be from any subject at all um you know

so that’s the advantage of this is we’re just studying proof techniques so it

doesn’t really matter what the q and the p and r are

all right so now we’re going to prove the following theorem so if we know

these two theorems have already been proven our goal is to now prove this

theorem which we could call theorem three if we if we wished if we can do it

of course all right so let’s look to see how to do

that let me move out of the way a little bit here so let me go down to this

00:11

corner here all right so our conclusion so p is a

premise right here and that’s what we’re going to start with right here

now we’re going to use the law of excluded middle q or not q

now this is something that you’re bringing to the proof it’s just a it’s

just a strategy this is just our first draft maybe it works maybe it doesn’t it

will work but um you know this is a creative step here because you can

always invoke the law of excluded middle whatever you want because this is

tautology and but i’m invoking it on cue in other

words i could say this my next step could be r or not r that could be a

next step here instead of my step two here

but i don’t want that to be my next step the reason why i choose q or not q is

because of this theorem right here so that’s a natural choice to try

so that’s my next step now what can i say from here i want to go down the path

00:12

which i’m hope doesn’t work because i want to get to the queue

so i’m going to go down the path of not queue and see what see what happens and

see what see if i can get a contradiction or not if i can get a

contradiction now with these two premises then i know that if i have p

then i have to have q so that’s the goal to get that

all right so now that we have not q we’ll look at theorem one so theorem one

says not q implies r and now we’ll use modest bonus i’m going

to abbreviate that with mp here and i like to identify my steps i’m using it

with so 3 and 4 so that gives me r that’s justified now

and theorem 2 says if r then either not p or q so this is an implication here by

theorem two and now i’m going to use modest bonus again on five and six so i

use modus ponens here and so now i have not p or q

now steps one and three give me the and so i have p

00:13

and step three says not q so steps one and three says i have an and

and now what i’m going to try to do is to build a contradiction from these two

statements here so i’m going to change this p in here into a double negation

and then i’m going to use de morgan’s law right here so this is the negation

negation of a p with an n and you see these both have negations so i’m going

to pull that negation out of the and and to do so i leave i take off this

negation here and i have just one and i take this negation off here so i like to

think about as factoring out a negation and we can do that by de morgan’s law

there so now what we have by this step right here by step 7

and step 10 we have the opposite of that so in other words this thing right here

and it’s exactly right here also so i have this thing and the negation of

this thing and that’s a contradiction right there so that’s a contradiction

00:14

between uh you know step seven and step ten

and i just put it all on one line just so that you can see it right there so

there’s our contradiction you cannot have the same thing

and the negation of that same thing there all right so now that we have uh

our contradiction now we can go back and say you know what assuming not q

isn’t going to work out we’re going to get a contradiction so and we know one

of these two has to hold this one doesn’t hold so this one right here q

must hold so this is this is an indirect proof and we’re looking at steps 3 and

steps 11. 11 gives us the contradiction and so the negation of this right here

has to hold right here which is q all right so uh we can look at a proof now

so i’ll move back up here and say here’s

what a proof would look like if you were to say write in a paragraph form so i’m

going to say assume p now i’m going to say uh assume q right

00:15

here this is our premise right here assume q for otherwise we are finished

so i’m gonna say you know if you already

have q you’re done but if you don’t well what’s gonna happen so if you if you

have negation of q then by theorem one you have r

now by hypothesis we cannot have not p because we’re assuming p

and so by theorem two right theorem two says you either have one of these two if

you have r we have r we have one of these two

but we cannot have this one because we’re assuming p

right so by hypothesis we c we cannot have not p so by theorem two we have to

have the other choice which is q which is where we want to end up being

so this right here is a shorter proof and i’d like to just uh kind of re

reiterate what i said in the previous video

that when you’re writing your paragraph proofs you really don’t want to write

down your inference rules that you’re using here you want to write down the

previous theorems and that’s because your reader who is reading a proof

00:16

should already know what the inference rules are and so we don’t need to write

them down here but we do need to refer because you may have hundreds of

theorems but you should have a small number of inference rules but you may

have hundreds if not thousands of theorems so you want to definitely quote

what theorems you’re using all right so now let’s look at another example here

so in this example we’re going to prove p if and only if q and q implies not p

then we’re going to prove that we can come up with not p

so here we go conclusions and justifications and again let me move out

of the way so here we go i’m going to start off with this is my premise here and

um [Music] i’m going to just kind of write out what

the definition of if and only if it means it means that p implies q and then

00:17

q and applies p also so that’s just a definition of uh if and only if or you

could say that this is a tautology if you want but

any case we have simplification so in other words if i have an and here

i know both of these right so i can now say this right here is true

so that’s the simplification inference rule

um step four that’s our premise right here so i’m writing my premise down

so now when i look at um this i want the not p

so i’m going to go with an indirect proof here i’m going to say p or not p

so i’m going to go down the road which is going to be a dead end i hope because

i want not p so what’s the road i’m hoping is a dead end it’s the p so i’m

going to say p is my premise now so let’s see what happens if i know p

then these two steps here three and six that tells me by modest bonus which i

abbreviate by mp so now i got a q so now i got the q and step four so step

00:18

four and seven again modest bonus and i have not p which is what i want right

so um i have p and not p and this is a contradiction right here

so this step six right here steps five through nine tell me um

we have an indirect proof here and so the this

p right here led me into contradiction p and not p and so

we end up with the other road right so we went down this road right here with

the p and it didn’t work we got a contradiction and so now this one right

here has to be the only way possible so let’s look at a proof

so again i don’t want to mention all the inference rules right so assume for a

contradiction p right because we want to say not p so i’m going to assume the

opposite since p and q are equivalent right

that’s why this hypothesis right here so if we assume p then now we have q

00:19

so by hypothesis if we have q then we have not p

so since p and not p is a contradiction our original premise of p cannot happen

and so there could be a proof by a paragraph there a paragraph form of your

proof there all right so this you know we’re calling

this a column proof we’re calling this a paragraph proof all right so here we go

wins not p right and so we used the um two hypothesis in here

and we came up with the not p all right so very good there is our um

second example there so now let’s look at a third example here

so assume the following so we’re gonna assume this axiom one holds

we’re gonna assume theorem one holds we’re gonna assume theorem two holds

theorem three and theorem four okay and here’s what we’re going to do we’re

going to prove this theorem here so we could call this theorem 5 if we wish

00:20

all right so let me get out of the way here this proof is going to be [Music]

kind of fun here we’re going to have 15 steps on this proof here

all right first step premise there’s my premise right there

so i’m i’m proving i need to prove this theorem i need to prove this implication

holds so p is going to be my premise right here

now i’m going to look at axiom one action one says if you know p is true

then you know that you either rs is true so i’m just stating axiom one here and

i’m going to use modest points and i’m gonna get r or s here

all right so i’m going to go down this road here of s

and see what happens here so i’m going to assume s

so if i do that the theorem 3 says s implies y

then we have modest bonus so now we have y

and then now if i look at theorem one y implies not p and now if i look at these

00:21

two right here i use modest bonus now i have not p so what

in the world did we do here we went down this path with an s and we got not p

but we already have p so that’s a contradiction we have p and not p

by steps one and eight so starting down this path of s right

here led me to a contradiction so now we can say not s

and so that’s an indirect proof right there

so if we try an s we get not s we if we try nest we get contradiction so not s

must hold and also um by the disjunctive uh syllogism we have the r and the

we have the r and we have the r or s so now we can say the the um

well we’ll quote theorem two now and so right so the disjunctive syllogism

00:22

sorry just to follow up on that so we have this step right here

so this is an inference rule that we talked about previously

and we have this right here so these two combine together with this inference

rule the disjunctive syllogism we get r so now i’m going to look at theorem two

r implies x and now i’m going to use mod exponents and then get x

and then i’m going to use theorem four and get x implies q

and then use modest bonus again and then i get q

and so that’s exactly where we want it to go here

so um i use this um or right here [Music] i’m sorry i used the s right here and

got a contradiction so now we know we have the negation of s and using those

two together right there we got the r and that led us to the q

using theorems two and three so let’s write up a uh proof now

00:23

um in paragraph form um so let’s go to the next um scene here

and let’s get started on this paragraph proof here right so proof

so i’m going to assume p here and i’m going to

you know because normally you don’t write things in column format so in

other words can we look at all this and just go straight to the paragraph proof

and the answer is yes so column format is useful but paragraph proof is by far

by far much more popular right so let’s see here assume p now if we have s

right then by theorem three we have the y yet by theorem 1 we would have not p

right so if we have this s we’re led to not p just by looking at the

theorem 3 and theorem 1. so if we have an s then we have a y

and the y gives us a not p so you know what we cannot have this s

00:24

here we cannot have both p and not p we cannot have both of these so we see that

if we have an s well that’s going to lead us to a contradiction so now we can

claim that we do not have an s all right so assume p

now we have um we cannot have s right so we have the negation so now we know p

and not s by axiom one if you have p then you either have r or s

but we can’t have an s so we must have an r by axiom one

now by theorem two if we have an r then we have an x

and so by theorem 4 if we have an x we have a q

so if we start with this p we end up with the q

and so we just prove this theorem right here and

you know column format paragraph format um pick your choice but definitely get

used to both of them when you’re first starting out writing your proofs

00:25

all right so now in the uh next episode we’re going to talk about um proof by

contrapositive and then in the episode after that we’re going to talk about

proof by cases so i look forward to seeing you in the next video in the next

episode and well 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