FoundationsofLogic (14).pdf

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 posted 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 for 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 that 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 odel 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 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 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 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 byxyzu(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 definitions 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 is 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 next 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 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 natural 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 that: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 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 truthInterpretability 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 logical 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 recursive,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 truthGoldbach-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 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,others 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 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 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 ConTis 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 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 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 sentences,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 ConT 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 we 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 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?”Compare:(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.17 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 try 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 thingsStronger 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.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 induction 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 truthQuestions(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