FoundationsofLogic (13).pdf

《FoundationsofLogic (13).pdf》由会员分享，可在线阅读，更多相关《FoundationsofLogic (13).pdf（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningOnline Course:Foundations of LogicDag Westerst ahlLecture 14:Incompleteness 1April 2,2020Dag Westerst ahlTsinghua LogicDiagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningTranslation throu

2、gh arithmetization 1When axTis primitive recursive(and T is a consistent extension of PA),the relation prfTis also primitive recursive,and thus representable in PAby a formula PrfT(x,y).Clearly,axPAis primitive recursive.This means we can translate from our informal metalanguage into thelanguage of

3、PA.For example,we know that(1)PA x 0+x=xsince we gave a proof of x 0+x=x in PA(more precisely,weconvinced ourselves that there is such a proof).The translation of(1)is(2)xPrfPA(x,px 0+x=xq)And since this proof has a G odel number m,and PrfPA(x,y)representsprfPAin PA,the translation of(1)is actually

4、provable in PA:PA xPrfPA(x,px 0+x=xq)1 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningTranslation through arithmetization 2Similarly,the true claim(3)PA 6 x x=x0gets translated into(4)However,(4),although true,is not provable in PA!This will be a consequence o

5、f the second incompleteness theorem,since(4)is essentially equivalent to the sentence ConPAwhich says that PA isconsistent.To get there,we start with the first incompleteness theorem,and asentence G which says“I am not provable in T”.2 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd

6、 TheoremModal reasoningDiagonalization:the taskConsider a formula(y).So(y)says that y has the property.If we replace(all free occurrencers of)y by the G odel number of somesentence,we get(pq)This sentence says that has property.But the G odel number of(pq)is distinct from the G odel number of.(Why?)

7、But we dont need the G odel numbers to be the same;we need to find a which is equivalent(in PA to(pq).This can be arranged with a clever use of substitution.3 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningDiagonalization:using the sub functionRecallsub(m,n,j)

8、=the result of replacing each freeif m is a term or aoccurrence of vjin m by nformula,n is a term,and n is free for vjin m0otherwiseConsider the following special case,where x is the variable v0:sub0(m,n)=sub(m,num(n),0)Thus,sub0(m,n)=the result of replacing all freeoccurrences of x in m by nif m is

9、 a formula or a term0otherwiseLet the formula Sub0(x1,x2,y)define sub0in PA.4 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningThe Diagonal Lemmasub0(m,n)=the result of replacing all freeoccurrences of x in m by nif m is a formula or a term0otherwise(a)If sub0(m

10、,n)=k,then PA y(Sub0(m,n,y)y=k)Now let(y)be any formula(with y as the only free variable),and let(x):=y(Sub0(x,x,y)(y)(x)has a G odel number k.Finally,let be the sentence(k),i.e:=y(Sub0(pq,pq,y)(y)Claim:PA (pq)This is the Diagonal Lemma.5 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels

11、2nd TheoremModal reasoningProof of the Diagonal Lemmasub0(m,n)=the result of replacing all freeoccurrences of x in m by nif m is a formula or a term0otherwise(a)If sub0(m,n)=k,then PA y(Sub0(m,n,y)y=k)(b)Given(y),let(x):=y(Sub0(x,x,y)(y),and(c):=y(Sub0(pq,pq,y)(y)6 of 26Diagonal LemmaG odels 1st The

12、oremRossers TheoremG odels 2nd TheoremModal reasoningProof of the Diagonal LemmaSo,to repeat:Lemma(Diagonal Lemma)For every formula(y)with just the free variable y there is a sentence such thatPA (pq)It is precisely in this reather weak sense that such sentences saysomething about themselves,namely,

13、that they have property.But this is enough for the first incompleteness theorem.7 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning1st Incompleteness Theorem,first partWe already saw(Chapter 7)how the first part of the proof goes.Suppose T is a consistent primit

14、ive recursive(i.e.axTis primitiverecursive)extension of PA.Let(y)be the formula xPrfT(x,y),and let G be the sentence thatexists by the Diagonal Lemma:PA G xPrfT(x,pGq)Part 1 of proof:Show that T 6 G.8 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning1st Incomple

15、teness Theorem,second part(i)As we also noted,the first part uses the fact that for any sentence:(I)If T ,then T xPrfT(x,pq).It follows from the first part that G is a true sentence.So G is false.If we know that T does not prove any false sentences,i.e.that T is atrue theory,then we could conclude d

16、irectly that T 6 G.For example,if T is PA,we can be pretty sure all the axioms,and henceall theorems,are true.But the incompleteness theorems apply much more generally;also totheories that may have false axioms as long as they are consistent.9 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG o

17、dels 2nd TheoremModal reasoning1st Incompleteness Theorem,second part(ii)(I)If T ,then T xPrfT(x,pq).We also observed that the following would suffice for the second part ofthe proof:(II)If T xPrfT(x,pq),then T .G odel used a more concrete assumption,which strengthens consistency,and implies(II).He

18、called it-consistency.10 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning-consistencyDefinitionA theory T is-consistent if for every formula(x)which is such thatT (k)for every number k,we have T 6 x(x).We observe:(a)-consistency implies ordinary consistency.(b)

19、-consistency implies principle(II).11 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning1st Incompleteness Theorem,G odels formulationWe have shown:Theorem(1st Incompleteness Theorem,G odel 1931)If T is an-consistent primitive recursive extension of PA,then T isi

20、ncomplete:we can effectively find a(true)sentence G such that T 6 Gand T 6 G.In particular,incompleteness is an inherent phenomenon:it doesnt helpto add more axioms!Consider the theory T0=T+G.T0has a false axiom,but isnevertheless consistent.(Why?)But T0is-inconsistent:12 of 26Diagonal LemmaG odels

21、1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning1st Incompleteness Theorem:generalizationsTheorem(1st Incompleteness Theorem)If T is an-consistent prim.rec.extension of PA,then T is incomplete:wecan effectively find a(true)sentence G such that T 6 G and T 6 G.This can be generalized in s

22、everal ways:IOne can replace“primitive recursive”by a more general notion“axiomatizable”.IOne can change the requirement that T is an extension of PA tothat T contains PA in a weaker sense(next time).IAnd in fact all of PA is not needed,a(finite)theory Q suffices.IBut the first improvement is to rep

23、lace-consistency by ordinaryconsistency.13 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningRossers version of the 1st Incompleteness TheoremTheorem(1st Incompleteness Theorem,Rosser 1936)If T is a consistent prim.rec.extension of PA,then T is incomplete:we cane

24、ffectively find a(true)sentence R such that T 6 R and T 6 R.Rossers trick was to use a more complex self-referential sentence.Let(y)be the formulax(PrfT(x,y)zzxRefT(z,y)Here RefT(x,y)says that x is a proof of y,exactly as PrfT(x,y)saysthat x is a proof of y.By the Diagonal Lemma,there is a sentence

25、R such thatPA R x(PrfT(x,pRq)zzxRefT(z,pRq)What does R say about itself?Is R true?14 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningPA R x(PrfT(x,pRq)zzxRefT(z,pRq)15 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning16 of

26、26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning2nd Incompleteness TheoremLetConT:=xPrfT(x,p0 6=0q)The first part of the proof of the 1st Incompleteness Theorem(whichonly uses consistency,not-consistency)showedIf T G,then T is inconsistent.This reasoning can be fo

27、rmalized in PA,resulting inPA xPrfT(x,pGq)ConTSince PA G xPrfT(x,pGq),we getPA ConT GThus,if T ConT,then T G,which we know is false.Therefore,T 6 ConT17 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningDerivability conditionsTheorem(2nd Incompleteness Theorem,G

28、odel 1931)If T is a consistent primitive recursive extension of PA,then T 6 ConT.Formalizing the first part of the proof of the 1st Incompleteness Theoremis a lot of work.It can be seen that the following derivability conditions of the formulaB(y):=xPrfT(x,y)suffice:(D1)If T ,then T B(pq).(D2)T B(pq

29、)(B(p q)B(pq)(D3)T B(pq)B(pB(pq)q)18 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningA modal logic version 1In fact,the reasoning can be rendered in the language of modalpropositional logic.Instead ofT B(pq)write 2Translate(D1)(D3)as follows:(D1)If ,then 2.(D2)

30、2 (2()2)(D3)2 22(Note that the distinction between and pq disappears.)19 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningA modal logic version 2In modal logic,2 can be read as necessarily,or the agent knowsthat,but also as provably (first suggested by G odel).T

31、he translated(D1)(D3)are familiar axioms and rules in modal logic:(D1)If ,then 2.(Necessitation rule)(D2)2 (2()2)(K axiom)(D3)2 22(4 axiom)This,together with ordinary propositional logic,is the modal logic K4.The reasoning in Chapter 12.45 can be rendered in K4:Let T is consistent be the claim that

32、6,and let ConT be the sentence 2.Also,let the sentence G(from the Diagonal Lemma)be such that(1)G 2G20 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningModal reasoning 1First:(2)2 (2 2)(1)G 2GHere is the first half of the 1st Incompleteness Theorem:(3)If 6,then

33、6 G.21 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningModal reasoning 2Then we get the 2nd Incompleteness Theorem:(4)If 6,then 6 2.22 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningModal reasoning 3Finally,we get L obs T

34、heorem:(5)If 2 ,then 2.This has the curious consequence that the sentence which says“I amprovable in T”is in fact provable in T!(exists by the Diagonal Lemma:PA xPrfT(x,pq).)Compare the Truth Teller:“This sentence is true”)The formalized version of L obs Theorem is2(2 )2Adding this axiom to(D1)(D3)g

35、ives an interesting modal logic,calledprovability logic(or GL,for G odel-L ob).In GL one can prove a DiagonalLemma,and e.g.a formalized version of the 2nd Incompleteness Theorem:(6)2 2(2)23 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningProof of L obs TheoremA

36、ssume 2 .Show .With the Diagonal Lemma we find a sentence C such that(a)C (2C )(“If I am provable then”,cf.Currys Paradox!)24 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoningThursday April 9:Finale!25 of 26Diagonal LemmaG odels 1st TheoremRossers TheoremG odels 2nd TheoremModal reasoning26 of 26