《FoundationsofLogic (8).pdf》由会员分享，可在线阅读，更多相关《FoundationsofLogic (8).pdf（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremOnline Course:Foundations of LogicDag Westerst ahlTsinghua LogicBackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremChapter 7For some historical background,read
2、 Chapter 7.1!The only way to know a scientific claim is to have evidence thatjustifies the claim.If its a mathematical claim,the only acceptable evidence is a proof.A proof starts from axioms(that dont need justification)andproceeds by logical inference.If the claim is formulated in FOL,we can colle
3、ct the axioms in atheory,and rely on the proof methods of the Hilbert system H.To be of any use,a theory must be consistent.So wed like to beable to prove the consistency of various theories(since someproposals turned out to be inconsistent;Russells Paradox).It seems natural to start with something
4、simple and very familiar,like arithmetic(number theory).1 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremAn apparently reasonable programThere is a well-known axiomatic theory of arithmetic,calledPeano Arithmetic(PA)in its first-order version,whi
5、ch provesalmost all number-theoretic facts that we currently know.So the initial project seems clear:IShow that PA or some similar theory proves not only allnumber-theoretic facts(in the vocabulary LPA)that weknow,but all true such facts.IProve that PA is consistent.This is where G odels incompleten
6、ess theorems enter thepicture.2 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe incompleteness theoremsInformal statement of the theorems:Theorem(the incompleteness theorems,G odel,1931)(1)Every consistent axiomatizable theory T which contains
7、 someelementary arithmetic is incomplete.(2)The consistency of such a theory T cannot be proved in T itself.PA is an example of such a theory.So PA is incomplete:there is asentence such that PA 6 and PA 6.Since every LPA-sentence is either true or false(in N),there must be atrue sentence which is no
8、t provable in PA.Moreover,it doesnt help to add more axioms!(as long as the result isaxiomatizable).So the first part of the program cannot be realized!3 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremProving consistencyTheorem(second incompleten
9、ess theorem)(2)The consistency of such a theory T cannot be proved in T itself.The second part of the program is also in trouble.Hilberts program was to prove consistency by completely reliable finitary methods.This seemed reasonable:a matter of analyzingpossible derivations from PA in the system H,
10、i.e.finite sequences ofsentences,and prove that none could end with e.g.0 6=0.But it also seemed that all of these methods(and more)are available inthe theory PA.Then the second incompleteness theorem shows that the goal of provingconsistency,even of PA,by finitary methods is unreachable!4 of 26Back
11、groundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe impact of G odels incompleteness theoremsThese theorems are not only cornerstones of modern logic,they have sparkedwide discussion outside logic,and have been taken to show many things:I“that human beings
12、 are not machines”I“that there is a special kind of mathematical insight that goes beyondmathematical proof”I“that we can never know that a theory is consistent”I.We will get back to these questions when we have seen exactly what thetheorems say and how they are proved.5 of 26BackgroundProving incom
13、pletenessG odels proofArithmetizationUndefinability of truthL obs TheoremMaking it preciseTheorem(1)Every consistent axiomatizable theory T which contains someelementary arithmetic is incomplete.(2)The consistency of such a theory T cannot be proved in T itself.We already know what consistent,axioma
14、tizable(at least informally),and complete mean.We must still make clear(a)what is means that T contains someelementary arithmetic,and(b)what it would mean to prove theconsistency of e.g.PA in PA.As to(a),we shall first assume that LT=LPA,and that T is an extensionof PA,in the sense that every theore
15、m of PA is also a theorem of T.(b)requires coding informal reasoning about of sentences and derivationsas reasoning in PA.Actually,this coding is also needed for the proof ofthe first incompleteness theorem.6 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL o
16、bs TheoremDecidabilityCoding,also called G odel numbering,can also be used to codeproblems as sets of numbers.Let#()be the G odel number of.For example,the validity problem for PL deciding if a sentenceis a tautology or not becomes the set ValPL=#():|=PL.This set is decidable:the truth table method
17、can be spelled out asa decision procedure for testing,for any number n,if n belongs toValPLor not.A main achievement during the 1930s,mainly due to Alan Turing,was to make the notion of decidability precise.Decidable sets,or more generally relations and functions,are calledrecursive(or computable).7
18、 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremUndecidabilityIf recursivity captures the informal idea of decidability or solvability this is the Church-Turing Thesis then a set which is not recursive canencode an undecidable or unsolvable probl
19、em.It was a completely new idea that such a notion could be made precise.If T is a theory,letThmT=#():T We say that T is undecidable if ThmTis not recursive.We will show:Theorem(undecidable theories)(1)Every consistent theory T which contains some elementaryarithmetic is undecidable.(2)The validity
20、problem for FOL is undecidable.8 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremDecidability,axiomatizability,and completenessHere is a simple but important observation:FactEvery complete axiomatizable theory is decidable.9 of 26BackgroundProving
21、 incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremA non-constructive proofOne road to the first incompleteness theorem goes by first showing theundecidability fact just mentioned:(1)Every consistent theory T which contains some elementary arithmeticis undecidable.Togethe
22、r with what we just showed,(2)Every complete axiomatizable theory is decidable.this immediately gives incompleteness:(3)Every consistent axiomatizable theory T which contains someelementary arithmetic is incomplete.BUT this proof is non-constructive in that it doesnt give us an explicitundecidable s
23、entence(=a sentence s.t.T 6 and T 6).AND itdoesnt prove the second incompleteness theorem.10 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe Liar paradoxG odel found a method to directly construct an undecidablesentence.The idea is based on an
24、 analogy with the Liar paradox:(1)This sentence is falseVariants:11 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs Theorem12 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe proof ideaGiven an axio
25、matizable consistent theory T containing PA,the idea is toconstruct an LPA-sentence G which says that it is not provable in T.This requires(a)that every sentence has a name,i.e.a closedLPA-term,say pq,that denotes,and(b)that there is an LPA-formula,say PrT(y),which somehow expresses that y is provab
26、le in T.It also requires that we can find a sentence G such that(x)PA G PrT(pGq)Proof idea:If G were provable in T,that would,by(i),make Tinconsistent,contrary to assumption.Thus,G is not provable.But thatswhat G says,so G is true,and thus G is false.So if no false sentencesare provable in T,G is no
27、t provable either.NB No paradox!13 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremMaking the idea preciseSuppose(x)PA G PrT(pGq)That PrT(y)expresses provability should mean that for every sentence:(I)If T ,then T PrT(pq).(II)If T PrT(pq),then T .
28、Then:Note that this argument doesnt involve truth(in N).14 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThings to doFirst we must do the G odel numbering of all relevant syntactic objects:u 7#(u)NThen properties of symbols,sentences,derivations
29、,etc.translate intoproperties of numbers:Ivar(n)iffn is the G odel number of a variableIterm(n)iffn is the number of a term(in LPA)Isent(n)iffn is the number of a sentenceIaxT(n)iffn is the number of an axiom in TIprfT(m,n)iffm is the number of a derivation in H of sentencenumber n from the axioms i
30、n T15 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremRepresentable sets and relationsNext,we must say how these sets and relation can be represented in PAor T.Recall the numerals 0,1,2,.,where n is 0000,0 followed by n primes.We say that a k-ary
31、relation R among numbers is representable in T ifthere is an LPA-formula(x1,.,xk)such that:Iif R(n1,.,nk),then T (n1,.,nk);Iif not R(n1,.,nk),then T (n1,.,nk)Then we must show that all the relations we are interested in are in factrepresentable in PA(and therefore in any extension of PA).16 of 26Bac
32、kgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremRepresentation in PAWe do this by showing that(a)all these relations are computable in a strong sense,namely,they are primitive recursive;(b)all primitive recursive relations are representable in PA.This wil
33、l take a while.(So we start next time by defining the primitive recursive relationsand functions.)17 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe proof relationSuppose all this has been taken care of.We use this notation:pq is the numeral o
34、f the G odel number of (i.e.of#().There is a formula PrfT(x,y)representing the relation prfT(m,n)in PA:Iif prfT(m,n),then PA PrfT(m,n)Iif not prfT(m,n),then PA PrfT(m,n)(Here we are assuming that T is axiomatizable in the sense that axTis aprimitive recursive set.Then the relation prfTis also primit
35、ive recursive.)Thus:Iif m is the number of a proof of in T,then PA PrfT(m,pq)Iif not,then PA PrfT(m,pq).18 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremDiagonalizationWe still need to find a sentence G which says“I am not provable in T”.This is
36、 an instance of the existence of self-referential or diagonalsentences in LPA:Lemma(Diagonal Lemma)For any formula(y)with the single free variable y there is a sentence such thatPA (pq)Let(y)be the formulaPrT(y):=xPrfT(x,y)So there exists a sentence G such thatPA G xPrfT(x,pGq)19 of 26BackgroundProv
37、ing incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe proof again(1)PA G xPrfT(x,pGq)This is the formula we wanted.Recall our two principles:(I)If T ,then T PrT(pq).(II)If T PrT(pq),then T Principle(I)is a consequence of the fact that the relation prfTisrepresented by
38、 the formula PrfT(x,y)in T:Principle(II)does not follow from that.G odel had to make an extraassumption(-consistency)to insure(II).Later Rosser showed that,with aslightly more complicated self-referential sentence than G,we can avoid(II)(consistency of T is enough.)20 of 26BackgroundProving incomple
39、tenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe second incompleteness theoremHere is a sentence saying that T is consistent:ConT:=PrT(p0 6=0q)Now the idea is to formalize the first part of the proof of the firstincompleteness theorem in PA:if G is provable in T,then T isinc
40、onsistent.The result should be:PA PrT(pGq)ConT21 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremThe undefinability of truthDiagonalization has many other applications.One is Tarskis theorem onthe undefinability of truth.A truth definition in T is
41、 a formula Tr(y)such that for every sentence:T Tr(pq)Theorem(undefinability of truth Tarski,1933)If T is a consistent extension of PA,there is no truth definition in T.Even in Th(N),there is no truth definition!22 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of tru
42、thL obs TheoremL obs TheoremTheorem(L obs Theorem,1955)If T is a consistent axiomatizable extension of PA,and ifT PrT(pq),then T .T cannot prove its own correctness.CorollaryIf PA H PrT(x,pHq)(“I am provable in T”),then T H.Compare the Truth Teller:“This sentence is true”.23 of 26BackgroundProving i
43、ncompletenessG odels proofArithmetizationUndefinability of truthL obs TheoremNext Thursday:Chapter 824 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs Theorem25 of 26BackgroundProving incompletenessG odels proofArithmetizationUndefinability of truthL obs Theorem26 of 26