《FoundationsofLogic (11).pdf》由会员分享，可在线阅读，更多相关《FoundationsofLogic (11).pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、PlanBasic functionsCompositionPrimitive recursionThe-functionOnline Course:Foundations of LogicDag Westerst ahlTsinghua LogicPlanBasic functionsCompositionPrimitive recursionThe-functionPlanToday we will show that all primitive recursive functions aredefinable in PA,from which it follows that all pr
2、imitive recursiverelations are representable in PA.We show:IThe basic functions are definable in PA.IIf f is defined by composition from functions definable in PA,then f is definable in PA.IIf f is defined by primitive recursion from functions definablein PA,then f is definable in PA.Clearly,thats e
3、nough!1 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionDefinable functions give representable relationsRecall that f is definable in PA if there is a formula(x)such thatif f(n)=m,then PA y(n,y)y=m)Now let R be a number-theoretic relation.Recall also that cR(n)=1 ifR(n)holds,and=0
4、otherwise.R is primitive recursive if cRis primitiverecursive.Claim:If cRis definable in PA,then R is representable in PA.2 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionDetailsAgain,the plan is to show:IThe basic functions are definable in PA.IIf f is defined by composition from
5、 functions definable in PA,then f is definable in PA.IIf f is defined by primitive recursion from functions definablein PA,then f is definable in PA.We will not go through all the details(most of them are in thebook),but rather give the idea and the explanation of preciselywhy the result holds.3 of
6、22PlanBasic functionsCompositionPrimitive recursionThe-functionThe basic functions are definable in PAThis is essentially trivial.Lets look at the successor function:s(n)=n+1.4 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionThe class of definable functions is closed under composit
7、ionSuppose f is m-ary,g1,.,gmare n-ary,and h=Cnf,g1,.,gm,i.e.(1)h(n)=f(g1(n),.,gm(n)Also,suppose that f is defined by f(u,y),and giis defined by gi(x,v).We have:(2)h(n)=k iffthere are k1,.,kmsuch that gi(n)=kifori=1,.,m,and f(k1,.,km)=k.To define h in PA,we simply write a formula(x1,.,xn,y)=(x,y)tha
8、t expresses the right-hand side of(2):5 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionThe class of definable functions is closed under primitive recursionSuppose f and g are definable in PA,by formulas fand g,and that his defined by primitive recursion from f and g,i.e.h=Prf,g:(3
9、)?h(n,0)=f(n)h(n,m0)=g(n,m,h(n,m)There is no such construction in PA.The plan is to rewrite the graph ofh as an explicit definition:(pr1)h(n,m)=k there are a0,.,amsuch thata0=f(n)iim(ai+1=g(n,i,ai)am=kWe will try to express the right-hand side of(pr1)with an LPA-formula.6 of 22PlanBasic functionsCom
10、positionPrimitive recursionThe-functionUsing sequence coding(pr1)h(n,m)=k there are a0,.,amsuch thata0=f(n)iim(ai+1=g(n,i,ai)am=kRecall:Isq(n)iffn is a sequence number(the code of a finite sequence).IIf s=hn0,.,nk1i,then(s)i=nifor i=0,.,k1.Thus,letting b=ha0,.,ami:(pr2)h(n,m)=k 7 of 22PlanBasic func
11、tionsCompositionPrimitive recursionThe-functionA problem(pr2)h(n,m)=k there is b such thatsq(b)(b)0=f(n)iim(b)i+1=g(n,i,(b)i)(b)m=kPROBLEM:This presupposes that the sequence coding functions,and in particular exponentiation,are already definable in PA.But thats what we are trying to prove!We need to
12、 code sequences with the functions we have in thelanguage,addition and multiplication,or functions that we knoware definable in PA.8 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionG odels-function 1G odel 1931 found an elegant way to do this.First,we need the following function,(e
13、ssentially)familiar fromelementary school mathematics:rem(n,m)=?the remainder when dividing n by mif m 6=0nif m=0Now consider the following formula:Rem(x,y,u):=(y=0 u=x)(u y wwx(x=w y+u)Then:(1)The formula Rem(x,y,u)defines the function rem in PA.9 of 22PlanBasic functionsCompositionPrimitive recurs
14、ionThe-functionG odels-function 2Rem(x,y,u):=(y=0 u=x)(u y wwx(x=w y+u)In fact,something more holds:FactRem(x,y,u)strongly defines the function rem in PA,in the sense thatnot only do we haveif rem(n,m)=k,then PA u(Rem(n,m,u)u=k),but alsoPA xy=1u Rem(x,y,u)Proof.See Chapter 10.2,and Exercise 10.5.4.1
15、0 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionG odels-function 3Note the big difference between:(a)PA x(x)and(b)for all n,PA (n)We will see that there are cases when we have(b)but not(a).Now consider the function(b,c,i)=rem(b,c(i+1)+1)E.g:It is not hard to see that(2)is(strongl
16、y)defined in PA by the formulaBt(x,y,z,u):=Rem(x,(yz0)0,u)11 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionG odels-function 4G odel showed that can be used to code finite sequences of numbers:Lemma(function lemma)For every sequence a0,.,amof numbers there are numbers b,c suchthat
17、(b,c,i)=aifor i m.The proof uses old facts about divisibility,in particular the ChineseRemainder Theorem;first known statement by Chinese mathematicianSun-tzu in the 3rd century:“There are certain things whose number is unknown.If we count them bythrees,we have two left over;by fives,we have three l
18、eft over;and bysevens,two are left over.How many things are there?”The theorem entails that there is a unique number x satisfyingrem(x,3)=2,rem(x,5)=3,rem(x,7)=2,and 0 x 3 5 7=105.That number is x=23.12 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionCoding finite sequence with the
19、-function(4)For every sequence a0,.,amof numbers there are numbers b,c suchthat(b,c,i)=aifor i m.Recall:(pr1)h(n,m)=k there are a0,.,amsuch thata0=f(n)iim(ai+1=g(n,i,ai)am=kThus:(pr3)h(n,m)=k 13 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionExpressing the definition of h with a f
20、ormula(pr3)h(n,m)=k there are b,c such that(b,c,0)=f(n)iim(b,c,i+1)=g(n,i,(b,c,i)(b,c,m)=kSince the formula Bt(x,y,z,u)(strongly)defines in PA,and we haveformulas fand gthat define f and g in PA,we can express theright-hand side of(pr3)in our language.Small complication:To say,for example,(b,c,0)=f(
21、n)we must write(since we dont have function symbols for and f):14 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionThe defining formula(pr3)h(n,m)=k there are b,c such that(b,c,0)=f(n)iim(b,c,i+1)=g(n,i,(b,c,i)(b,c,m)=kPrimRech(x,x0,y):=uvw(Bt(u,v,0,w)f(x,w)zzx0w0w1(Bt(u,v,z,w0)Bt(u
22、,v,z0,w1)g(x,z,w0,w1)Bt(u,v,x0,y)15 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionThe final lemmaPrimRech(x,x0,y):=uvw(Bt(u,v,0,w)f(x,w)zzx0w0w1(Bt(u,v,z,w0)Bt(u,v,z0,w1)g(x,z,w0,w1)Bt(u,v,x0,y)LemmaIf h=Prf,g,and fand gdefine f and g in PA,thenPrimRechdefines h in PA.16 of 22Pla
23、nBasic functionsCompositionPrimitive recursionThe-functionPart 1:If h(n,m)=k,then PA PrimRech(n,m,k)PrimRech(n,m,k):=uvw(Bt(u,v,0,w)f(n,w)zzmw0w1(Bt(u,v,z,w0)Bt(u,v,z0,w1)g(n,z,w0,w1)Bt(u,v,m,k)17 of 22PlanBasic functionsCompositionPrimitive recursionThe-function18 of 22PlanBasic functionsCompositio
24、nPrimitive recursionThe-functionPart 2:PA =1y PrimRech(n,m,y)See Chapter 10.4.1.19 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionNext Monday:Chapter 11After that,we can finally get back to the incompletenesstheorems!20 of 22PlanBasic functionsCompositionPrimitive recursionThe-functionQuestion time!21 of 22PlanBasic functionsCompositionPrimitive recursionThe-function22 of 22