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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FoundationsofLogic 14 14
限制150内