Indirect Proof (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
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

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