FoundationsofLogic (6).pdf

《FoundationsofLogic (6).pdf》由会员分享，可在线阅读，更多相关《FoundationsofLogic (6).pdf（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityOnline Course:Foundations of LogicTsinghua University,spring 2020Dag Westerst ahlTsinghua LogicModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identity1 of 30ModelsModel Existence TheoremTruth LemmaLindenbaum

2、s LemmaFOL with identity2 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identity3 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityThis is Chapter 5Now our task is to do the same for FOL(first-order logic),i.e.to prove:Theorem(completeness theor

3、em,G odel 1930)If is a set of FOL-sentences and is a FOL-sentence,then|=implies .And exactly as before,it is enough to prove the ConsistencyLemma,that every consistent set of sentences is satisfiable.4 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityTerminology change!

4、What we used to call interpretations,will now be called models.Thus,a modelM=(M,I)for a vocabulary L consists of a domain M(any non-empty set)anda function I assigning suitable values to the symbols in L.So a model is a kind of mathematical structure,and well see nextweek that these structures,and t

5、heir relation to our FOL language,can be studied in their own right.We often say“M is a model of”for“is true in M”,or“M|=”.Similarly for“M is a model of”,meaning that allsentences in are true in M.5 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityModel Existence Theore

6、mAccordingly,the Consistency Lemma will now be called theModel Existence Theorem,and can be formulated simply asfollows.Theorem(Model Existence Theorem)Every consistent set of sentences has a model.Here,“has a model”means of course that there is a model(interpretation)making all sentences in true.So

7、 we now focus on proving the Model Existence Theorem.6 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityModel Existence TheoremLuckily,the proof has exactly the same structure as for PL.That is,given a consistent set,we let the atomic sentences in determine the interpre

8、tations of the non-logical symbols.For example,if Pc1c2,then the interpretations of c1and c2should stand in the relation PMto each other.But first we need a domain!Here there are many possible choices,but a simple idea is to use thesyntactic material for the domain too:we let M consist of theindivid

9、ual constants that occur in sentences in.So M is a set of individual constants,and every constant c isinterpreted as itself:cM=c.7 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityModel Existence TheoremFor this idea to work,even when is maximal consistent,variousthings

10、 need to hold:(i)There has to be(enough)individual constants in ourvocabulary L.(ii)Suppose that xPx ,and also that Pc for every c inL.can still be consistent!But no atomic sentence in is awitness to the existential claim.(iii)We may have c=d ,where c and d are distinct symbols,but they should be in

11、terpreted as the same object.We solve(i)by adding(infinitely many)new individual constants toL,and(ii)by systematically adding witness sentences to.And we first avoid problem(iii),by looking at FOL:first-orderlogic without identity.8 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL

12、with identity-complete setsWe say that a set of sentences is-complete if,for everysentence of the form x(x)in,there is an individual constant cin L such that(c).It turns out that maximal consistency and-completeness is exactlywhat we need for the Truth Lemma.Given,we construct the model Mas follows:

13、IM=c:c is an individual constant in LIcM=c for c L.IIf P is an n-ary predicate symbol in L,then PM(c1,.,cn)iffP.Lemma(Truth Lemma)If is maximal consistent and-complete,then M|=iff .9 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityInduction over FOL-formulasLemma(Truth

14、 Lemma)If is maximal consistent and-complete,then M|=iff .We want to prove the Truth Lemma by induction over(thecomplexity of).But one cannot do induction over sentences:because thesubformulas of a sentence can have free variables!Therefore,we prove a more general claim about formulas,which hasthe T

15、ruth Lemma as a special case.Recall our notationM|=(x1,.,xn)a1,.,an,or simplyM|=(x)afor(a1,.,an)satisfies(x1,.,xn)in M.10 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityGeneralized Truth LemmaLemma(Generalized Truth Lemma)Suppose is maximal consistent and-complete.The

16、n,for all n,allL-formulas(x1,.,xn),and all c1,.,cn M:M|=(x1,.,xn)c1,.,cn iff(c1,.,cn)This is something that can be proved by induction over.There are five cases:is atomic;is a negation;is animplication;is an existentially quantified formula;and is auniversally quantified formula.The case n=0 is the

17、Truth Lemma we want.11 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of generalized Truth LemmaA():M|=(x1,.,xn)c1,.,cn iff(c1,.,cn)Case 1:is an atomic formula Pt1.tk,where the tiare eitherindividual constants or variables(no function symbols since no=).12 of 30

18、ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of generalized Truth LemmaA():M|=(x1,.,xn)c1,.,cn iff(c1,.,cn)Case 2:is.Case 3:is .13 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of generalized Truth LemmaA():M|=(x)c iff(c)Case

19、4:is y(y,x).14 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of generalized Truth LemmaA():M|=(x)c iff(c)Case 5:is y(y,x).15 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityStrengthened version of Lindenbaums LemmaAll that remains

20、 is to prove the following strengthened variant ofLindenbaums Lemma:Lemma(Lindenbaums Lemma for FOL)Let be a consistent set of L-sentences,and let L0=L c0,c1,c2,.where the ciare new individual constants.Then there is a maximalconsistent and-complete set 0of L0-sentences such that 0.The Model Existen

21、ce Theorem(and thus the CompletenessTheorem)follows as before:we obtain a model M0of 0by theTruth Lemma,and since 0,all sentences in are true inM0,i.e.M0is a model of.16 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of Lindenbaums LemmaLet and L0=L c0,c1,c2,.be

22、 as stated.And let0,1,2,.be an enumeration of all L0-sentences.(We are assuming that L is countable,so L0is countable(countablyinfinite),and so there are countably many symbols as before,andwe can enumerate all finite strings of these symbols,and hence inparticular the L0-sentences.)Again we extend

23、by going through the list 0,1,2,.one by one,but now we also have to add witnesses toexistential sentences.The witnessing constants will all be taken from c0,c1,c2,.17 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of Lindenbaums Lemma:the sets n18 of 30ModelsMod

24、el Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProperties of n(a)=0 1.n n+1.(b)Each nis consistent.19 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProperties of n(c)is consistent.(d)is maximal consistent.(e)is-complete.20 of 30ModelsModel Existence

25、 TheoremTruth LemmaLindenbaums LemmaFOL with identityBringing in identityWe noticed that if a sentence c=d is in,where c and d aredistinct constants,then we cannot let cM=c and dM=d(forthen c=d will be false in M).The solution to this is a common mathematical construction:We define a relation betwee

26、n individual constants:c d iffc=d We show that is an equivalence relation:reflexive,symmetric,transitive(if is maximal consistent).We identify equivalent constants:the elements of the domain arethe equivalence classes:|c|=d:c d And we let cM=|c|.21 of 30ModelsModel Existence TheoremTruth LemmaLinden

27、baums LemmaFOL with identityAnother lemmaSo we have to check that this idea works.To simplify a little,I assume here that L has no function symbols.(For the general case,see Chapter 5.4.)First,defining c d c=d ,we must show:LemmaIf is maximal consistent,then(a)is an equivalence relation.(b)If ci dif

28、or i=1,.,n,then P iffPd1.dn.In mathematical terms,this says that is a congruence relation.If C isthe set of individual constants,the set C/of corresponding equivalenceclasses is the quotient of C over.22 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of the lemm

29、aLemmaIf is maximal consistent,then(a)is an equivalence relation.(b)If ci difor i=1,.,n,then P iffPd1.dn.23 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityProof of the lemma,cont.24 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityModel c

30、onstruction and Truth LemmaAssuming is maximal consistent and-complete,we define themodel Mas follows:IM=|c|:c is an individual constant in LIcM=|c|for c L.IIf P is an n-ary predicate symbol in L,then PM(|c1|,.,|cn|)iffP.NB PMis well-defined because of the preceding lemma!Lemma(generalized)Truth Lem

31、ma)Suppose is maximal consistent and-complete.Then,for all n,allL-formulas(x1,.,xn),and all|c1|,.,|cn|M:M|=(x1,.,xn)|c1|,.,|cn|iff(c1,.,cn)25 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identityFinishing the proofThe proof of the(generalized)Truth Lemma(by induction on)is

32、essentially as before.The clause when is t1=t2is taken care of by the definitionof.Lindenbaums Lemma needs no change,and the rest is exactlyas before!So we have proof of the Model Existence Theorem for FOLwith identity,and thereby the Completeness Theorem.26 of 30ModelsModel Existence TheoremTruth L

33、emmaLindenbaums LemmaFOL with identityNext Monday:Chapter 6,up to somewhere in Ch.6.527 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identity28 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identity29 of 30ModelsModel Existence TheoremTruth LemmaLindenbaums LemmaFOL with identity30 of 30