003: Logic of Arithmetic: The Logic of Arithmatic Vol 3 (Lectures on Mathematical Logic) - nieuw boek

For propositional logic it can be decided whether a formula has a deduction from a finite set of other formulas. This volume begins with a method to decide this for the quantified formulas of those fragments of arithmetic which express the properties of order-plus-successor and of order-plus-addition (Presburger arithmetic); it makes use of an algorithm eliminating quantifiers which, in turn, is also applied to obtain consistency proofs for these fragments. Stronger fragments of arithmetic, also containing multiplication, are sufficiently rich to express a primitive recursive encoding of terms, formulas and deductions, and this leads to Godel's theorem exhibiting statements already undecidable in these fragments. Its central idea, isolated in Tarski's fixpoint lemma, has a certain analogy with Eubulides' antinomy of the Liar, and in a non-technical chapter, accessible to a wider class of readers, this analogy is exploited for an informal discussion of undefinability and incompleteness. The technical tools required to verify the hypotheses on arithmetical representability, on the other hand, are collected in an independent presentation of recursive functions and relations. For the theory Peano Arithmetic (PA) of full arithmetic with induction it is shown that its extension PR by function symbols for primitive recursive functions is conservative. Thus PR permits us to speak about the encoding of PA itself, and this, essentially, with free variable formulas. This makes it possible to verify the Bernays-Lob provability conditions which entail Godels theorem about the unprovability in PR of the encoded form of statements expressing the consistency of PA.