Proofs in Quantified Logic (QL)

hello and welcome back to Phi 320 deductive logic today we're starting our final unit on proofs in ql um so let's get into it so um a few things you should know from the get-go about proofs in ql they work the same as proofs in SL except we use the sentences of ql instead of the sentences of SL we have introduction and elimination rules for our quantifiers our Universal and existential quantifiers we have a new replacement rule which we call the quantifier negation replacement rule that's based on the relationship between the existential and the universal quantifier and we have identity introduction and elimination rules for the identity connective so let's talk about these additional introduction and elimination rules first so perhaps the simplest quantifier rule uh we have is the universal elimination rule if you have a universal statement on line M you can replace it um with a statement with no Universal quantifier and the variable replaced with a constant so if the variable is X we can replace it with the constant like C right and here you see it um represented with the meta variable script a script X script c um for example right if we have the uh statement for all X MX then rxd we can apply the universal elimination Rule and replace the X with whatever quantifier we like could be a as on line two could be d as in line three any constant will do um and if you think about it this makes sense because if it's true for all X then it's going to be true for any um any object that's represented by one of our constants now I want to say something about this um notation we use uh for the universal elimination rule it allows us to create what we call a substitution instance right so when we have a universal quantifier uh case like for all X and we replace the variable with a constant we call this the substitution instance and we call the constant that we use in a substitution instance the instantiating constant right um so the uh Universal elimination rule just allows us to replace a universal statement with one of its substitution instances and replace the variable with an instantiating constant let's look at the next rule which is also pretty straightforward it's the existential introduction rule um it's it's also a direct inference Rule and it's it makes a certain amount of sense we if we have a sentence with a constant in it we can replace that with an existentially Quantified sentence with a variable right um so for some a with a constant C we can replace that with there exists some X ax and again this makes sense just based on the definition of the existential quantifier it tells us that there's at least one thing right um that has of which this statement is true and um on line M we have that one thing uh uh spelled out for us right here are some other examples of how we can use the existential introduction rule we've got on line one a sentence with uh constants and no quantifiers and any of two through six here are legitimate applications of the existential introduction rule so you notice on line two for example we've replaced just the final D in R A with an X right um where is on line three we've replaced both A's in Ma and R A with an X but on line four we've just replaced the a in the um in the ma right and not the a in the consequent of the conditional right um so the X that we introduce with our existential quantifier introduction rule can replace some or all of the occurrences of whatever our constant C is right um it's very flexible and you see in F line five and line six we can even apply the rule multiple times to deal with multiple constants the universal introduction rule is a little bit more complicated right it looks a lot like the existential introduction rule right with a caveat right so we have some line M that has a sentence with a constant in it right so call that sentence a call that constant C we can replace that constant C with a variable and apply the universal quantifier but only if the constant C does not occur in any of the premises of our argument or in any undischarged assumption in a sub proof only if you have got it there totally arbitrarily um can you use it in a universal introduction okay um so what does that look like let's look at an example I have here a proof that starts with a simple indirect proof um that proves a theorem that we proved a version of in L previously right in in one of our homeworks um and it is a pretty straightforward we assume for the sake of a conditional introduction DF right um that's an atomic uh sentence with a constant F reiteration rule we bring it down to line two and that gives us this conditional we know this is a theorem it's a topology we've shown it multiple ways in past units right if DF then DF right now that we've got that and since F doesn't appear in a premise there are no premises in this argument and since we've discharged the sub proof so it's no longer the Assumption of a sub of an undischarged subproof we satisfy that condition on this Rule and we can um eliminate the constant replace it with the variable in this case z to get line four and use the universal introduction rule the reason I can use the universal introduction rule in this way is because I could have picked any constant whatsoever a b c d e f Etc doesn't matter right um it is arbitrary if it's arbitrary then the same form of this sentence three should apply to anything whatsoever because I didn't pick out anything specific right um I don't have any conditions that are that are holding me to F the final and most complicated of our basic uh quantifier rules is the existential elimination rule right um and we represent it in this way we need an existential statement um with a variable in it um we need to create a sub proof um and we need to derive some conclusion that is independent of the substitution instance we assumed for our sub proof so let me walk you through this I have some existential statement there exists some X ax remember my X and A here on line M are meta variables it could be any variable XYZ could be any more complex sentence which we call a with the script a um on line N I start a sub proof by assuming a substitution instance of of line M right so I've replaced all the instances of the variable x with the constant C and I have uh started a sub proof the C can't be a constant that's already in M right it can't appear in the existential statement itself right it also can't appear in any undischarged Assumption of a sub proof that we're still in it can't appear in a premise of the argument it has to be a new constant right and then I need to derive some conclusion call it B that doesn't have that constant either so C cannot appear in B it cannot appear in uh the original existential and it can't appear in any premise or undischarged assumption um and again this is to capture the fact that it has to be an arbitrarily chosen constant right and you have to get rid of that constant before you exit the sub proof because we know that something exists that satisfies a right that's what line M tells us but we don't know what it is right so we're using C to refer to it temporarily but we don't know that c is actually the thing right we're just using it as a placeholder this will make more sense if we look at an example so we've got two premises here premise one gives us this existential uh there exists an xsx that we're going to apply the existential elimination rule line two gives us this simple conditional uh for all X if SX then TX or all S's are T's um more colloquially that we will use to do our derivation we start on line three with a sub proof and our subproof starts with a substitution instance of line one right that's the existential where eliminating right um I chose a here at random right um it doesn't appear in any previous part of the proof that's crucial um and then I work through the proof line four five and six fairly straightforward I apply the universal elimination rule to line two there are no conditions on the constant I use there because it applies to all X right so I can do the a again um and then a conditional elimination rule to get line five that works just like SL I apply my existential introduction rule right which I can do um without any conditions on the um on the constant I've chosen right and I get there exists an XTX right now line six there there exists an XTX there are no variables in there most crucially the variable a does not appear and so I've satisfied uh my desire to get some B some specific B that doesn't have the constant in it now I can close my sub proof discharge my original assumption um and uh we represent uh the rule in this way right um existential elimination line one tells us the original existential that we're eliminating lines three through six are the lines of the sub proof and I've repeated the way this is all way this always goes I've repeated on line seven what I had on line six just outside the sub proof okay so that's how the existential elimination works I've stepped through it kind of slowly because it is I think the most difficult of these rules we also get a new replacement rule for ql which we call quantifier negation and this just depends on the way the two quantifiers are defined in relation to one another right the negation of a universal is equivalent to the existential of a negation and vice versa right so I can move the negation in or out of the quantifier and it flips from being Universal to existential in this way right um and and this is a replacement rule so we can apply this to partial sentences we can apply this to parts of our of our lines right um whereas all of the existential um and Universal introduction and elimination rules have to apply to the the whole sentence with the quantifier is the main connective we're looking at we also have identity introduction and elimination rules remember from the earlier unit where we introduced the identity predicate it is a pred predicate right um a relation specifically a two-place predicate um but it's also a special logical connective as a special logical meaning which we use the equal sign to represent the introduction rule for identity is simple we can always introduce C equals c for any constant right any constant will be equal to itself right um that's just True by definition right and so we can always bring this online right um it doesn't seem obviously super useful but in certain kinds of um indirect proof situations you can use it um to to your benefit more useful in doing proofs involving identity perhaps is the elimination rule right if we know two constants are equal if we know some constant C and some constant D are equal then any um any sentence a that has constant C in it we can replace it with the constant D we can if we know that two constants are equal we can substitute them one for the other in any statement right um we can also we can replace D with C we can replace C with d they can be traded back and forth right um and so those are the special introduction elimination rules that we get for the identity predicate what I want to do next is I want us to look at some examples I want you to pause the video and try providing proofs for these uh these three arguments um and then we'll check our work together okay so what I'm going to do now is I'm going to open up carnap and uh we'll we'll try to prove these three arguments so here we go with our first argument which I've already put our two premises here and we what we want to get is for all X ax then CX right so I'm going to start just by thinking about okay what I've got I've got these um Universal quantifiers here so um what I'm going to start with is just manipulating these by using the universal elimination rule so let's pick the constant a to do um the elimination on this first line if a a then ba a that's Universal elimination on line one and we can do the same for line two that's Universal elimination on line two that's nice because it gets us some conditionals that we can work with here what I'm going to do next is I'm going to apply the hypothetical syllogism right that tells us that we can conclude if AA then CA through hypothetical syllogisms on line three and four right another way to do this would be through an indirect proof to get a conditional introduction now because my constant a uh doesn't exist in any of my premises I haven't done any assumptions for a sub proof so I don't have to worry about that either I can go ahead and reintroduce my Universal quantifier to get for all X ax then CX that's my Universal introduction rule on line five and that completes my proof let's go on to our second example here I have um a universal that's a little complex I've got this if ax then BX or or CX I've got Ag and not BG I want to get CG okay so first again let's let's manipulate what we have to get rid of that Universal quantifier so I'm going to do a g then BG or CG Universal elimination on line one now I have this conjunction on line two so I can disaggregate this use my conjunction elimination rule on line two to pull out the AG the AG is the antecedent of line three so I can um use my conditional elimination rule to get BG or CG that's conditional elimination on line three and four and then I want to get I want to get that CG out how am I going to do that well I got not BG in that Con in that conjunction from before so I can do conjunction elimination again to get not BG and then if you look at five and six that's the form of our disjunction elimination rule so that can get me CG through disjunction elimination on line five and six and that finishes our proof note that if we wanted to we could not do Universal introduction in here to get ax CX through Universal introduction on line seven because the term G is uh here carap says it's not fresh which is a funny way to put it it appears in premise 2 so we can't rely on it for this right we can't use it in this in this case all right let's carry on to the third proof I hope you did well on the first two so this thir third proof we have again um the same first premise for all X if ax then either BX or CX um but I have this existential there exists an X ax and not CX and I want and I want to get there exists an X BX right so I'm going to start again the same way I'll even use the same uh constant I'll cheat a little bit and copy paste here right that'll work now um because I have an existential here instead of something with a constant in it I have to use my existential elimination rule to get at any of this stuff um remember for the existential elimination rule I need to start a sub proof um where I assume the substitution instance of um my original existential so this is my assumption I want to get EX BX here so now I've got my same kind of uh conjunction here so I can use the same structure I used before to get um the AG out I can get BG or CG again through conditional elimination although my line numbers have changed now it's line three and five I get not CG also through conjunction elimination on line four and that means I can get BG through disjunction elimination with our disjunction on line six and our negation of one of the disjunct on line seven right still not where I want to be because I still got that constant I got to get rid of that constant before I can end this sub proof but um I'm close because I can use the existential introduction rule to get there exists an X BX right that's existential introduction on line 8 so that's good um that's what I need right that's what I wanted so um I'm going to repeat that here on line 10 and that's the existential elimination rule my existentials on line two my sub proof is on lines 4 through 9 that gets me my conclusion that proof is complete how did you do with those proofs I hope you got the hang of it if you have any questions of course send me a note or come by my office hours and we can talk it through next time I will talk about how to combine uh proofs with translations and we will look at some more examples I look forward to seeing you then before you check out the next lecture I do encourage you to try out a couple of the practice exercises all right good luck bye