FoundationsofLogic (5).pdf

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 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 Propositional 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 LemmaSoundness 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 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 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 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-sentencesuch 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: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 letter 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 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 sentencecan 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 LemmaMaximal 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 valuation.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 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|=iff 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 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 problemReformulationMaximal 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 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 sentences 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 symbols,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 problemReformulationMaximal 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 LemmaLindenbaums 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