**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. Gödel Numbers

The Fixed-Point Theorem. Gödel’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**

**Answers to Selected Exercises**

**Bibliography**

**Notation**

**Index**