《FoundationsofLogic (5).pdf》由会员分享，可在线阅读，更多相关《FoundationsofLogic (5).pdf（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaOnline Course:Foundations of LogicTsinghua University,spring 2020Dag Westerst ahlTsinghua LogicThe completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaThis is Chapter 4We have two
2、notions of consequence:|=iffevery interpretation making all sentences in true also makes true.H iffthere is a derivation in H of from.These are conceptually very different!One talks about the existence of a finite syntactic object(aderivation),the other quantifies over all interpretations.In Proposi
3、tional Logic(PL)the difference is not so great:interpretations are valuations,and for every sentence onlyfinitely many different valuations are relevant.(Why?)But in FOL the difference is huge.(Why?)1 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaSoundn
4、ess and completenessAn inference system S is sound ifI S implies|=and it is complete ifI|=implies SSoundness is(usually)easy:Show that the axioms(if any)arelogically true,and that the rules preserve truth.This is easy to check for H(or ND);you can find the proof(by induction)in Chapter 4.1.The hard
5、part is completeness.2 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaCompleteness for PLToday we consider the completeness of the system H for PL.We must show that if is true in every valuation in which(all sentences in)is truethenthere is a derivation
6、of in H from.That doesnt seem obvious.Actually there are fairly simple ways of showing completeness for PL(this was first done in 191820 by Paul Bernays and(independently)Emil Post);see Exercise 4.7.11.We will use another technique,because it generalizes almost directlyto FOL.3 of 20The completeness
7、 problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaA reformulation of the problemRecall that a set of sentences is satisfiable if there is aninterpretation making(all sentences in)true,and that(1)|=iff is unsatisfiable.We say that is consistent if 6 (where is some PL-sentencesuc
8、h that H,such as(p0 p0).We have:(2)H iff is inconsistent.4 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaThe Consistency LemmaThis means that to show completeness,it is enough to showLemma(Consistency Lemma)If is consistent,then is satisfiable.For then:
9、So we focus on proving the Consistency Lemma.5 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaThe Consistency LemmaSo suppose is consistent.How can we find a valuation V makingall sentences in true?Idea 1:Let tell us the truth value of every sentence let
10、ter p:IIf p ,let V(p)=1;otherwise V(p)=0.So if p ,then p 6 (since is consistent),so V(p)=0,which is good!But there is a problem:may not contain enoughinformation.Example:suppose p but p 6.Example:suppose p q and p ,but q 6.Solution:Add the missing sentences to!But how do we know which sentences are
11、missing,and how can weadd them systematically?6 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaMaximal consistent setsIdea 2:Extend to a maximal consistent set.Definition(maximal consistency)is maximal consistent if it is consistent,and no further senten
12、cecan be added to it without breaking consistency.I.e.if 6,then is inconsistent.Are there such sets?Yes:for every valuation V,the set:V|=is maximal consistent.(Why?)But that doesnt help us now.(Why?)7 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaMaxima
13、l consistent setsFirst we check that maximal consistent sets solve our problem.This is because they have the following nice properties:Fact(properties of a maximal consistent set)(a)iff 6.(b)If H,then .(c)iff 6 or .Roughly:no sentence is missing,so we can use a maximalconsistent set to create our va
14、luation.8 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaProperties of maximal consistent sets(a)iff 6.(b)If H,then .(c)iff 6 or .Proof:9 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaThe interpretation and
15、the Truth LemmaNow suppose is maximal consistent.Define the valuation VbyV(p)=?1if p 0if p 6(i.e.if p )Lemma(Truth Lemma)V|=iff 10 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaProof of the Truth LemmaAssume is maximal consistent.Lemma(Truth Lemma)V|=if
16、f Proof.We use induction over PL-formulas.11 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaLindenbaums LemmaThe Truth Lemma shows that if we start with a maximalconsistent set,Vis a valuation making every sentence in true,so is satisfiable,as we wanted
17、to show.But our assumption was only that is consistent.The final step is provided by the next fact.Lemma(Lindenbaums Lemma)Every consistent set of sentences can be extended to a maximalconsistent set(by adding more sentences).If we can show this,we are done.(Why?)12 of 20The completeness problemRefo
18、rmulationMaximal consistent setsTruth LemmaLindenbaums LemmaProof ideaThe idea for proving Lindenbaums Lemma is simple:Suppose is consistent.We go through every sentence in ourlanguage(relative to given vocabulary),one by one in someorder,and add it if it is consistent to do so,otherwise not.Can we
19、enumerate all PL-sentences?A sentence is just a finite string of symbols.There are at most countably many symbols,(,),p0,p1,p2,.and therefore countably many finite strings of symbols.13 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaEnumerating all sente
20、nces 1This is a general fact.Suppose our symbols are enumerated ass0,s1,s2,.We enumerate all pairs of symbols as follows:14 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaEnumerating all sentences 2Similarly we can enumerate all triples,quadruples,.of sy
21、mbols,write them in a table,and then by the same method enumerate allfinite strings of symbols:Most of these strings of symbols are meaningless,but if wesuccessively delete these,we are left with an enumeration of allPL-sentences.(See also Appendix Ch.16.4.)15 of 20The completeness problemReformulat
22、ionMaximal consistent setsTruth LemmaLindenbaums LemmaBack to the proof of Lindenbaums LemmaSo let0,1,2,.be an enumeration of all PL-sentences.We start with our consistentset,and define a sequence of sets 0,1,2,.as follows:16 of 20The completeness problemReformulationMaximal consistent setsTruth Lem
23、maLindenbaums LemmaProof of Lindenbaums Lemma,cont.17 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaNext Thursday:Chapter 518 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums Lemma19 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums Lemma20 of 20