Sets, Logic, Computation

A textbook on the semantics, proof theory, and metatheory of first-order logic. It covers naive set theory, first-order logic, sequent calculus and natural deduction, the completeness, compactness, and Löwenheim-Skolem theorems, Turing machines, and the undecidability of the halting problem and of first-order logic. It is based on the Open Logic project, and available for free download at slc.openlogicproject.org.

Table of Contents

I Sets, Relations, Functions

1 Sets

2 Relations

3 Functions

4 The Size of Sets

II First-order Logic

6 Syntax of First-Order Logic

7 Semantics of First-Order Logic

8 Theories and Their Models

9 Derivation Systems

10 The Sequent Calculus

11 Natural Deduction

12 The Completeness Theorem

13 Beyond First-order Logic

III Turing Machines

14 Turing Machine Computations

15 Undecidability

About the Author

Richard Zach is Professor of Philosophy at the University of Calgary, Canada. He works in logic, the history of analytic philosophy, and the philosophy of mathematics. In logic, his main interests are non-classical logics and proof theory. He has also written on the development of formal logic and historical figures associated with this development such as Hilbert, Gödel, and Carnap. He has held visiting appointments at the University of California, Irvine, McGill University, and the University of Technology, Vienna.