Class Note for CMPSCI 601 at UMass(38)
Class Note for CMPSCI 601 at UMass(38)
Popular in Course
Popular in Department
This 27 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 17 views.
Reviews for Class Note for CMPSCI 601 at UMass(38)
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 Recall From Last Time Lecture 16 De nition F is consistent iff F l7 false Completeness Theorem If F is consistent then P is satis able that is there exists a model A such that A i F Proof Outline 0 Add witnessing constants 0 law for every formula Pa with one free variable c Extend F to an existentially complete theory A that satis es the Henkin Property If A l 332 Pa then A l PCpx c Build a model of T by taking the objects to be equiv alence classes of the constants including the wit nessing constants where two constants c1 and Cg are equivalent if A l 01 2 CQ 0 Check that this model is wellde ned Versions of the Proof There are two versions of Lec ture 15 the one I wrote and the one that Prof Immerman delivered Both are now up on the course web site The principal difference is that Prof Immerman built A to be formally complete as well which simpli es the proof somewhat My version follows BE more closely Corollary to Completeness Fich 42gt icp i so ltgt i so FOVALID FOTHEOREMS Note that FOVALID and FOTHEOREMS are state ments that are true in any model of the given vocabu lary While we constructed a special model where every statement was either provably true or provably false this is not true in general An FOVALID statement about graphs would be true for all graphs but most interesting statements are true for some graphs and not for others CMPSCI601 Compactness Theorem Lecture 16 Just as in propositional logic we can apply completeness to get another useful property Theorem 161 Compactness Theorem Let F be a set of sentences Suppose every nite subset of F has a model Then F 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 F has a model CMPSCI 601 Compactness Applications Lecture 16 The Compactness Theorem has surprising consequences for number theory TheoryN 2 90 E MEN 1 N i 90 F 2 TheoryN U cgt0cgt1cgt2cgt3 Corollary 162 This theory F has a model There is a countable model of TheoryN 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 6 Corollary 163 Connectedness is not expressible m the rstorder language of graphs Eg Proof Suppose that X E I am connected F 2 x U DIST3tgt1DISTstgt 2 DIST0azn gt n E n l V1 n 1 V 93239 03241 Ez39 93241 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 6 The Downward LowenheimSkolem Theorem Theorem 164 If a set Of rstOrder sentences T0 has any model at all it has a countable model Proof Suppose that To has a model By the Sound ness Theorem T0 must be consistent Our proof of the Completeness Theorem thus constructs a model for T0 where the objects are the equivalence classes made from the witnessing constants 01 02 Since there were only countably many constants to put into equivalence classes there can be only countably many classes and thus this new model has a countable domain 0 The set of real numbers R and the set of countable binary sequences are both uncountable But if we de ne a rst order vocabulary to talk about R for example we get a rstorder theory ThR the set of rstorder sentences that are true about the actual real numbers R 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 R Some thing must be wrong with this model since it s not the real R but we can t state whatever it is in rstorder logic In rstorder set theory even stranger things happen You can prove that there are sets that are uncountable big ger than the reals and even bigger than that So there is a countable model M that has sets that M thinks are uncountable The reason this is possible is that the de nition of C is countable is that there exists a onetoone function from C to N Thus M might think that a set C39 that is actually countable is uncountable because M doesn t have any of the functions that demonstrate that C is countable 91 9mm 510911 l JaqmnN 311110 J 109 IOSdWO 14 NlNT AlNT NT is a set of statements in the vocabulary of number theory As you can easily see all of them are true for the structure N consisting of the actual natural numbers NT consists of the rst four of the Peano axioms to gether with the two parts of the inductive de nitions of addition multiplication and exponentiation and order 10 But we re missing the fth Peano axiom the rule of mathematical induction This means that there s plenty we can t prove from NT including such simple things as the commutativity of addition and multiplication We call the sentences provable from NT a fragment of true number theory Why don t we include the rule of induction For one thing in the world of rstorder logic it is an in nite set of axioms For every formula Pa with one free variable we need a separate axiom to say that Va Pa follows from P0 and Va Pa gt Paa There is a larger fragment of number theory called Peano Arithmetic that has these induction axioms But we ll see that there are things true of N that can t be proved in Peano Arithmetic either And NT will be powerful enough to allow us to prove the Incompleteness Theo rem which is our main goal here 11 First let s see that NT is actually good for something This theorem is number 61 in P which is a good refer ence if you want to learn more Theorem 165 Let go have no variables Then N l 90 42gt NT 1 0 Proof 0 is a boolean combination of t lt t t 2 t Case 1 t and t are numbers 00 00 use NT1 NTQ lt use NTm NT13 NT14 Case 2 tt use gtltT Use NT4 NTg to transform these to numbers 6 12 De nition 166 A formula 0 E ZN is bounded iff it can be written with all quanti ers in front and all univer sal quanti ers bounded 6 Example Va lt 9 JyVz lt 2 T a x T 3 z T 3 17 Remark If 901 is bounded and has only one free variable 11 then STD is re where 590 RENINTltPH Note that the bounded sentences are not closed under negation They are sentences that you can check by a naming numbers and b doing sequences of tests that are guar anteed to nish This is reminiscent of Bloop but not the same thing be cause there is no equivalent in Bloop for the unbounded El A proof can name a number but a Bloop program can t look for it Without a limit on how far it may look 13 NT is strong enough to deal with these sentences as well as we see from the following P s Theorem 62 Theorem 167 Let p be a bounded sentence a bounded formula with no free variables Then lecp 42gt NTl cp Proof lt2 Since Fitch is sound and NT is true in N everything we prove from NT is also true in N gt We use induction on the number of quanti ers in 0 Assume N l 0 Base case A sentence with no quanti ers has no vari ables so we are done by the previous theorem Inductive step 0 E 332W Thus N l 2M3 lt n for some particular n E N Thus NT l z a lt n by the inductive hypothesis Thus NT l p by ElIntro l4 Other Inductive step 0 E Va lt tw The term t must be closed meaning that no variables occur in it So by unrolling the operations NT t 2 n for some particular n E N NT10NT11NT14 i a lt n gt a 2 0V3 21a 2 72 1 N2 b i2QHWn 1 NTFMxe i2QHWn 1 Now we can do a big Aelim with a 2 t as the other case to get NTi cp 15 De nition 168 Let f N gt N Formula pf represents f iff forall n1 nk m E N fn1nkm 42gt Nltpfn1nkm 6 Example f 2 n2 1 Let pfnm E n x n1 m WWW ltgt nxn1m 4 fnm What Does This Mean Ifcpfm m is a bounded formula then so is Elm pfm m which says that f is de ned on input n Remember that NT can prove any true bounded sentence So while it may not be able to prove Vn Elm f n m f is well de ned it can prove that f exists for any particular n 16 What other functions can we represent All our tools for talking about sequences for starters Lemma 169 T he primitive recursive functions Prime PrimeF IsSeq Length and Item are each representable by bounded formulas Proof PrimeFn p asserts that p is prime number n by assert ing that there exists a number s 20x31gtlt52gtlt73gtlt114gtltgtltpn asly 3zlty1agtltzy DEW 631 33er A ae H Xy Primea E 3 gt1 Vyz lt x z as PrimeFnp E 33Primep 2 X3 DEpns Vq S p39q lt a PrimeQ V 1Primeq Gigquot lt qq39 lt qquot Primeq v 38 lt 1DEq39es DEq e 1s 17 IsSeqa E 32 lt lt at3p lt 2 T acPrimeFip g z1 plat gt z1 plx Lengtha E ElkpqIsSeqa k1 PrimeFk p APrimeFUf q plat q Itemaie E 3pIsSeqa PrimeFip DEp e 1 18 It s not a coincidence that these formulas are all primitive recursive and all representable by bounded formulas Theorem 1610 Every primitive recursive function is rep resentable by a bounded formula Proof I d make this an exercise but it s in Lecture 15 of the Spring 2003 notes You might think we could have skipped the clever proofs for the individual func tions above But the proof of this theorem uses sequences to deal with primitive recursion We have to do the work of coding sequences as numbers someplace 0 l9 Bloop Floop and Bounded Formulas Note In fact whenever we use an El quanti er in the proofs above with some more effort we could have made it a bounded El quanti er A function is Bloopcomputable iff it is represented by a formula where both kinds of quanti ers are bounded It should be pretty clear that a Bloop program can test the truth of such a completely bounded formula On HW5 I ll have you prove that a function is Floop computable iff it is represented by a bounded formula as we have de ned it here ie a Vbounded formula The intuition should be pretty clear in Floop you can look for the number satisfying the unbounded El and with the bounded formula you can use 3 to express that the whi l e loops will terminate But note that all we are going to need to prove Godel s theorem is that being Bloopcomputable primitive recur sive implies representability by a bounded formula 20 Now What is This Good For Remember the most complicated primitive recursive pred icate we looked at earlier COMPn as c 3 meaning that c is a halting computation of the Turing machine Mn on input as and that its output is 3 Theorem 1611 COMPn as c y is represented by a bounded formula Proof This would follow from the general theorem about primitive recursive functions of course But even With out that you can go back to Lecture 9 where we proved that COMP is a primitive recursive predicate by express ing it in terms of the sequence operations This argument essentially constructs the bounded formula directly I ll have you follow up on the details in HW5 0 21 Now things get interesting Corollary 1612 K is representable by a bounded for mula Proof cp n E 30COMPn n c 1 By our earlier results about NT K 711 Niltmltn K n l NTFWW O Our standard unsolvable problem can be de ned in terms of NT 22 De nition 1613 For a structure A E STRUCZ TheoryM 90 E 152 I A 1 so TheoryN 2 90 E EN I N t 90 Thus TheoryN is true number theory Theorem 1614 Godel s Incompleteness Theorem There is no re set of sentences P such that I N F and 2 F F TheoryN There is no axiomatization of number theory much less all of mathematics 23 Proof Let F be re and N l P 5 HEN l Fl lenB S is re and S g F Why the latter Because if a number n were in K we would have NT l cme which is impossible because NT and F are both true in N Intuitively S 2 n E N I F l n E F S is an re subset of the nonre set F It can t be equal to F and in fact it has to miss in nitely many elements Since if it missed only nitely many 5 plus those ele ments would still form an re set So there eXist in nitely many n E N st N l WM and F l7 WM 9 24 Actually P states this result in the following form P Theorem 63 T he set of unsatis able sentences and the set of sentences provable from NT are recursively inseparable Thus a recursive set not only cannot separate true number theory from false number theory but can t even include all the true bounded formulas without letting in some thing inconsistent P has proved that the sets M M outputs yes on e and M M outputs no on e are recursively insepara ble Try to show this yourself Look at the sentence NT holds and there is an accepting computation of M on e If M says yes this is prov able from NT If M says no it is inconsistent because it says that the computation says no while NT can prove that it says yes 25 CMPSCI601 Sketch of Godel s Original Proof Lecture 16 0 Encode symbols as natural numbers 0 Encode formulas as nite sequences of natural num bers 0 Encode proofs as nite sequences of formulas 0 Let F be a primitive recursive axiomatization of some portion of mathematics including number theory The following predicates are primitive recursive and thus rstorder de nable in MEN Formulaa a is the number of a formula Axioma a is the number of an axiom Proofa a is the number of a proof Theorema a is the number of a theorem 0 Let 1 R1 list all rstorder formulas with one free variable ie rstorder de nable sets LetG 2 n I 1TheoremRnn 0 G 2 n I Rqn for some q Rqq E x TheoremRqq E I am not a theo rem If Rqq then P l7 Rqq Ifquq then P l Rqq 26 Theorem 1615 FOTHEOREMS is re complete Proof We have already seen that FOTHEOREMS is re Recall that K is represented by a bounded formula pK nEK 42gt NltpKn 42gt NTl cpKn n E K 42gt NT gt cp n E FOTHEOREMS We have shown K g FOTHEOREMS by de ning f so that n 2 NT gt cp n 27
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'