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