Gödel's Theorems and Zermelo's Axioms : A Firm Foundation of Mathematics

This book provides a concise and self-contained introduction to the foundations of mathematics. The first part covers the fundamental notions of mathematical logic, including logical axioms, formal proofs and the basics of model theory. Building on this, in the second and third part of the book the authors present detailed proofs of Gödel’s classical completeness and incompleteness theorems. In particular, the book includes a full proof of Gödel’s second incompleteness theorem which states that it is impossible to prove the consistency of arithmetic within its axioms. The final part is dedicated to an introduction into modern axiomatic set theory based on the Zermelo’s axioms, containing a presentation of Gödel’s constructible universe of sets. A recurring theme in the whole book consists of standard and non-standard models of several theories, such as Peano arithmetic, Presburger arithmetic and the real numbers. The book addresses undergraduate mathematics students and is suitable for a one or two semester introductory course into logic and set theory. Each chapter concludes with a list of exercises. Preface Contents Introduction: The Natural Numbers Part I Introduction to First-Order Logic Chapter 1 Syntax: The Grammar of Symbols Alphabet Terms & Formulae Axioms Formal Proofs Tautologies & Logical Equivalence Notes Exercises Chapter 2 The Art of Proof The Deduction Theorem Natural Deduction Methods of Proof The Normal Forms NNF&DNF Substitution of Variables and the Prenex Normal Form Consistency & Compactness Semi-formal Proofs Notes Exercises Chapter 3 Semantics: Making Sense of the Symbols Structures & Interpretations Basic Notions of Model Theory Soundness Theorem Completion of Theories Notes Exercises Part II Gödel's Completeness Theorem Chapter 4 Maximally Consistent Extensions Maximally Consistent Theories Universal List of Sentences Lindenbaum's Lemma Exercises Chapter 5 The Completeness Theorem Extending the Language Extending the Theory The Completeness Theorem for Countable Signatures Some Consequences and Equivalents Notes Exercises Chapter 6 Language Extensions by Definitions Defining new Relation Symbols Defining new Function Symbols Defining new Constant Symbols Notes Exercises Part III Gödel's Incompleteness Theorems Chapter 7 Countable Models of Peano Arithmetic The Standard Model Countable Non-Standard Models Notes Exercises Chapter 8 Arithmetic in Peano Arithmetic Addition & Multiplication The Natural Ordering on Natural Numbers Subtraction & Divisibility Alternative Induction Schemata Relative Primality Revisited Exercises Chapter 9 Gödelisation of Peano Arithmetic Natural Numbers in Peano Arithmetic Gödel's -Function Encoding Finite Sequences Encoding Power Functions Encoding Terms and Formulae Encoding Formal Proofs Notes Exercises Chapter 10 The First Incompleteness Theorem The Provability Predicate The Diagonalisation Lemma The First Incompleteness Theorem Completeness and Incompleteness of Theories of Arithmetic Tarski's Theorem Notes Exercises Chapter 11 The Second Incompleteness Theorem Outline of the Proof Proving the Derivability Condition D2 Löb's Theorem Notes Exercises Chapter 12 CompletenessofPresburgerArithmetic Basic Arithmetic in Presburger Arithmetic Quantifier Elimination Completeness of Presburger Arithmetic Non-standard models of PrA Notes Exercises Part IV The Axiom System ZFC Chapter 13 The Axioms of Set Theory (ZFC) Zermelo's Axiom System (Z) Functions, Relations, and Models Zermelo-Fraenkel Set Theory with Choice (ZFC) Well-Ordered Sets and Ordinal Numbers Ordinal Arithmetic Cardinal Numbers and Cardinal Arithmetic Notes Exercises Chapter 14 Models of Set Theory The Cumulative Hierarchy of Sets Non-Standard Models of ZF Gödel's Incompleteness Theorems for Set Theory Absoluteness Gödel's Constructible Model L LZF LZFC Notes Exercises Chapter 15 Models and Ultraproducts Filters and Ultrafilters Ultraproducts and Ultrapowers Łos's Theorem The Completeness Theorem for Uncountable Signatures The Upward Löwenheim-Skolem Theorem The Downward Löwenheim-Skolem Theorem Notes Exercises Chapter 16 Models of Peano Arithmetic The Standard Model of Peano Arithmetic in ZF A Non-Standard Model of Peano Arithmetic in ZFC Exercises Chapter 17 Models of the Real Numbers A Model of the Real Numbers A Model of the Integers A Model of the Rational Numbers A Model of the Real Numbers using Cauchy Sequences Non-Standard Models of the Reals A Brief Introduction to Non-Standard Analysis Notes Exercises Tautologies References Symbols Persons Subjects