Logic and foundations

A book in 20 chapters about reasoning itself: from true and false, truth tables and how to write a proof, to sets and infinity, formal logic, Turing machines and what computers cannot do, and Gödel's theorems on the limits of proof. Each chapter starts from a question, proves what it claims, works examples step by step, and ends with questions whose answers are folded underneath.

How to read it

• In order. Each chapter needs only the ones before it; the Next link at the end of every chapter walks you through.
• Levels inside a chapter. The box at the top of each chapter says which sections are beginner, intermediate, advanced or expert. On a first read, skip the harder sections and come back later.
• Nothing needed to start. Part I needs no algebra at all, only patience with careful words. It is also the best place to learn how to read and write proofs before any other book on this shelf.
• Slower help. The first chapters point to the matching lessons on the Topics shelf ("Logic and puzzles"), which teach the same ideas more gently, for younger readers.
• Honest about the famous results. Gödel's and Turing's theorems are often quoted to mean more than they say. The chapters state exactly what was proved and what was not.

Contents

Part	Chapter	Level
I. Reasoning	1. Statements and truth	beginner
	2. Propositional logic	beginner
	3. Quantifiers	beginner to intermediate
	4. Proofs	beginner to intermediate
II. Sets, relations and functions	5. Sets	intermediate
	6. Relations and functions	intermediate
	7. Infinity and cardinality	intermediate
	8. Axiomatic set theory	advanced
III. Formal logic	9. Proof systems for propositional logic	intermediate to advanced
	10. First-order logic	advanced
	11. Completeness and compactness	advanced
	12. Model theory	advanced to expert
IV. Computation	13. Algorithms and Turing machines	intermediate to advanced
	14. Undecidability	advanced
	15. Recursive functions and computability	advanced
	16. Complexity	advanced
V. Incompleteness and beyond	17. Arithmetic and Peano	advanced
	18. Gödel's incompleteness theorems	expert
	19. Other logics	advanced to expert
	20. Where logic goes	expert

The glossary defines every term, with a link to the chapter that teaches it.

Three ways in

• To think and argue clearly: chapters 1 to 4. They are the logic every other book on this shelf uses.
• For infinity: chapters 5 to 8, Cantor's road from counting to the axioms of set theory.
• For the limits of proof and computation: chapters 13, 14, 17 and 18, going back to Part III when a word is new.