Formal Semantics in QL using Models

hi and welcome back to deductive logic I'm professor Matthew J Brown and today we're doing our second lesson on formal semantics in ql um using models so before we continue I want to go back to the semantics of SL to compare the two um systems that we discussed last time so in SL you'll remember we use truth tables um also known as truth value assignments to determine the truth value of complex Expressions right in ql we use models right so they play the same role we can't use truth tables because of the relation between predicates and objects and terms um there's there's too many things going on for truth tables in SL a truth value of a statement is relative to a truth value assignment you could have chosen a different truth value assignment and you'd get a different truth value for most sentences for contingent sentences in ql the truth of a statement is relative to a model right so again for contingent statements truth values are relative to a model the semantic entailment of a means true and every truth value assignment right so tooies in SL are true in every truth value assignment whereas in ql a tautology is true in every model right so the semantic entailment of a means it's true in every model right this is when you've got a statement um uh on the right hand side of the double Turn Style and nothing on the left hand side indicating a topology so that's just a bit of a of a reminder of how these two things line up in SL versus ql right let's construct a model to evaluate this sentence if PA then for all X PX right um here's a universe of discourse contains three cities Atlanta Dallas and San Diego um we'll take we'll say the extension of our predicate P includes all three of those Atlanta stallas and San Diego and that the reference of a is Atlanta right um on that model it looks like our statement is true right um PA we know is true because Atlanta is an the extension of p and a refers to Atlanta and for all X PX is also true because every item in our universe of discourse is in the extension of P so uh that's a case in which the antecedent is true and the consequent is true so the conditional is true let's consider replacing this model with the extension of P includes all of the universe of discourse with a smaller extension for p Just containing Atlanta right now on this new model um PA is still true Atlanta is still in the extension of P but for all xpx is false because Dallas and San Diego are not in the extension of P right um the anticon is true but the consequent is false making the sentence false according to our uh basic semantics for the conditional let's try one more uh model um by changing the extension of P now to include Dallas and San Diego but not Atlanta right so now we know that PA is false why because a Atlanta is not in the extension of P right so the antecedent of the conditional is false whenever the antecedent of the conditional is false we know the conditional itself is true right so this tells us that our conditional is true in this model right this is obviously a case of a contingent sentence because its truth value changes from model to model let's think about another statement PA if and only if PA by conditional between PA and Pa right let's look at our universe of discourse from the last Model right let's consider the extension of p as just including Atlanta and Dallas right and let's keep the referent of a referring to Atlanta we can ask is the sentence true or false well pa okay is true because Atlanta is in the extension of P um and so it's true on both sides of the bond conditional so the sentence is true if we replace the extension uh of p with San Diego so Atlanta is not in the extension of P then it's false on both sides of the by condition so the bond conditional is still true right if we change the reference of a to Dallas it doesn't change anything if we change the reference to San Diego it's now true and true on both sides so the bond conditional remains true you may notice right that um PA if and only if PA looks an awful lot like a toogy because it is in every model the referent of a is either in the extension of P or it isn't if it is then the byond conditional is true if it isn't then it is still true right so in order to demonstrate semantically that this is a topology we sort of have to talk about what's going on in every possible model right um and there are many cases we'll look at some more in a bit where we have to do that let's think about another statement which looks um something like a topology right um at least it seems like it might be a topology for all x i either PX or not PX right um we can again look at some models here let's consider a model where uh everything is in the extension of the of the predicate P right then PX is true for every X right if PX is true then PX or not PX is true so we know our our Universal quantifier here is is true right um we can consider another model right where the expension of p is smaller only containing Atlanta and as we move through every item of our universe of discourse which we have to do with the universal quantifier we say okay is PX or not PX true for Atlanta yes um because PX is true is it true for Dallas yes because not PX is true making the disjunction true um I think I might have called it a biconditional a moment ago but it's a disjunction um and then uh if we go to San Diego again not PX is true because San Diego is not in the extension of p and since that side of the disjunction is true the disjunction is true right and again we can look at another example it's going to be the same right so you might ask given that we're talking about not a single term a um in a in a tautology but we're talking about something that has a universal quantifier which quantifies over par potentially very many um uh items in a with a large Universe of discourse as many models will have how do we argue that this is true in every model we'll come back to this question in a moment um but the the basic idea is you're going to have to provide a kind of schematic argument that takes into account every possible model right um so let's uh let's again line up some examples of State ments right we know that PA is true in a model M if the referent of a is in the extension of P similarly for a two- Place predicate or relation we know that it's true in a model if the if the ordered pair of the referen of a and the referen of B is in the extension of the predicate M this gets more complicated as we get more complicated statements but here again we know that um this conditional is true in a model M if and only if um PA is false right which we know how to do from above or MBC is true um which we know how to do above right so um this is this also gives us um how we do this but what we want to know is how do we articulate whether a universal Quantified statement is true in a model right we we say it's true in the model if if and only if every object in the universe of discourse of the model is in the extension of P so the way in which I stepped through item by item a moment ago that's how you have to do with a universal quantifier with an existential quantifier you just have to look for one item one object in the universe of discourse um which uh satisfies the statement right so let's consider how we would show that this is a topology right um given what we have to do with a um Universal quantifier right we're going to construct an argument the argument is just in English and it's an argument concerning any possible model right so consider any model M and any arbitrary member of the universe of discourse Omega we're just using Omega to stand for an object as we often do it must be the case that either Omega is in the extension of P or it is not there's no vagueness about that question for any particular model predicate is going to have an extension and something is going to be in it or it's not going to be in it if Omega is in the extension of P then the left half of the disjunction is Satisfied by a variable assignment that assigns Omega to X if it is not then the right half of the disjunction is satisfied either way the disjunction is satisfied right so PX or not PX is going going to be satisfied whether or not omega is in the extension of p and those are the only two options right and this is the case for any member of the universe of discourse right and remember what we said to do a universal quantifier we have to determine what is the case for every member of the universe of discourse so for all X PX or not PX is Satisfied by any variable assignment right so um because a x PX or not PX is a sentence for all X PX or not PX is true in model M and this argument holds no matter the universe of discourse or the extension for p right we didn't say anything specific about the the universe of discourse size or what was in it nor about the extension of P so this is true of any model and therefore for all X PX or not PX is a topology that's how we determine that it's a topology right by by constructing this argument remember this chart that we ended our last lecture with right this is going to help us know what kind of reasoning using models to do right it lets us know whether we need to construct a specific model or two models perhaps um or whether we need to um engage in reasoning about any possible model right so let's look at some examples let's look at the question of whether a sentence is contingent right um in order to know that in order to show that a sentence is contingent we have to construct two models one in which it's true and another in which it's false so here are some examples of sentences that are contingent and what I'd like you to do is try to come up with a Model A pair of models for each that shows that the sentence is contingent so pause the lecture and try to work that out okay let's see how you did so um with sentence one BC Let's uh have a universe of discourse with two items in it Bob and Charles we'll say the extension of B is Bob and the reference of C is Charles and on that case we know that b c is false because C is not in the extension of B right um let's do a second model the only difference is that the extension of B includes Charles reference C stays the same right here we know that because C is in the extension of B Charles is in the extension of B that BC is true right um and so we have a model where it's false and a model where it's true that shows that it's contingent here's a slightly more complicated sentence AC if and only if not in C and again we just construct two models where it comes out true in one and false in the other so on the first model we'll keep our same universe of discourse we'll say the extension of a is Bob and the extension of n is Charles right we'll say the reference C is Charles right um so here AC is false because Charles is not in the extension of a NC is true because Charles is in the extension of n so not NC is false we've got false on both sides of the bond conditional so the byond conditional is true let's look at a second model here we've got Bob in the extension of a and in the extension of n um and the referent of C is Charles so on this AC is false and NC is also false because Charles is not in the extension of either but not in C is true so we've got false on the left true on the right that makes the by conditional false right for all X ax right this involves the universal quantifier it's a little more complicated our universe of discourse will keep the same let's have the extension of a b Bob and Charles right that's everything in our universe of discourse so for all X ax is true it's true for Bob it's true for Charles that's all the items we've got so it's true on the other hand if our extension of a is smaller than our Universal discourse we know for all X ax is false right right we get to we go to Bob it's true but we go to Charles and ax is false so the universal quantifier statement is false so again contingent right so that's how we show that a sentence is contingent to show that it's not contingent we would just show either that it is a tautology or a contradiction and that requires that reasoning with all possible models let's look at the question of whether an argument is in is uh valid let's look at the question of whether an argument is valid and here I want to say um I'm going to give you some examples and tell you from the get-go these are invalid arguments right to show that an argument is invalid we have to construct a model in which the premises are true and the conclusion is false right um so here are two examples of invalid arguments I want you to pause the video and take a moment to work out um a model that shows that these are invalid let's see how you did first with number one um I'm going to pick a universe of discourse with just three numbers 1 two and three right we'll say the extension of P includes one and two the extension of Q includes one right and the referent of a is two right okay so let's look at our let's look at our um statements here there exists an X PX and QX right so we're looking for some object X that is both in the extension of p and in the extension of Q we've got one it's number one right so um the first line the first premise is true right what about PA well the reference of a is two and two is in the extension of P so PA is also true but QA is false because because two is not in the extension of Q so two premises both premises are true the conclusion is false so the argument is invalid let's look at our second example we've got a um Universal uh quantifier pise for all X if ax and BX then CX we have not CE right and so and then therefore not AE so let's again let's pick a model um that's going to show that the premises are true but the conclusion is false Let's uh we only need one item in our universe of discourse here and sometimes when I'm constructing these um models what I'll do is I'll just start with one item in the universe of discourse and if I need a another one to make the model work I'll add another one and so I only have the number of items that I really need um so we'll start with one because we can do it with one here we'll say the extension of a is one right the extension of B is the empty set we use this little zero with a a cross through it could be an O I guess with a cross through it but stands for the empty set we could also use the brackets with nothing in between to represent the empty set um this just means there's nothing in the extension of B there's nothing in the extension of C okay and the referent of e is one so on this model our first premise is true why because ax is true of of the one item BX is false though so ax and BX is false when the antecedent of the conditional is false the conditional itself is true so that makes um that means for one the conditional is satisfied and there's only one in the Universal discourse so the universal quantifier is true first premise is true not C is true because e is not in the extension of C because nothing is but not AE is false because one is in the extension of a um and so we've got two true premises and a false conclusion so the argument is invalid next I want to look at are A and B equivalent right to show that they are equivalent we would show that A and B must have the same truth value value in any model um it's um on the other hand to show that they're not equivalent we have to construct a model in which they have different values so let's go through some examples of how we show that a set of sentences or a pair of sentences are not equivalent right um so how do we show that they're not logically equivalent again we construct a model where they have different truth values right so pause the video and try to work out a model that will show that they're not equivalent for of these all right let's check your work so the first one we've got a A or ba and ab or BB now these look like they might be equivalent because they have exactly the same form right so they they have a very uh they're very similar right but because A and B lowercase a and lowercase B can refer to different objects they can have different truth values right um I've got a universe of discourse here with two items in it right ABA and Blondie um uh we need two objects in this case because we've got two constants right um we'll say the extension of a is ABBA and the extension of B is the empty set um and the reference of a is ABBA the referent of B is Blondie right um this makes a A or ba a true right that is ABBA is in the extension of large a right and since the left hand side of the disjunction is true the disjunction is true right although ba is false it doesn't matter but Blondie is not in the extension of a or the extension of B so the second disjunction is false so true on the left false on the right means that they're not equivalent let's look at our second example this involves two quantifiers so it's a little more complicated um we've got not it's not the case that for all X ax then BX and there exists an X that is not ax and BX right we're going to show that these are not logically equivalent um we can do this with a universe of discourse with just one member call it tailor um the extension of a is the empty set right um the extension of B is Taylor right um now let's look at our uh two sentences right or two statements um for Taylor if ax then BX right is satisfied right because um Taylor is not in the extension of a which means ax comes out as false or zero um that means the condition conditional comes out as true or one right it is the conditional is satisfied right um Taylor's the only thing in our universe of discourse so that means that the universal quantifier statement for all X ax and BX comes out true and because we've got the negation sign out front it means that the entire statement on the left comes out false right now there exists an X that is not ax and is BX that comes out true right while because Taylor is in the extension of B so BX is true Taylor is not in the extension of a so ax is false or not satisfied um and not ax is Satisfied by Taylor that means that the entire conjunction not ax and BX is Satisfied by Taylor which means that the existential comes out true because there's one item in the universe of discourse at least one item in the universe of discourse that satisfies it let's look at one more for example we want to know is the set a consistent right um remember consistent just means that it's possible for all of the sentences in a to be true um that makes it fairly easy to show using models we just have to come up with one model where all the sentences are true here are two more examples I want you to show a model for each that shows that the following sets of sentences are logically consistent pause the video and give it a go all right let's see how you did so for the first one here um uh we've got there exist an X that's ax and BX and for a lowercase a a a and not ba right so again I'm going to give you a universe of discourse with two members right we'll say the extension of a includes both members Abba and Blondie right the extension of B only includes Blondie and the referen of a is ABBA right um now the um there does exist an X that is ax and BX right Blondie is both in the extension of A and B so the first one comes out true um AA and not ba also comes out true because um ABBA is in the extension of a but not in the extension of B right so both sides of the conjunction are true so the conjunction is true right now this wouldn't be true in every model it's possible that you could have both come out false or one come out true and one come out false um in this case they are not logically equivalent and neither is a tautology um and they are logically consistent with each other right our second statement has um three different sentences um the first says that for all X if ax then BX the first says not AA and the second says ba so let's come up with an example that of a model that makes these all logically consistent we'll start with the universe of discourse with just one item in it um again that's a good strategy is to just add items to your Universe of discourse as you figure out you need them um we can say the extension of a is the empty set this is nice because that will make the first statement true if there's if ax is always false for every item in our universe of discourse then the universal quantifier uh trivially comes out true because of the nature of the material conditional right um we'll say the extension of B contains atom right um and the referent of a is atom right um we know that not a a comes out true because nothing uh has is in the extension of a that will include little a and we know that um Big B little a also is going to come out true because atom is in the extension of B right so that's another model showing the second set of sentences is consistent I want to back up for a second and ask why is it we keep talking about satisfaction in addition to truth in ql right remember we introduced this notion of satisfaction in the last lecture and you've actually seen me stumble a little bit over Truth Versus satisfaction as I've tried to talk my way through some of these models right and again the reason is because some well formed formula in ql have free variables and that means that that can't have a truth value right um a free variable in a um in a woof means it's not a sentence it doesn't have a determinant truth value but since our semantics for ql is recursive right it follows that recursive definition of well formed formula in building up the um semantics of a complex statement from more more uh from its more simple constituent parts we need to be able to get the truth value for a sentence based on the parts some of those parts being well formed formul with free variables so so we use the term satisfaction to keep track of um that part of the uh of the sentence which is contributing to the truth value but which itself can't have a truth value right that's different from SL because in SL sentences the sentence has a truth value and every part of a complex sentence also has a truth value that can't be the true for ql so we talk about satisfaction it makes things a little more complicated but you can think of it as a bookkeeping device a way of keeping track of how um the truth of a sentence depends on the parts so we should ask for all formal languages not just SL and ql what do we need to know to determine the truth or falsity of a sentence what do we need to know to determine truth values of sentences generally right um and again as we dis discussed last time we need two things the interpretation of the sentence right we need to know what it means what it refers to um and we need to know the state of the world right that it refers to right um this is given in SL by a truth value assignment it's given in ql by a model in other Logics it might be given by other kinds of semantic es right um but um all of these are different ways of combining the interpretation of the sentence um with the state of the world that it refers to right um there are of course some sentences in most formal languages that are true independent of the state of the world right topologies or false independent of the state of the world contradictions right um but in general in the general case we need to know that here's a question right what's the difference between semantic entailment right which we used the um double Turn Style to indicate and provability or derivability which we use the single Turn Style to indicate right remember that semantic entailment is a relation between truth values right um to to say that a semantically entails b means that whenever a is true B must must be true it's a relation between the truth values of the the sentences or sets of sentences on either side of the entailment relation provability means that um the statement can be derived based on the rules of proof to say B is provable from a means that you can construct a proof with a as a premise and B is a conclusion right so those are different Notions we'll talk in our next unit about how they're related but it's important to know that the semantic relation of entailment and the syntactic relation of provability provability are different and in and in many formal systems they might come apart although in others they might uh line up with each other you should also know what the difference is between a set and an ordered pair right remember that a set is an unordered collection of things right our universe of discourse is a set it's got uh it's got a bunch of different things the particular order that they're in the universe of discourse doesn't make any difference right um an order and we represent a set with the curly brackets right an ordered pair right or an ordered triple or an ordered in tupal right is a collection of things whose order matters right when we've got a relation like lxy right um uh the things that satisfy or or are in the extension of that two- Place predicate are ordered pairs right and what's first and what's second is crucial ordered tupal we use those triangle bra uh braces right or brackets to uh represent in this class when we use sets they can have individual objects in their as their members as we do when weever we represent a universe of discourse for a model they can have ordered pairs as their members as when we represent the extension of a two- Place predicate a relation they can have ordered triples as their members as when we represent the extension of a three Place relation and so on so here are some examples of pieces that might go in a model and all of these have something wrong with them pause the video and see if you can figure out where each of these goes wrong all right so let's see the first one um is a problem because the extension of any predicate has got to be a set right um Bob is an object not a set we could fix it by putting the curly brackets around it right and it's the same problem with the second line the extension of M can't just be an ordered pair it has to be if m is a two-place predicate it has to be a set of ordered pairs so again we could fix this by putting our curly brackets around it the reference of P equals Bob that could be right in the sense that reference of uh of a of a constant take a single object as um what's on the right hand side but that looks like a big p that's an uppercase p and it's only constants which we represent with lowercase letters that have a reference right um the case with the reference of B here is that it's got a set on the right hand side and it needs to have an object so we actually need to get rid of those braces and those would all be acceptable uh things to appear in a model right now the way they've been Rewritten so among the other things that you should know um out of this unit you should know how to define in terms of the semantic entailment relation in general as well as the specific terms of SL and ql toogy contradiction and contingent right so you should know three different definitions of each of those right consistent and inconsistent valid and invalid logically equivalent right um so you should know how to define each of these just in terms of semantic entailment for example um tautology is semantically entailed with nothing on the Left Right by anything or nothing right um a valid argument is one in which the um prises semantically entail the conclusion right you should be able to Define them in terms of SL for example a contingent statement is one where uh a truth value assignment could make it true or false right um You can show it with two different truth value assignments and in terms of ql in terms of models for example uh we know that an argument is invalid if there is a model where the es come out true but the conclusion comes out false right and in line with this you should be able to show um using truth tables or models um or arguments about models um whether something is a topology or not whether something is valid or invalid Etc right so you should know the definitions and know how to use models and um truth value assignments to determine all of these things right once you're able to do that you should have no problem with the exam for uh for unit six here on formal semantics um that's our last lecture on formal semantics I'll see you for our next and last unit on proofs and ql after you've done a satisfactory job on the exam for formal semantics good luck with it bye