Class Note for CMPSCI 601 at UMass(21)
Class Note for CMPSCI 601 at UMass(21)
Popular in Course
Popular in Department
This 22 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(21)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 601 Tarski s Truth De nition Lecture 15 0AMh2 gtuwu UAW Rjtlv vtrRj lt93 ltHltt1awutrRjgt 6 R34 MW F To lt MW 90 UAMU V lt UN 0 MUNMO Au 0751090 lt for all a E lw auaa t M gt yx where May a ifrg x Fitch Proofs for FOL The Fitch proof system of BE can prove FOL formulas as well as propositional ones We have to add SlX new proof rules to deal with the new concepts of identity and quanti ers 0 Intro Derive n n cf Atlas Shrugged 0 Elim From Pn and n m derive Pm VIntro Ordinary form If for a new variable 0 you derive P0 derive Vx P0 VIntro General conditional form If from P0 for a new variable 0 you derive Q0 conclude Vx PCT gt QW VElim From Vx 3 x derive 30 0 EJIntro From 3 0 derive 3x 3 0 EJelim If from 3 0 for a new variable 0 you derive Q then you may derive Q from 3x 3 Coming Attractions We will prove Fitch to be sound for FOL following BE Section 183 with some details on HW4 The basic idea is very similar to soundness for propositional Fitch We show by induction on steps of any proof that each state ment is true in any structure in which all of its premises are true instead of for any truth assignment Then we will prove the completeness of Fitch for FOL following BE Chapter 19 with some details on HW5 The goal is to prove that any FOLvalid sentence can be proved in Fitch We will do this as follows 0 De ne an in nite set of sentences called the Henkin theory 0 Show that any propositional extension of the Henkin theory has a model 0 Use propositional completeness to get a propositional Fitch proof of any FOLvalid sentence from the Henkin theory and nally 0 Show that in Fitch we can eliminate every use of the Henkin theory in this proof to get a Fitch proof of the FOLvalid sentence Soundness 0f Fitch for FOL Once again we prove by induction on all steps in any proof that every statement is a FOL consequence of the premises in force when it occurs This means that if M is any structure such that M l B for every premise in force when Q occurs then M Q Since the last step of the proof can use any of our eighteen proof rules we need eighteen cases in our inductive step We ll do two of these cases with a few others to follow on HW4 The gtElim Case The EJElim Case The cases of the other new Fitch rules are either similar to this case or are even easier Making an Existentially Complete Structure We now begin the proof of completeness for Fitch Given a set of sentences T from which we cannot prove l we want to show that T has a model a structure in which all of its sentences are true This is an equivalent form of completeness if T U m9 has no model it must be that we can derive i from T U m9 and thus prove S from T using lelim Our rst step is to convert T into an existentially com plete set of sentences over an expanded vocabulary We do this by adding an in nite set of witnessing constants to the vocabulary For every formula Px in the vocab ulary with exactly one free variable we add a new con stant named 01333 Eventually we will insist that if there is any element such that P is true then P 0166 will be true Note that there is nothing wrong with a vocabulary being in nite In almost any imaginable computer science ap plication we will want the vocabulary we use to be nite but everything we have proved about FOL systems and Fitch has applied equally well to in nite vocabularies An Interesting Technicality We want to have a constant 0 1333 for every formula Px over the vocabulary But of course we mean every for mula over the new improved vocabulary with the Wit nessing constants already in it This leads us to an appar ent circularity in the de nition But we can get around this problem Let 0 be the orig inal set of formulas over the original vocabulary Let 1 be the set of valid formulas over the vocabulary that in cludes the original one and Witnessing constants for all onefreevariable formulas in g Let LIZ1 be the set of valid formulas over the vocabulary that has Witness ing constants for all onefreevariable formulas in 25 for each number 239 Our nal set of formulas L3 is the union of 2 for all 239 Every Witnessing contant has a date of birth the number of the phase of this construction on which it is created It s easy to see that if a formula of 2 contains a Witness ing constant for a formula containing another Witnessing constant I then the date of birth of b is less than 239 Example of Witnessing Constants Let 20 be ET the Tarski s World vocabulary Let 0 be all formulas over 20 Let 21 be 20 together with all Witnessing constants for onefreevariable formulas in g such as cCube If cCubem is a true Witnessing constant then CubecCube will be true iff 3x Cubex Let 1 be all formulas over 21 such as Smallery comm Then 22 includes Witnessing constants for formulas in 1 such as csmalle ychubam For this last constant to be a true Witnessing constant we would have Smallercsmalle yyccubema CCubec lt Ely Smallery cCubem The Henkin Axioms We want to apply our completeness result for proposi tional Fitch in order to get the completeness result we want for full Fitch To do this we will create a set of ax ioms for the augmented vocabulary with the Witnessing constants Every statement that is an FOL consequence of some premises will be a rstorder consequence of those premises plus the Henkin axioms The ve classes of Henkin axioms will correspond to the nonpropositional proof rules of Fitch Let Px be any formula with exactly one free variable and let 0 and d be any constants The Henkin axioms H consist of H1 Every statement ofthe form Elm Px gt PCp H2 Every statement of the form Pc gt 3x Px H3 Every statement of the form Vx lt gt 3x nPCTDa H4 Every statement of the form c c and H5 Every statement of the form Pc c d gt Pd Proposition 151 Given any model M of the vocabulary for 0 we can interpret the witnessing constants to get a model M of the vocabulary for L such that M39 l H Proof The statements in H2 H3 H4 and H5 are true in every FOL structure because they are provable in Fitch and Fitch is sound We proved half of the generic H3 statement earlier and the other half is similar Statements in H2 H4 and H5 have oneline proofs using 3intro intro and elim respectively So all we need to do is pick the witnessing constants to satisfy all the H1 statements For every formula Px with one free variable we assign 0 1333 to be an element 1 such that M l Pb if any such element exists If no such element exists any element of the domain will do why More precisely we pick a I such that M l P b where M refers to M with the partial assignment of values for witnessing constants with dates of birth less than that of 01333 Q Continuing With Completeness From this proposition we know that if T U H l S then T l S That is if a statement holds in any structure M in which all the sentences of both T and H are true it holds in any model M in which T is true This is be cause given M we can make M which satis es 3 still satis es T and has the same truth value for S But our goal here is to show that if T l S then T l S Later in this lecture we ll show that if T l S then S is a propositional consequence of T U H and thus by propositional completeness T U H l S This as we will now see is good enough to reach our goal 10 Theorem 152 The Elimination Theorem Suppose that S is the conclusion of a Fitch proof whose premises are P1 Pk plus a nite set ofsentences from H Then there is a Fitch proof of S from P1 Pk alone Proof We can use Fitch directly to prove anything in H2 H3 H4 and H5 The interesting case is to eliminate an arbi trary H1 axiom We will need a series of lemmas about Fitch proofs Lemma 153 IfT U P i Q then T l P gt Q Proof With the necessary premises from T as assump tions assume P prove Q as in the given proof and then conclude P gt Q by gtelim Q 11 More Lemmas Lemma 154 IfT i P gt Q andT i P gt Q then T i Q Proof With the necessary premises in place derive P V P from scratch Then assume P prove P gt Q and derive Q by gtelim Then assume P and derive Q from it in the same way Then derive Q from P V P by Velim Q Lemma1551fT P gtQ gtR thenTFIPeR andTi QeR Proof Use ielim gtintr0 Q 12 Still More Lemmas Lemma 156 IfT l Pc gt Q and c does not appear in T or Q then T l Ela gt Q Proof Assume 3x Px use EJelim to get Pc derive P c gt Q from T by the give proof then conclude Q by gtelim Q Lemma 157IfT U 3513 gt Pc l Q then T l Q Proof From the above lemmas and the given proof we know T l Elx gt 130 gt Q T l EJz Pz gt Q and T l Pc gt Q From this last we get 3x gt Q and this is enough to derive Q Q But now we are done with the Elimination Theorem as repeated use of this last lemma can eliminate each H1 premise in any proof from T U H A 13 The Henkin Construction We now need only one more step to prove the complete ness of Fitch Theorem 158 Henkin Construction Let h be a truth assignment to L3 considering all sentences beginningwith a quanti er as atomic that makes every sentence in H true Then there is a model Mb such that for any S Mb S i h makes S true How does this construction give us completeness Sup pose S is a rstorder consequence of a set of sentences T We claim that S must be a propositional consequence of T U 3 If it were not there would be a truth assign ment making T and 3 all true but making S false From the Henkin construction there would then be a structure modeling T U S which contradicts our hypothesis l4 Proof of Henkin construction As in Exercise 1812 we begin by taking the constants themselves including all the witnessing constants as the elements of our do main We set the truth of the atomic formulas from the predicate symbols according to h This won t quite do We are assured that sentences of the form I b are true because they are in H but it is possible for h to assign statements of the form a 1 true where a and b are two di erem constants To be a valid model our M will have to make a and b the same object The way we do this is to make our domain not the set of all constants but a set of equivalence classes of constants where we consider constants a and b to be equivalent iff h makes the formula a 1 true This is the essence of the construction the rest is checking details to make sure we can get away with this 15 Validating the Henkin Construction First we must make sure that if a and b are the same ob ject then Ra and Rb have the same truth value ac cording to h And if a a and b b are both true ac cording to h that Sa b and Sa b have the same truth value and so forth This follows because h makes the H5 axioms true the ones from elim and his proposition ally consistent This is the base case of a big induction on all formulas S showing that this model makes S true iff h does We have dealt with atomic formulas identity and other pred icates and the propositional steps of the induction are clear By using the H1 and H2 axioms we can carry out the inductive step for E To handle V we use the appropriate H3 axiom to convert the V into an El and two 4s then apply the inductive steps for El and I 16 A nal wrinkle comes in if our language has function symbols For every constant d and function f we need to de ne a value for f But since the statement 3x f d 1 is true it holds for its own Witnessing constant Cgzfd and because h says that any other constant c satisfying f d c is equal to this one all such constants are equivalent and f d is a unique object of the domain We have nished the proof of completeness for Fitch Q 17 CMPSCI601 Compactness Theorem Lecture 15 Just as in propositional logic we can apply completeness to get another useful property Theorem 159 Compactness Theorem Let F be a set of sentences Suppose every nite subset of F has a model Then T has a model Proof If F is inconsistent meaning that i can be proved from F in Fitch then some nite subset of F is inconsis tent because Fitch proofs are nite But no nite subset of F can be inconsistent because that set has a model and Fitch is sound So F is consistent By completeness then T has a model 18 CMPSCI 601 Compactness Applications Lecture 15 The Compactness Theorem has surprising consequences for number theory TheoryN 90 E MEN 1 N i 90 F TheoryN U cgt0cgt1cgt2cgt3 Corollary 1510 F has a model There is a countable model 0fThe0ryN that is not iso morphic to N EN cannot uniquely characterize N Proof Every nite subset of F is satis able by N for 239 su iciently large By Compactness F is satis able Q 19 Corollary 1511 Connectedness is not expressible m the rstorder language of graphs 029 Proof Suppose that X E I am connected F X U DISTStgt1DISTstgt 2 DISTx0xn gt n E n l 07171quot 39xn l VO 7 172M Exiv 171 2 Every nite subset of F is satis able By Compactness F is satis able This is a contradiction Thus Connectedness is not expressible in the rstorder language of graphs Q 20 The LowenheimSkolem Theorem Theorem 1512 If a set of rstorder sentences has any model at all it has a countable model Proof Take the truth assignment to L3 arising from the model and use the Henkin Construction to make a model from it Since there were only countably many constants to put into equivalence classes there can be only count ably many classes and thus the new model has a count able domain Q The set of real numbers and the set of countable binary sequences are uncountable But if we de ne a rstorder vocabulary to talk about either of these sets we get a rstorder theory the set of sentences that are true This theory has a countable model Thus there is a countable set with addition and multi plication operations and a zero element that satis es exactly the same rstorder sentences as does the reals Of course the new operations are not the usual ones 21 In rstorder set theory even stranger things happen You can prove that there are sets that are uncountable bigger than the reals and even bigger than that So there is a countable model that has sets that the model thinks are uncountable The reason this is possible is that the notion of one set being an element of another does not have its usual meaning in this model 22
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'