### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 601 at UMass(33)

### View Full Document

## 19

## 0

## 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.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 601 at UMass(33)

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.