Class Note for CMPSCI 601 at UMass(33)
Class Note for CMPSCI 601 at UMass(33)
Popular in Course
Popular in Department
This 19 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 19 views.
Reviews for Class Note for CMPSCI 601 at UMass(33)
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 15 De nition F is consistent iff P if false Completeness Theorem If F is consistent then P is satis able that is there exists a model A such that A l P Corollary F l p ltgt F l p i so ltgt P so FOVALID FOTHEOREMS Note that FOVALID and FOTHEOREMS are state ments that are true in any model of the given structure While we constructed a special model where every state ment 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 state ments are true for some graphs and not for others Compactness Theorem If every nite subset of F has a model then P has a model 1 m gt a lt ltlt gt0 gt 200 v lt0 gt mm 2 gt an 2 gt v gt 91 9mm 510911 l JaqmnN 311110 J 109 IOSdWO 14 NNT 2 Aler The statements of NT are all true and can be used to prove a fragment of true number theory Theorem 61 Papa Let 0 have no variables Then N i 90 42gt NT i 0 Proof 0 is a boolean combination of t lt t t 2 t Case 1 tt numbers 00 00 use NT1 NTQ lt use NTm NT13 NT14 Case 2 t t use gtltT Use NT4 NTg to transform these to numbers A De nition 151 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 A Example Va lt 93y72 lt 2 T a X T 3 z T 3 17 Remark If 902 is bounded and has only one free variable 39u then 50 is re Where 590 RENINTltPTL 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 E A proof can name a number but a Bloop program can t look for it Without a limit on how far it may look Theorem 62 Papa Let p be a bounded sentence ie no free variables Then N 90 42gt NT p Proof Soundness Theorem gt induction on number of quanti ers in 0 Assume N i 0 Base case Theorem 61 Inductive step 0 E 3mm Thus N i x lt n for some n E N Thus NT i v x lt n Thus NT i p Inductive step 0 E Vx lt t b t is a closed term thus NT t 2 n for some NT10NT11NT14 F 17 lt 7 1 gt 8 2 0V2 21V i0n 1 NTFMaH i i0n 1 NTFcp nEN x 72 1 De nition 152 Let f N gt N Formula pf represents f iff forall n1 nk m E N fn1nkm 42gt Nltpfn1nkm A Lemma 153 T he following primitive recursive functions Prime PrimeF IsSeq length and Item are each repre sentable by bounded formulas Proof PrimeFn p asserts that p is prime number n by assert ing that there exists a number s 20gtlt31gtlt52gtlt73gtlt114gtltgtltpn xly 32lty1xgtltzy DEx8y Ter we Xy Primex E 1 gt1 Vyz lt X 2 a x PrimeFnp E 38Primep 2 X8 DEp n s W S pVQ lt q PrimeQ V Primew V 341quot lt 41W lt q Primeltaquot 38 lt qDEq39 e s DEq e 1 IsSeqx E 32 lt lt x3p lt 2 T xPrimeFip z1 p113 igtz1 plx lengthx E 3kpqIsSeqx k1 PrimeFkpj PrimeF q p11 q Itemxie E 3pIsSeqx PrimeFip DEpe1xi A Theorem 154 Every primitive recursive function is rep resentable by a bounded formula Proof Base case Obvious for the initial functions Inductive step Composition f l1 m 2 hglx1 xk gmx1 By inductive assumption h and the 92 s are representable 90M 2 E 391 ym wgl 91M 909mi gm M211 ym 2 10 Inductive step Primitive Recursion Cali 73116 9 17317 39 39 hfn7y17 39 39 39 7yk7n7y17 39 39 39 By inductive assumption 9 and h are representable f is representable as follows WW 3 2 E 38Vi lt x3a b lt sIsSeqs Itemsi a Itemsi1b 2 0 gt 9093 1 phaigjb Itemsxz ll Bloop Floop and Bounded Formulas Note In fact whenever we use an E quanti er in this proof with some more effort we could make it a bounded E quanti er A function is Bloopcomputable iff it is rep resented 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 for mula A formula is Floopcomputable iff it is represented by a Vbounded formula as we have de ned it here I m not going to prove these assertions all we need to prove Godel s theorem is that Bloopcomputable primi tive recursive implies representability by a bounded for mula 12 A Fact We Didn t Prove This Time The primitive recursive predicate COMPn 13 c y mean ing that c is a halting computation of Turing machine Mn on input 1 and its output is y How to prove it Write Bloop programs for PrimeF IsSeq Item and so forth Then write a Bloop program that interprets c as a sequence of con gurations and tests that each con guration follows from the one before ac cording to the rules of the machine Mn Section 62 of P in effect does this I ll just appeal to the intuition I hope you ve formed about Bloop Corollary 155 K is representable by a bounded formula cp n 30COMPn n c 1 K 711 Nllteen K 2 n NTl cpKn l3 CMPSCI 601 Summary S0 Far Lecture 15 14 NT 2 1 NTZ39 6 De nition A formula 0 E ZN is bounded iff it can be written with all quanti ers in front and all universal quanti ers bounded Theorem 62 Papa Let p be a bounded sentence Then N l 90 42gt NT l 0 De nition pf represents f iff forall 711 nk m E N fn1nkm 42gt Nltpfn1nkm Theorem Every primitive recursive function is repre sentable by a bounded formula Corollary K is representable by a bounded formula cp n E 30COMPn n c 1 K n l Nlltpzltn K 2 n NTl cpKn 14 De nition 156 For a structure A E STRUCZ TheoryM 90 E 132 I A 1 so TheoryN 2 90 E ZN I N t 90 Thus TheoryN is true number theory Theorem 157 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 15 Proof Let F be re and N l P 5 HEN l Fl w n S is re and S g F 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 4 l6 P states this result in the following form proves this in the form of his Theorem 63 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 Recall that the sets M M outputs yes on e and M M outputs no on e are recursively inseparable 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 17 CMPSCI601 Sketch of Godel s Original Proof Lecture 15 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 axiomitization of some portion of mathematics including number theory The following predicates are primitive recursive and thus rstorder de nable in MEN Formulax x is the number of a formula Axiomx x is the number of an axiom Proofx x is the number of a proof Theoremx x is the number of a theorem 0 Let R0 R1 list all rstorder formulas with one free variable ie rstorder de nable sets tLetG 2 n I TheoremRnn 0 G 2 n I Rqn for some q 0 Rqq E TheoremRqq E I am not a theo rem 0 If Rqq then P l7 Rqq If RqQZ then P l Rqq 18 Theorem 158 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 cpKO L E FOTHEOREMS We have shown K g FOTHEOREMS by de ning f so that f n NT gt WM 19
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'