An Introduction to Godel's Theorems

Preface     xiiiWhat Godel's Theorems say     1Basic arithmeticIncompletenessMore incompletenessSome implications?The unprovability of consistencyMore implications?What's next?Decidability and enumerability     8FunctionsEffective decidability, effective computabilityEnumerable setsEffective enumerabilityEffectively enumerating pairs of numbersAxiomatized formal theories     17Formalization as an idealFormalized languagesAxiomatized formal theoriesMore definitionsThe effective enumerability of theoremsNegation-complete theories are decidableCapturing numerical properties     28Three remarks on notationA remark about extensionalityThe language L[subscript A]A quick remark about truthExpressing numerical properties and relationsCapturing numerical properties and relationsExpressing vs. capturing: keeping the distinction clearThe truths of arithmetic     37Sufficiently expressive languagesMore about effectively enumerable setsThe truths of arithmetic are not effectively enumerableIncompletenessSufficiently strong arithmetics     43The idea of a 'sufficiently strong' theoryAn undecidability theoremAnother incompleteness theoremInterlude: Taking stock     47Comparing incompleteness argumentsA road-mapTwo formalized arithmetics     51BA, Baby ArithmeticBA is negation completeQ, RobinsonArithmeticQ is not completeWhy Q is interestingWhat Q can prove     58Systems of logicCapturing less-than-or-equal-to in QAdding '[less than or equal]' to QQ is order-adequateDefining the [Delta subscript 0], [Sigma subscript 1] and [Pi subscript 1] wffsSome easy resultsQ is [Sigma subscript 1]-completeIntriguing corollariesProving Q is order-adequateFirst-order Peano Arithmetic     71Induction and the Induction SchemaInduction and relationsArguing using inductionBeing more generous with inductionSummary overview of PAHoping for completeness?Where we've got toIs PA consistent?Primitive recursive functions     83Introducing the primitive recursive functionsDefining the p.r. functions more carefullyAn aside about extensionalityThe p.r. functions are computableNot all computable numerical functions are p.r.Defining p.r. properties and relationsBuilding more p.r. functions and relationsFurther examplesCapturing p.r. functions     99Capturing a functionTwo more ways of capturing a functionRelating our definitionsThe idea of p.r. adequacyQ is p.r. adequate     106More definitionsQ can capture all [Sigma subscript 1] functionsL[subscript A] can express all p.r. functions: starting the proofThe idea of a [beta]-functionL[subscript A] can express all p.r. functions: finishing the proofThe p.r. functions are [Sigma subscript 1]The adequacy theoremCanonically capturingInterlude: A very little about Principia     118Principia's logicismGodel's impactAnother road-mapThe arithmetization of syntax     124Godel numberingCoding sequencesTerm, Atom, Wff, Sent and Prf are p.r.Some cute notationThe idea of diagonalizationThe concatenation functionProving that Term is p.r.Proving that Atom and Wff are p.r.Proving Prf is p.r.PA is incomplete     138Reminders'G is true if and only if it is unprovable'PA is incomplete: the semantic argument'G is of Goldbach type'Starting the syntactic argument for incompleteness[omega]-incompleteness, [omega]-inconsistencyFinishing the syntactic argument'Godel sentences' and what they sayGodel's First Theorem     147Generalizing the semantic argumentIncompletabilityGeneralizing the syntactic argumentThe First TheoremInterlude: About the First Theorem     153What we've provedThe reach of Godelian incompletenessSome ways to argue that G[subscript T] is trueWhat doesn't follow from incompletenessWhat does follow from incompleteness?Strengthening the First Theorem     162Broadening the scope of the incompleteness theoremsTrue Basic Arithmetic can't be axiomatizedRosser's improvement1-consistency and [Sigma subscript 1]-soundnessThe Diagonalization Lemma     169Provability predicatesAn easy theorem about provability predicatesG and ProvProving that G is equivalent to Prov(G)Deriving the LemmaUsing the Diagonalization Lemma      175The First Theorem againAn aside: 'Godel sentences' againThe Godel-Rosser Theorem againCapturing provability?Tarski's TheoremThe Master ArgumentThe length of proofsSecond-order arithmetics     186Second-order arithmetical languagesThe Induction AxiomNeat arithmeticsIntroducing PA[subscript 2]CategoricityIncompleteness and categoricityAnother arithmeticSpeed-up againInterlude: Incompleteness and Isaacson's conjecture     199Taking stockGoodstein's TheoremIsaacson's conjectureEver upwardsAncestral arithmeticGodel's Second Theorem for PA     212Defining ConThe Formalized First Theorem in PAThe Second Theorem for PAOn [omega]-incompleteness and [omega]-consistency againHow should we interpret the Second Theorem?How interesting is the Second Theorem for PA?Proving the consistency of PAThe derivability conditions     222More notationThe Hilbert-Bernays-Lob derivability conditionsG, Con, and 'Godel sentences'Incompletability and consistency extensionsThe equivalence of fixed points for ProvTheories that 'prove' their own inconsistencyLob's TheoremDeriving the derivability conditions     232Nice theoriesThe second derivability conditionThe third derivability conditionUseful corollariesThe Second Theorem for weaker arithmeticsJeroslow's Lemma and the Second TheoremReflections     240The Second Theorem: the story so farThere are provable consistency sentencesWhat does that show?The reflection schema: some definitionsReflection and PAReflection, more generally'The best and most general version'Another route to accepting a Godel sentence?Interlude: About the Second Theorem     252'Real' vs 'ideal' mathematicsA quick aside: Godel's cautionRelating the real and the idealProving real-soundness?The impact of GodelMinds and computersThe rest of this book: another road-map[Mu]-Recursive functions     265Minimization and [Mu]-recursive functionsAnother definition of [Mu]-recursivenessThe Ackermann-Peter functionThe Ackermann-Peter function is [Mu]-recursiveIntroducing Church's ThesisWhy can't we diagonalize out?Using Church's ThesisUndecidability and incompleteness     277Q is recursively adequateNice theories can only capture recursive functionsSome more definitionsQ and PA are undecidableThe EntscheidungsproblemIncompleteness theorems againNegation-complete theories are recursively decidableRecursively adequate theories are not recursively decidableWhat's next?Turing machines     287The basic conceptionTuring computation defined more carefullySome simple examples'Turing machines' and their 'states'Turing machines and recursiveness     298[Mu]-Recursiveness entails Turing computability[Mu]-Recursiveness entails Turing computability: the detailsTuring computability entails [Mu]-recursivenessGeneralizingHalting problems      305Two simple results about Turing programsThe halting problemThe Entscheidungsproblem againThe halting problem and incompletenessAnother incompleteness argumentKleene's Normal Form TheoremKleene's Theorem entails Godel's First TheoremThe Church-Turing Thesis     315From Euclid to Hilbert1936 and all thatWhat the Church-Turing Thesis is notThe status of the ThesisProving the Thesis?     324The projectVagueness and the idea of computabilityFormal proofs and informal demonstrationsSqueezing argumentsThe first premiss for a squeezing argumentThe other premisses, thanks to Kolmogorov and UspenskiiThe squeezing argument defendedTo summarizeLooking back     342Further reading     344Bibliography     346Index     356

\ From the Publisher"How did Gödel establish the two Theorems of Incompleteness, and why do they matter? Smith (U. of Cambridge) advises readers to take their time in answering these and related questions he poses as he presents a variety of proofs for the First Theorem and shows how to prove the Second. He also examines a group of related results with the same care and attention to detail. In 36 well-paced chapters Smith builds his case from a basic introduction to G<&#58;o>del's theorems on to such issues as the truths of arithmetic, formalized arithmetics, primitive recursive functions, identifying the diagonalization Lemma in the First Theorem and using it, dirivability conditions in the Second Theorem. Turing machines (and recursiveness) and the Church-Turing thesis. Accessible without being dismissive, this is accessible to philosophy students and equally suitable for mathematics students taking a first course in logic." \ Book News\ "... Without doubt, a mandatory reference for every philosopher interested in philosophy of mathematics. The text is, in general, written in a prose style but without avoiding formalisms. It is very accurate in the mathematical arguments and it offers to mathematicians and logicians a detailed approach to Gödel's theorems, covering many aspects which are not easy to find in other presentations."\ Reinhard Kahle, Mathematical Reviews\ \ \