Logic in Computer Science An Introductory Course for Master Students Wang Ji jiwang@nudt.edu.cn Lecture 10 Logic in Computer Science { p.1/21 Completenss Logic in Computer Science { p.2/21 Two forms of Completeness Theorem Let be a set of w s. The following parts are equivalent. If j= A then ‘ A If is consistent, then is satis able. Logic in Computer Science { p.3/21 Sequence of consistent sets of w s Partially Ordered Set A relation on a set S is called partial ordering or partial order if it is re exive, antisymmetric and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset. Totally Ordered Set If < S;R > is a poset and every two elements of S are comparable, S is called a totally ordered set or linearly ordered set. A totally ordered set is also called a chain. Lemma Let S 2 L(F) . If < S; > is a totally ordered set, and for any 2 S, is consistent, then S S is consistent. Logic in Computer Science { p.4/21 Existence of consistent and maximal set Theorem Let L(F) be consistent. There exists 0 2 L(F) such that 1. 0 , and 2. 0 is consistent and maximal. Zorn’s Lemma Let S be a nonempty set such that for any chain Z S, the set S Z 2 S. Then there is a m 2 S which is maximal in the sense that it is not a subset of any other element of S. Logic in Computer Science { p.5/21 Expansion Let F 1 and F 2 be two rst order systems. 1. If L(F 1 ) L(F 2 ), then we say that F 2 is an expansion of F 1 . 2. If L(F 1 ) L(F 2 ), then we say that F 2 is a proper expansion of F 1 . 3. F 2 is an expansion of F 1 i every constant of F 1 is a constant F 2 . Logic in Computer Science { p.6/21 Extension Let F 1 and F 2 be two rst order systems. 1 L(F 1 ) and 2 L(F 2 ). 1. If L(F 1 ) L(F 2 ) and Th(F 1 S 1 ) Th(F 2 S 2 ), then we say that F 2 S 2 is an extension of F 1 S 1 . 2. If for every A 2 L(F 1 ), 1 ‘ F 1 A i 2 ‘ F 2 A, then we say that F 2 S 2 is a conservative extension of F 1 S 1 . Logic in Computer Science { p.7/21 Expansion and Extension 1. If F 2 is an expansion of F 1 , then Th(F 1 ) Th(F 2 ). 2. If F 2 S 2 is a conservative extension of F 1 S 1 , then Th(F 1 [ 1 ) = Th(F 2 [ 2 ) \L(F 1 ) Logic in Computer Science { p.8/21 Expansion, Extension and Consistency 1. If F 2 S 2 is a conservative extension of F 1 S 1 , then F 1 S 1 is consistent i F 2 S 2 is consistent. 2. Let F 1 and F 2 be formulations of F, so that F 2 is an expansion of F 1 obtained by adding additional individual constants to the set of constants of F 1 . Let L(F 1 ), Then (a) F 2 S is a conservative extension of F 1 S , and (b) F 1 S is consistent i F 2 S is consistent. Logic in Computer Science { p.9/21 Frugal Interpretation An interpretation < D;I 0 > for F is said to be frugal i #D #L(F). An interpretation I is said to be a frugal model of if it is a frugal interpretation of . Logic in Computer Science { p.10/21 Ideas of Proof of Completeness Theorem We begin with a consistent set . In steps 1-3 we extend to for which is consistent and is maximal in the sense that for any w A either A 2 or A 2 . For any w A and individual variable x, there is an individual constant d such that 8xA S x d A 2 Then in step 4, we form an interpretation I and 2 I which satis es . Logic in Computer Science { p.11/21 Step 1 Expand the language by adding countable in nite set of new individual constants. 1. F F + 2. F [ F + [ Logic in Computer Science { p.12/21 Step 2 For each A 2 L(F + ) and each individual variable x, add to the w 8xA S x d A 2 where d is one of the new individual constant. The resulted set [ 0 of w s is still consistent. Logic in Computer Science { p.13/21 Step 3 Extend [ 0 to a consistent and maximal set . Logic in Computer Science { p.14/21 Step 4 De ne I =< D;I 0 >, where 1. D = Term F + 2. I 0 (a) If d is an individual constant, then I(d) = d. (b) If f n is an n-ary function constant, then I(f n ) = f n . (c) If p is a propositional constant, then I(p) = T i p 2 . (d) If P n is an n-ary predicate constant, then I(P n ) = P n , where < t 1 ; ;t n >2 P n i P n (t 1 ; ;t n ) 2 . Logic in Computer Science { p.15/21 Step 4 (continued) 2 I is de ned as 1. If x is an individual variable, then (x) = d. 2. If f n is an n-ary function variable, then (f n ) = f n . 3. If p is a propositional variable, then (p) = T i p 2 . 4. If P n is an n-ary predicate variable, then (P n ) = P n , where < t 1 ; ;t n >2 P n i P n (t 1 ; ;t n ) 2 . Logic in Computer Science { p.16/21 I? I(t)( ) = t I(A)( ) = T i A 2 Logic in Computer Science { p.17/21 G odel Completeness Theorem 1. If j= A, then ‘ A. 2. Any consistent set of w s is satis able. Logic in Computer Science { p.18/21 Consistent vs Satis able Let L(F). The following parts are equivalent. is consistent. There exists a frugal interpretation I such that is satis able in I. is satis able. Logic in Computer Science { p.19/21 Let L 0 (F). The following parts are equivalent. is consistent. has a frugal model. has a model. Logic in Computer Science { p.20/21 Compactness Let L(F). is satis able i every nite subset of is satis able. is consistent i every nite subset of is consistent. Let L 0 (F). has a model i every nite subset of has a model. Logic in Computer Science { p.21/21