Introduction to Mathematical Logic (Hardcover, 6)

Preface

Introduction

The Propositional Calculus
Propositional Connectives: Truth Tables
Tautologies
Adequate Sets of Connectives
An Axiom System for the Propositional Calculus
Independence: Many-Valued Logics
Other Axiomatizations

First-Order Logic and Model Theory
Quantifiers
First-Order Languages and Their Interpretations: Satisfiability and Truth Models
First-Order Theories
Properties of First-Order Theories
Additional Metatheorems and Derived Rules
Rule C
Completeness Theorems
First-Order Theories with Equality
Definitions of New Function Letters and Individual Constants
Prenex Normal Forms
Isomorphism of Interpretations: Categoricity of Theories
Generalized First-Order Theories: Completeness and Decidability
Elementary Equivalence: Elementary Extensions
Ultrapowers: Nonstandard Analysis
Semantic Trees
Quantification Theory Allowing Empty Domains

Formal Number Theory
An Axiom System
Number-Theoretic Functions and Relations
Primitive Recursive and Recursive Functions
Arithmetization: Godel Numbers
The Fixed-Point Theorem: Godel’s Incompleteness Theorem
Recursive Undecidability: Church’s Theorem
Nonstandard Models

Axiomatic Set Theory
An Axiom System
Ordinal Numbers
Equinumerosity: Finite and Denumerable Sets
Hartogs’ Theorem: Initial Ordinals?Ordinal Arithmetic
The Axiom of Choice: The Axiom of Regularity
Other Axiomatizations of Set Theory

Computability
Algorithms: Turing Machines
Diagrams
Partial Recursive Functions: Unsolvable Problems
The Kleene?Mostowski Hierarchy: Recursively Enumerable Sets
Other Notions of Computability
Decision Problems

Appendix A: Second-Order Logic

Appendix B: First Steps in Modal Propositional Logic

Appendix C: A Consistency Proof for Formal Number Theory

Answers to Selected Exercises

Bibliography

Notations

Index