数理逻辑作业14,15章

《数理逻辑作业14,15章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PartI14.7Proof:(1)(R0)(2)(R1),(1)(3)(R3),(2)(4)(R5),(3)(5)(R6),(4)(6)(R0)(7)(R1),(6)(8)(R3),(7)(9)(R5),(8)(10)(R6),(9)(11)(R4),(5),(10)(12)(R2b),(11)(13)(R2a),(12)(14)(13)14.9Proof:(1)(R0)(2)(R8a),(1)(3)(R2a),(2)(4)(R2a),(3)(5)(R3),(4)(6)(R3),(5)(7)(R2b),(

2、6)(8)(R5),(7)(9)(R5),(8)(10)(R5),(9)(11)(R2a),(10)(12)(11)Q3Proof:Supposethefollowingprerequisitesaretrue:(1)isdeduciblefrom(2)isdeduciblefromThen,PartII15.5Proof:SupposethereexistsuchasetBwithfinitelymany,sentencesB1,B2,...,BmsuchthatTisthesetofconsequenc

3、esofB.∵Bi├Bi,foranyBi∈B∴Bi∈T,foranyBi∈B∵TisalsothesetconsistingofallsentencesprovablefromtheA,whereA={A1,A2,A3,...}∴ThereexistafinitesubsetofDi⊂AsuchthatDi├Bi,foranyBi∈BPicktheAkinalltheDisuchthatthesubscriptkofAkislargestamongtheelementsinalltheDiThenbyru

4、leR1ofsequentcalculus,theset{A1,A2,...,Ak}├Bi,foranyBi∈BButbyassumptionB├Ak+1,whichmeanstheset{A1,A2,...,Ak}├Ak+1bysoundnesstheorem.Wehavederivedacontradiction.Therefore,theoriginalassumptioncannotbesatisfied,thatis,Tisnotfinitelyaxiomatizable.15.7Proof:By

5、definition,asentenceDisfinitelyvalidiff,whereMisaninterpretation.ThereforeasentenceDisnotfinitelyvalidiff,iff.DefinerelationSMD={(M,D)

6、}.ThenthesetRD={D

7、Disnotfinitelyvalid}canbedefineasThecharacteristicfunctionofSMDis.Intuitively,functionciseffectivelycom

8、putable,byChurch’sthesis,cisrecursive.ThereforeSMDisrecursive.Bythedefinitionofsemirecursiveset,thesetRDofsentencesthatarenotfinitelyvalidissemirecursive.15.7Proof:∵Tisanaxiomatizabletheory∴,whereΓisasetofsentencesandDisasentence.∵ifff(a)=b∴ifff(a)=b,iffGa

9、bwhereGisgraphrelationoff.IfGissemirecursive,thenbyfirstgraphprinciple,fisrecursive.Therefore,ourproofisnowequivalenttotheproofoftheproposition:TherelationofnaturalnumbersGabsuchthatisdeduciblefromΓissemirecursive.WecanmimictheproofofCorollary15.6.Wewantto

10、provethatthesetRofrelation(φ,a,b)suchthatφisthecodenumberforaformulaandisdeduciblefromΓissemirecursive.Itimmediatelyfollowsthatforanyonefixed,withcodenumberφ,thesetofrelation(a,b)suchthatisdeduciblefromΓwillb