FoundationsofLogic (14).pdf

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

1、Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthOnline Course:Foundations of LogicDag Westerst ahlTsinghua LogicTwo thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthTwo things(1)The exam homework will be poste

2、d later today,or tomorrowat the latest.Concerning Chapter 12,we will skip section12.7.(2)We will end this course with a photo session,in the sensethat all of you should turn on your videos,so everybody ispresent with picture on the Zoom screen,and we canpresumably save this image.(Thanks Jialiang fo

3、r thissuggestion!)We can do this right at the end today.1 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truth“T contains arithmetic”The incompleteness theorems hold for(consistent primitive recursive)theories T that contain arithmetic in the sense th

4、at they are extensionsof PA in the same vocabulary.But they hold for many other theories too.Suppose we require only thatLPA LT,so T talks not only about numbers but perhaps about otherthings too,but it is still required that every LPA-sentence provable in PAis also provable in T.We also need to G o

5、del number the symbols(hence formulas,proofs,etc.)of LT,but it should be clear how to do that.So the requirement will bethat thmPA thmT.Then it is also fairly clear that the arguments for the incompletenesstheorems still work,so that if T is a consistent primitive recursive theorywhich extends PA in

6、 this more general sense,T is incomplete,and ConTis not provable in T.2 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthSet theoryBut there are theories in completely(or partially)different vocabularieswhich also contain PA in a clear sense.A good

7、 example is set theory.In the theory ZF(Zermelo-Fraenckel set theory),the only non-logicalsymbol is (so LZF=),a binary predicate symbol,that intuitivelystands for is an element of.Also intuitively,everything is a set,so x y means the set x is anelement of the set y.The fact that sets are determined

8、by their elements is expressed by theExtensionality Axiom:xy(z(z x z y)x=y)The existence of the empty set is guaranteed byxy y 6 x3 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthZF,cont.The existence of the union of two sets can be expressed byx

9、yzu(u z u x u y)ZF contains axioms like these,and also axiom schemes like the Axiom ofSeparation:for every formula(x)and every set y,there exists the set ofelements in y that satisfy:yzx(x z x y (x)We can introduce terms for the sets that exist by these axioms,such as,x y,x:x y (x),etc.(These defini

10、tions are allowed because,by Extensionality,it follows thatthe empty set,the union of two sets,etc.are unique.)Thus we have the familiar language of informal set theory.4 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthNatural numbers in ZF 1ZFC i

11、s obtained by adding the so-called Axiom of Choice.In ZFC,almost all of current mathematics can be carried out.This holds in particular for arithmetic(here ZF suffices).One candefine the natural numbers,as follows:0:=,1:=0,2:=0,1,.,n:=0,1,.,n 1,.So one starts from,and the operation that gives the ne

12、xt number(thesuccessor)is this:from x to x+=x x.5 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthNatural numbers in ZF 2This allows us to translate the language of PA into the language of ZF.Let ube the translation of an LPA-expression u.Then,in

13、particular:Ix=x(when x is a variable)I0=I(t0)=(t)+=t tOne can also define the translations(s+t)and(s t)using correspondingset-theoretic operations.In this way,all LPA-terms are translated.And forLPA-formulas:I(s=t)is the formula s=tI()=I()=()I(x)=x(N(x)Here N(x)is an LZF-formula which says x is a na

14、tural number(in theset-theoretic sense,as defined from with the successor operation+).6 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthNatural numbers in ZF 3Next,one shows that the translations of all axioms in PA are theorems ofZF,and hence tha

15、t:TheoremIf PA ,then ZF .Now a translation of the proof we gave for PA shows that all primitiverecursive functions are representable by arithmetical formulas in ZF(i.e.formulas where all quantifiers are restricted to N(x).This is enough to prove the Diagonal Lemma(for arithmetical formulas),and then

16、 one can construct a Rosser sentence which is neither provablenor disprovable in ZF(if ZF is consistent),so ZF is incomplete.Likewise,ZF 6 ConZF.The situation with PA and ZF can be generalized.7 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthInte

17、rpretability 1PA is said to be interpretable in a theory T if there is an LT-formula(x),anda primitive recursive function from G odel numbers of LPA-formulas to G odelnumbers of LT-formulas such that,if we writefor the LT-formula whose G odel number is(#(),we have:(i)if PA ,then T ;(ii)preserves log

18、ical constants:()=,()=(),and(x)=x(x).LetPA=:T Claim:PA iffT 8 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthInterpretability 2Thus,(1)PA iffT We conclude(though we need to use a fact from Ch.15.5;see notes):(2)If T is consistent and primitive re

19、cursive,then PAis a consistent andprimitive recursive extension of PA.Theorem(generalized first incompleteness theorem)If PA is interpretable in a consistent prim.rec.theory T,then T is incomplete.9 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truth

20、Goldbach-like sentencesAn property P of numbers is algorithmic if there is a mechanicalprocedure to check if an arbitrary number has that property.For example,the property of being an even number which is the sum oftwo prime numbers is algorithmic.A Goldbach-like sentence says that every number has

21、som algorithmicproperty.Goldbachs conjecture,that every even number 2 is the sum of twoprimes,is a typical Goldbach-like sentence.It is not known if this sentence is true,let alone provable in PA.There are many Goldbach-like sentences in number theory,expressible inLPA.Some are known to be true,othe

22、rs not.10 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthGoldbach-like sentences:examplesGoldbachs conjecture:(1)x(x 2 Even(x)yz(Prime(y)Prime(z)y+z=x)The infinity of prime numbers:(2)x(Prime(x)y(Prime(y)x 0 y 0 z 0 u 2 xu+yu6=zu)This was proved

23、in 1995 by Andrew Wiles using methods far beyond numbertheory.It is not known if it is provable in PA.11 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthConTis Goldbach-likeInterestingly,the undecidable sentences of the incompleteness theoremsare

24、Goldbach-like.Recall:ConT:=xPrfT(x,p0 6=0q)An LPA-formula is bounded if(roughly)it is built from atomic formulasusing only connectives and bounded quantification.One can show:(1)All primitive recursive relations are representable in PA by boundedformulas.So PrfT(x,y)is bounded,which means that ConTi

25、s Goldbach-like.From the point of view of quantificational complexity,ConTis a verysimple sentence.12 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truth1and 1formulasWe say that a formula is 1if it has the formx1.xnwhere is a bounded formula.And it

26、is 1if it has the formx1.xnwhere is bounded.For example,xPrfT(x,pGq),x(PrfT(x,pRq)yyxRefT(x,pRq),ConTare all 1sentences.TheoremAll true 1sentences are provable in PA.So the simplest true but unprovable sentences in PA,like ConT,are 1.We dont know if Goldbachs conjecture is true.But if it is false,it

27、 isprovable in PA!(Since the negation is 1.)13 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthWhat do the incompleteness theorems prove?Bottom line:There is a gap between truth and proof.But:the theorems dont prove that G or ConTare true sentence

28、s,onlythat if T is consistent,then(it follows that)G and ConTare true.So first you have to prove that T is consistent.NB A consistent theory is not necessarily a good theory.Suppose T isconsistent,so T 6 ConT.Then T0=T+ConTis consistent.Then T0 ConT.And T T0,which means that it is easy to show PA Co

29、nT ConT0.Thus,T0 ConT0!14 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthOk,but how can we prove that T is consistent?That depends on T!But start with T=PA:how can we know/prove that PA isconsistent?Dont the incompleteness theorems tell us that w

30、e cannot provethis with the means available in PA;we need a stronger theory,andthen how do we know that that theory is consistent?Its a regress!Let us look at two ways of proving that PA is consistent.15 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and

31、truthSemantic proof that PA is consistentThe informal argument is clear:This reasoning can be carried out in ZFC(in fact in a much weaker settheory):16 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthIs truth a suspicious concept?“What is truth?”C

32、ompare:(a)The sun is shining.(a)It is true that the sun is shining.(b)There are infinitely many primes.(b)It is true that there are infinitely many primes.Does(a)say something more than(a)?Does(b)say more than(b)?Surely a number theorist who has arrived at(b)is allowed toconclude(b),and vice versa.1

33、7 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthTheories of truthBut in the argument for consistency we are quantifying over truth:IEvery axiom of PA is true.INo contradiction is true.Theories of truth is an active research area in logic.They tr

34、y to give a consistent and empirically adequate account of truth,even though truth for all sentences in a language is not definable(Tarskis Theorem).But our present issue is if we can conclude that a theory is consistentfrom the fact that it has a model.The answer seems to be:18 of 23Two thingsStron

35、ger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truthSyntactic proof that PA is consistentAnother argument is proof-theoretic:by carefully analyzing proofs in PAone tries to establish that no proof can end with 0 6=0.This analysis works better for proofs in the ND system.

36、One can assignnumbers to the levels in a proof tree and the individual sentences in it,and do the consistency proof by induction on these numbers.But for this the natural numbers are not enough;one needs induction on(transfinite)ordinal numbers.The proof can be formalized in a theory which has induc

37、tion up to acertain ordinal(which is stronger than induction over natural numbers asin PA),but in other respects is weaker than PA.Still,this theory uses principles that most mathematicians accept.19 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and trut

38、hQuestions(1)Must consistency be established by some special kind of insight?(2)Do the incompleteness theorems give us reasons to doubt theconsistency of e.g.PA?(3)What about the consistency of ZFC?(4)Other questions?20 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truth21 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truth22 of 23Two thingsStronger resultsSet theoryInterpretabilityGoldbach-like sentencesConsistency and truth23 of 23