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.
Author(s): Lorenz Halbeisen, Regula Krapf
Edition: 1
Publisher: Birkhäuser
Year: 2020
Language: English
Pages: 236
Tags: Mathematical Logic, Set Theory, Models, Incompleteness, Ultraproducts
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
