A Problem Course of Mathematical Logic v1.6 (1)

《A Problem Course of Mathematical Logic v1.6 (1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AProblemCourseinMathematicalLogicVersion1.6StefanBilaniukDepartmentofMathematicsTrentUniversityPeterborough,OntarioCanadaK9J7B8E-mailaddress:sbilaniuk@trentu.ca1991MathematicsSubjectClassication.03Keywordsandphrases.logic,computability,incompletenessAbstract.Thisisatext

2、foraproblem-orientedcourseonmath-ematicallogicandcomputability.Copyrightc1994-2003StefanBilaniuk.Permissionisgrantedtocopy,distributeand/ormodifythisdoc-umentunderthetermsoftheGNUFreeDocumentationLicense,Version1.2oranylaterversionpublishedbytheFreeSoftwareFoundation;wit

3、hnoInvariantSections,noFront-CoverTexts,andnoBack-CoverTexts.Acopyofthelicenseisincludedinthesec-tionentitledGNUFreeDocumentationLicense".ThisworkwastypesetwithLATEX,usingtheAMS-LATEXandAMSFontspackagesoftheAmericanMathematicalSociety.ContentsPrefacevIntroductionixPartI

4、.PropositionalLogic1Chapter1.Language3Chapter2.TruthAssignments7Chapter3.Deductions11Chapter4.SoundnessandCompleteness15HintsforChapters1{417PartII.First-OrderLogic21Chapter5.Languages23Chapter6.StructuresandModels33Chapter7.Deductions41Chapter8.SoundnessandCompleteness4

5、7Chapter9.ApplicationsofCompactness53HintsforChapters5{959PartIII.Computability65Chapter10.TuringMachines67Chapter11.VariationsandSimulations75Chapter12.ComputableandNon-ComputableFunctions81Chapter13.RecursiveFunctions87Chapter14.CharacterizingComputability95iiiivCONTEN

6、TSHintsforChapters10{14101PartIV.Incompleteness109Chapter15.Preliminaries111Chapter16.CodingFirst-OrderLogic113Chapter17.DeningRecursiveFunctionsInArithmetic117Chapter18.TheIncompletenessTheorem123HintsforChapters15{18127Appendices131AppendixA.ALittleSetTheory133Appendi

7、xB.TheGreekAlphabet135AppendixC.LogicLimericks137AppendixD.GNUFreeDocumentationLicense139Appendix.Bibliography147Appendix.Index149PrefaceThisbookisafreetextintendedtobethebasisforaproblem-orientedcourse(s)inmathematicallogicandcomputabilityforstudentswithsomedegreeofmath

8、ematicalsophistication.PartsIandIIcoverthebasicsofpropositionalandrst-orderlogicrespectively,PartIIIco