Direct 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 and in
this episode direct proof what it is and when to use it
so this episode we’re going to start writing proofs we’re going to work on
direct proofs and we’ll learn when to use them
and so i’m so excited because in this series here
logic and mathematical proofs in-depth tutorials for beginners link below in
the description we have been chomping at the bit we’ve
been waiting and waiting and and and gathering all this information
so that we can start learning how to write proof so we can start writing proofs
and in today’s video we’re going to get to it
so here we go let’s go ahead and get started um in this video in this episode
i’m first going to rehash the inference rules that we talked about last time
i’ll just briefly summarize them we went over them in depth last time we even
looked at all the tautologies and looked
at all the truth tables and did all that stuff and we talked about why we needed

00:01
to use inference rules and so we’re going to refresh your
memory on that we’re going to talk about mathematical proofs what they are
and why we should use them and then we’re going to talk about different
types of proofs and then we’re going to start writing
some proofs we’ll do some example proofs and um yeah i’m so excited
you get ready for this and so let’s go here we go
okay so up first we’re going to uh look at these inference rules let’s combine
these together and look at our first rule here
so we’re going to look at this rule right here we talked about last time
it’s going to be the addition uh inference rule whereas if you have a p
then therefore you can conclude p or q and we talked about the simplification
rule and we talked about the conjunction rule
if you know that you have p and you also have q is true then you have the and is

00:02
true and if you have an and then you know that at least one of them is true now
it doesn’t really matter on the ordering here
in other words for the simplification we could say p and q
and then we can conclude therefore q so this would also i would also consider
this to be the simplification rule same thing with the conjunction you
could have an argument that says q and p and then therefore you can
conclude p and q and so i would also consider this to be
the conjunction rule also now for some other ones
we talked about um modest bonus and again here order doesn’t matter we can
say we could also say this is modest bonus if we have p implies a q
and then we have a p and then we can say therefore we have a q
therefore q must follow so this would be modest opponent’s rule here also
so similarly we could have um modest tones here we talked about before we

00:03
could have these switched but either way
we’d be able to conclude the negation of p um and here’s the hypothetical
syllogism and then we have the disjunction um also and so
these are the inference rules that we talked about um in the last video
so um let’s start out and ask this question here what is the derivation here
okay so let’s move down here and let’s ask what is this
so derivation is a chain of statements connected by meta statements
namely the justifications for each line so we’re going to be
writing our proofs like this it’ll be like line 1 line 2 line 3 this is usually
called the column format but we’re also going to write them in
paragraph form also so we’re going to see a column proof
followed by paragraph proof i think that
you should be uh working on both of them simultaneously but i did definitely

00:04
think when you’re very first starting out a column proof is a good idea but so
we’ll have our lines numbered and so we’re going to have a chain of
statements so we’re going to have a statement right here
and this statement needs to be true and the justification for it being
true is written right here justification right here
and so we’ll have statement we’ll have justification so we’ll write a statement
right here with some p’s and q’s or whatever we’re working with and we’ll
have a justification for it and so this is going to be a proof or
derivation the chain of statements right one two three four connected by meta
statements this is the justifications if an argument has a derivation we say
the argument is derivable so the derivability of an argument is
one thing and the truth of the component statements involved is another so
we’re going to be working down and work as we’re working down that’s going to be

00:05
a derivation but and remember each step along the way you have to come up with
the justification and that justification has nothing to do with the uh argument
that the argument is valid or not so there’s two different uh ideas going
here we have a chain of of statements that are and related to each other by
inference rules and then we have justifications right here
okay so we’re going to say that we can have a derivable argument with
component statements that happen to be true or happen to be false and we can
have a non-derivable argument with component statements that happen to be
true or happen to be false so the point is that the derivability of an argument
is only a question of relation of the conclusion of the argument with the
premises and not whether the conclusion or premises are actually true
so this drivability term here has a lot to do with the validity

00:06
of an argument and that’s why we spent so many episodes over
driving home this idea of what a valid argument is so for a given argument
there is often more than one possible derivation in general it’s acceptable in a
derivation to replace one statement with another that is logically equivalent to
it so we’ll see an example of that here when we work out some proofs so
let’s go on and try to look at the next question now
so what is the relationship between these two approaches so
um a little bit more um understanding a little bit more
background before we get to our proofs right so now we face an important
question given an argument we have two notions whether the argument works
which are that it is or is not valid in other words the

00:07
argument as a whole if it’s valid or not and that whether or not is it is
derivable so the former notion involves checking
truth values so the valid argument is just purely checking truth values we’ve
done with true tables and we we spent um several episodes over doing that so
later is constructing a chain of statements linked together by rules of
inference so our justifications will need to contain the rules of inference
so though it is not at all obvious nor easy to prove
it turns out quite remarkably that these
two approaches while different in nature always yield the same result
that is an argument is valid if and only if it is derivable
so the intuition i get from that is the little building blocks that we talked
about in our previous episode inference rules the building blocks keep us on
track so that our our chain of statements is stays valid and conversely

00:08
as long as our um you know we’re using these um inference rules
we’re we’re going to get something that is derivable conversely if we get
something that’s derivable and we know it’s drivable it could have
come from these inference rules so if we want to show that a given
argument is valid it will it will suffice to show that it’s derivable and
vice versa now um the equivalence of these two results
of these two approaches is a major result in logic and so this is called
the completeness theorem and for predicate logic this was uh first given
by a girdle and we also have the soundness theorem and the correctness theorem
these are really the different names for the same theorem but um so there’s two
different theorems here one going for valid argument is derivable and
derivability means you’ll always have a valid argument all right so

00:09
what are direct proofs right so um direct proofs are proofs that
donut do not use the law of excluded excluded middle tautology which means
that uh all right so this is a tautology right here not p or p
and as long as you’re not using this you’re going to stay away from indirect
proof so there’s to be different types of proofs that we’re going to talk about
we’re going to talk about direct proofs indirect proofs proof by contradiction
proof by cases and so in today’s video we’re going to start
talking about direct proofs now it’s not really exactly clear what this
means um so at this point i would just say
notice that we never use this topology tautology in our in our proofs
um and then when we start talking about indirect proofs it would be much more
clear about what direct proofs are so um in fact today’s video even though
we’re going to talk about direct proofs and we’re only going to do direct proofs

00:10
i really kind of just hope that you get the idea and the understanding of what a
proof is so don’t worry about the word direct right now we will get to that um
and i’ll talk about a little bit more in this video but um you know this this
word right here really comes into focus when we start talking about the
different types of proofs and you know we talk about direct versus
indirect proof all right so let’s look at our first example here
so in this first example we’re going to um make a proof here
and it’s going to um you know in order to make some proofs we
need some previous theorems or some axioms right so this is just an example
right so we’re going to be given three previously proven theorems so theorem one
is p implies a q and theorem two is q this is the same q

00:11
over here q implies an r and then we’re going to be given theorem
3 which are ours implies s now notice i haven’t said what p q and r are
and that’s because the method of proof that we’re going to
use is going to be the same no matter what field of mathematics you’re using
if you’re if you’re studying number theory set theory you know calculus
analysis topology it doesn’t matter and this is p could be a statement in
topology this q could be a statement another statement in topology and right
so so the point is that you have a p here and you have a q and this is the
same q and this is an r and this is the same r and this is you have an s so the
next theorem we want to prove is if p then s so we want to prove this as a
theorem here and the way that we’re going to do that
is by writing a proof and we’re going to write a column proof
and so here we go we’re going to have our conclusions our statements and we’re

00:12
going to have our justifications over here in this column so number one
well this theorem says if p then s so i’m going to start off with the p
here and this is and this is an example of using a direct proof this is
hypothesis and then this is an s so i want to start off p as my premise and
now my last sentence that i get to here i don’t know how many steps it’ll take
maybe it’ll take 200. but my last step i’m hoping it’ll look like s
and i’ll have some justification over here for it and each one of these lines
2 3 4 5 all the way to 200 will need to have some type of justification
and where we use an inference rule over here so this will be the strategy of our
proof is a direct proof we start with p and we end with s and that will prove
the theorem if p then s now it’s actually not going to take 200
lines so let’s see how many lines it does take where would we go after number

00:13
one here p is the premise so i’m looking
right here p is my premise now if i look at over these three theorems here
theorem one theorem two theorem three some of them involve p and some of them
don’t theorem two does not involve p theorem three does not involve p
and all we have at this point is p so it stands to reason we would try to
use theorem one so my step two here is going to be theorem one
p implies a q so all we’re doing here is
we’re saying this is a previously proven theorem we know this is true we’ve
already proven it that’s why that’s what we mean we say is the theorem was
previously proven all right so now i’m going to use a
um justification here inference rule so this is modest bonus and i usually
like to include the step numbers because you know modest bonus has um two steps
to it p and p implies a q and therefore we can conclude a q so we have a p

00:14
we have a p implies q so steps one and two and now paul modesto says we can
conclude a q so that’ll be my line three now and i
can justify that line three by saying modest bonus so this is just for
convenience right here but the the inference will be using is modest bonus
all right so is q where we wanted to end no it’s we want to end with an s so
we’re not finished so now that we have a q um and and in fact we have all these
three statements now so now what would we try to use
well theorem two gives us a q implies an r
so i’m going to try to use a theorem two
next i’m gonna say now that i know about q
i’m gonna use theorem two q implies an r and then i’m gonna use modest bonus
again and now i can claim r and so it looks like we’re making some
kind of path the question is are we ever going to get to s now we know r
so now i’m going to use theorem three r implies an s so we have a connection

00:15
here and again i’m going to use modest bonus
because i have an r and r implies s so modest bonus says
that we can now conclude s and so now we’ve achieved our goal we
have started with p and we ended with s so and we have a justification for each
step a previously proven theorem or a definition or an inference rule so
we have proven this theorem now and so this would be a complete proof right here
um but i usually like to actually also include a paragraph proof
now in my view a paragraph proof is sort of like a summary
and by that i mean you don’t really want to state your inference rules it’s
really not um it’s just frowned upon if you actually
stay your inference rules so we’re going to assume the reader knows how to write
proofs and we’re going to assume the reader of this proof when i write in
paragraph form knows the inference rules

00:16
so we’re just not going to state them so we’re basically going to run through
this proof here again but we’re not going to state our inference rules
unless of course it’s something creative and it’s a very complex inference rule
maybe then we might say but any case but assume p
now i’m going to use theorem 1 and i’m going to conclude q
and then i’m going to use theorem 2 and now we have r
and so that’ll be my next sentence so i’m using modest bonus to link these
together first i know p then i know q then i know r and then
by theorem 3 we’re going to have s and then i’m just simply going to say that’s
all we needed we assumed p and we’ve reached s and that’s all we needed to
prove this theorem here so this could be a paragraph proof depending upon your
audience um but if your audience knows how to
fill in the steps right here then you don’t really need to mention the

00:17
inference rules and you don’t need to write out every single detail here uh in
fact some people would would even write it even shorter than this it really just
depends um but writing the proof out in rigorous uh layout like this and column
format where justification for each and every line
this is a very rigorous and this is rigorous too it’s just more of a summary
point of view all right so now let’s look at a next example
all right so let’s see what we’re going to do for our next example here so we’re
going to prove the following p or q and not q and then p
so we’re going to try to prove this right here
so let’s prove let’s write a proof so we’re going to need our conclusions and
we’re going to need our justifications now notice this is an if then so this is
going to be another direct proof and by direct proof i mean i’m going to start
with my hype my premises my hypothesis here and then my final step is going to

00:18
be my p so here we go this is premise number one
uh this is an and here so it doesn’t really matter which way you list them i
just happen to want to list this one first so that’s my premise
this is also my premise now i’m going to look over my inference
rules and i realize that one of the inference rules is a just disjunctive
syllogism and that’s all i need these two steps right here and i need
this inference rule and i will be able to conclude p
and that’s what happens to be right here and so this proof right here is done
so if you know this inference rule right here then you can just quote it and be
done with your proof and so we would have something like this assume not p
and p or q right there’s my assumptions there’s my premise
and so then i can just say we cannot have q and not q right that would be a

00:19
contradiction right we cannot have q and iq so that’s p follows immediately
the reason why word like this is because i frown upon using an actual inference
rule in the proof and so i think that this is just clear right if you have p
or q and you know you don’t have q well since you know that you’re going to
either have q and not q you cannot have both of them
and you know that you already have this one right and so if you have one or the
other perhaps both then you also have to then you have to
have the p here right so this is a nice um proof here if you know this inference
rule here now what if you didn’t know this inference rule here and you’re not
really following this argument here so let’s back up here and see if we can
write a more um [Music] more basic proof let’s say more of a more of
a direct proof without using so i want to use something like this

00:20
right here i want to use this implication right here to move away from this or
and so let’s see if we can do that here so i’m going to try to prove this a
different way so i’m going to say here step one is going to be my not q
and i’m going to say premise and then i’m going to say p or q also premise
now as you know like i said a minute ago assume we don’t know or we’re not using
the disjunctive syllogism right here so how can we proceed
um just using the other inference rules in fact um is it possible to just use
one inference rule modest bonus is that only one you truly need well any case
let’s let’s just use modest opponents instead
instead of the disjunctive syllogism well first i’ll need some more steps
because we cannot use a modest bonus like this because we don’t have implication

00:21
so i want to uh recall this equivalence right here so this is equivalent to what
not p or q and that’s what i was saying here a
minute ago when i was saying recall this right here so recall this right here
and this is a tautology right here so let’s go back here and see if we can use
this to tautology here um these are logically equivalent to
each other now we don’t have a not p in our proof though right we have we’re
just given p or q so what we’re going to do is we’re going
to also rely upon this to tell you here that p is logically equivalent to not
not p so this p right here i’m going to replace it with a not not p
and so this uh the justification right here is that p is logically equivalent
to not not p and so this goes to what i was
mentioning earlier in the episode here about you can replace one statement with

00:22
a list another statement that’s logically equivalent to it and so i want
to re uh replace this p with the not not p
so now i have a not in front of whatever this is so either not and this is my
thing i have right here so i’m going to replace this right here with a this is
my not p implies q so p implies q whatever is after the not
goes right here so whatever is after this not which is the not p
and then the or changes to an implication and then we have the q so we
have a q right here so this follows by this equivalence right here p implies q
is logically equivalent to p not p or q so these are tautologies right here or
these are logical equivalences right here all right so now

00:23
um we can start to try to make a connection here between these two right here um
but this has not q in it and this has the q in it
so there you know we cannot use modest opponents yet um in fact we can’t use my
exponents at all because this is in the conclusion right here right and this is
not a not p this is a not q so what we can do now is we can use the
contrapositive so we’ll say not q implies a not not p
so this is the contra positive and we can just say contra positive here or we
could just use the logical equivalence uh notation here so not q implies a not p
so this was uh we called this the contradiction contrapositive before
and then now step six here um we’ll go ahead and use this double
negation again so not q implies a not not p so we’ll just say p now and so

00:24
then this is just this logical equivalence again a double negation
and now we have what we need for modest opponents we have the negation of q is
true and the negation of q implies p so now we can conclude p
and this will be by modest bonus i also like to put the steps here so steps one
and step six so one and six and then i’ll say modest bonus
and so we did it we started with these two premises here
premise premise and then we concluded p is our last step right here
and so this would be a direct proof right here because we started with our
two premises here and we use p and we use some logical equivalences in
here to manipulate the p’s and q’s and as you can see that this argument
follows a lot because we’re just using very basic logical equivalences here
we’re using double negation we’re using implication we’re using contrapositive

00:25
and because this argument happens so many times people just give it a name
and they just call it an inference rule the disjunctive syllogism so this is
actually kind of his basic idea behind that
and so we made this proof right here and this was a lot of fun and i think we
should do one more though right let’s do
one more so let’s get um some erasing in here
and let’s look at a third example here now so here we go example three
all right so example three we’re going to prove
we’re going to assume first before we prove something we’re going to assume we
have a definition so we’re going to say a is said to be b
if and only if r implies s so is said to be is what we’re defining

00:26
right here a is said to be b whatever that means if and only if r implies s
now we have an axiom now what an axiom is an action is different than a theorem
an axiom is a beginning statement of your system that doesn’t need to be proved
and so we have an axiom r implies q now we have theorem 1 so that’s a
theorem that was proven based upon our axioms and rules of inference and then
so the theorem one was proven and what was proven was a is c
if a is c then q is t and we also proved a second theorem that t implies s
now i just like to mention one more time that i’m not saying with a and b and r
and q and s and t i’m not saying what any of these variables represent
because um that’s not the point of this it’s not the point to do number theory
or set theory or topology the point is to understand how proofs work and so

00:27
this could be a um an example this could be a theorem
here in any uh mathematical you know subject that you want but our theorem
that we’re going to prove is if a is c then a is b so we’re going to prove that
based upon this other stuff that we’ve already proven and we’ve already worked
out here so and this is going to be another
example of a direct proof there’s not going to be anything indirect about it
i’m going to start with this and i’m going to go directly to this
right here and so that’s the way our proof will be structured i’ll start with
a is c and that’ll be my premise here and we’ll do lots of steps in here
200 2 000 2 million a finite number of steps
it won’t be that many but our last step will be a is b
and each of these statements that we write will have to be justified by

00:28
something that we’ve already established or an inference rule
and so let’s get started so let’s look at the proof here
so i’m going to have my conclusions i’m going to have my justifications and
um so i’m going to start with my premise or you could write the word hypothesis
here and that’s uh certainly a useful word
all right so now um you know where do we go from here a is c where do we go
if we look over here a is c well we have theorem one it says if a is
c then we have q is q implies t so in order to use theorem one we need
to know this first but we do know it so it looks like we can use theorem theorem
one here so that’s what i’m going to go with next is i’m just going to say
theorem one holds right we’ve already proven it if a is c then q implies t
that’s theorem one verbatim right so now if i have both of these i have this one

00:29
already established it’s premise i already have a justification
and now i have an implication where i have the hypothesis right here
so what can we use what’s the justification going to be and what’s our
conclusion going to be so you guessed it it’s going to be modest bonus we’re
going to use step one and two and now we know that q implies t
so there’s something that we’ve gained already from our proof um but
you know just just because we got that doesn’t mean we’re going to use it i mean
you know there’s nothing here saying that we need to use theorem 1. in fact
if you look at the statement right here theorem theorem it’s got a’s and c’s and
b’s in it it doesn’t say anything about q implies t
so is this even going to be useful there’s a lot of times about writing a proof
is it’s not brute force making of truth table that would be way too long
and take way too many steps let’s do something creative

00:30
should we introduce q implies t or not well
the answer to that is um by looking at what this right here means what does it
mean to say a is b right and we have our definition here it says a is b
if and only is so we have to prove this first in order to say that
so in order to finish with this remember we’re going to start with this and our
last step is a’s b well the step before that because the definition says
that is true means we first have to have r implies s
so the step right before it needs to be r implies s because if we can reach
somehow reach this step right here then our definition says we’ll end up
with here which is where we need to end up so the question is now how can we get
this how can we get this q implies t r implies s

00:31
is there any connection between these two right here
so let’s look at some of our other theorems here so
we have axiom one it says r implies t so that kind of gives us a a little bit
of a connection because this has got it q in it
and the axiom one has a q in it and it has an r in it and this has a r in it so
it seems like we would want to use an axiom one to somehow connect these two
together so let’s see what our next step will be my next step is premise r
now why is that our next step well we’re
trying to show that r implies s remember
that’s our second to last step if we get this step then we will get this step by
definition so how do we get r implies s the way to establish an implication is
by first making a premise so that’s going to be my second premise now it’s a
little bit confusing to some students who are just starting

00:32
proofs because it looks like i said asc is a premise
but it didn’t give us an r here did it so you have to realize on your own
that in order to get an implication you have to start with this hypothesis
so now my goal will be to get an s if i can start with an s and fill in the
steps sorry if i can start with an r and fill in the steps with justifications
over here and get the s then these steps will prove that r implies s
which will then give me the a is the b so this is a very common practice in
mathematics is because we’re not robots right we don’t just um you know
see it and go step by step by step you often have to do some kind of intuition
some kind of step building it’s like if you’re solving a puzzle you don’t just

00:33
pick out one piece and then peck out the second piece and they automatically
connect together right you have to you know look at the broad
scope of the pieces of puzzle and so how to piece them together right so that’s
what i’m kind of doing here all right so i’m doing r as the premise because i
want to establish the implication so now that i know r what will step 5 be
well axiom 1 here says r implies a q so that could be my next step right there
right so r implies a q now i’m going to use mod exponents
because i have these two right here together um i’ve established that r
implies q and i’ve established r as a premise and
so now i’m going to use modest opponents here to say q
now if i look at these two steps uh 3 and 6 i’m going to use modest
poinus again i know q is true i know q implies t is true

00:34
so now we have t by modest ponies so we started with the r here on step
four and we went to a t but that’s not quite what we want we want an s
so how can we go from t to s that’s what theorem two provides
so theorem two says t implies an s now i’m going to use modest bonus again
and now i’m gonna say an s and so now i don’t need that
now as we as we mentioned if you start with an r as a hypothesis
and you reach an s then we have the implication right here
so this is steps four through nine tells us that we have an implication
right here so you could say four through nine or um
you could say uh let’s see here what would it be um
yeah i could just we’ll just say four through nine there steps four through
nine and then now that we have our implies s
now that we know by definition that a is b
and so there’s our proof right there i find this to be

00:35
a very um interesting proof i find that if students are able to understand this
proof because it involves you making hypothesis on your own in order to prove
an implication and so that’s a common um trouble spot for students when they’re
starting to write proofs is knowing to when to make your own premise i think
it’s pretty clear to make this is your premise because this is given to you as
something to prove you have to prove this so it says if right here so that is
an obvious uh premise there to me but to prove asb to come up with the
ending of that you have to look at the definition and see oh i need to i need
to show an implication i need to show that in order to get that and in order
to show an implication i gotta start with an r and end with an s
and the other stuff in between is just there to get you to that implication
all right very well so now let’s see a paragraph proof

00:36
let me move out of the way over here i’ll move up here so
again we don’t want to mention all the modest ponies in our paragraph proof but
we will certainly uh require require the hey what theories did i use what
definitions did i use you know what was the strategy behind the proof
so assume asc that’s our hypothesis right there that’s where our starting
point is and then i’m going to use theorem 1 and so now we have q implies t
and now to prove that asb were assumed are so i think this is the proof this is
the key statement especially if you’re learning beginning to learn how to write
proofs this is a very crucial statement i think if you skip over this statement
right here that this proof could be very difficult to read for a beginner uh the
goal is to prove this so i say that the to prove asb we’re gonna assume are
because we need to show an implication right so by axiom one so that’s why i
come up with this we have q so now we got to q

00:37
which now yields t so i’m following him through this argument right here i’m
leading them through this argument here and then by theorem two we now have an s
so we assumed an r is true and then now we have s is true and so now we have
this implication holds and so that’s all we needed
and notice i didn’t even bother to end with a is b
because it’s a definition i mean we could say we have shown our play s is
needed and then by definition a is b so um you know that’s certainly something
you could write out but i i think this is a good enough right here you want to
say are implies s as needed and then you
could say if you wanted to you could say by definition um but you know
this is good this is good paragraph proof here
all right so there we go there’s three of our first examples of writing proofs

00:38
we did uh three direct proofs and in the next episode we’re going to talk about
indirect proofs and we’re also talk about proof by cases
proof by contra positive so by the time that we’re done with all these episodes
you’ll be um you know on your path to writing mathematical proofs in whatever
subject of math you choose so i hope you’re getting lots of value from this
video if you have any questions leave some comments below i’ll get it right to
them and then um well i look forward to seeing you in the next video
and 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