Sets, Logic, Computation: An Open Introduction to Metalogic

Contents
Preface
I. Sets, Relations, Functions
	1. Sets
		1.1 Extensionality
		1.2 Subsets and Power Sets
		1.3 Some Important Sets
		1.4 Unions and Intersections
		1.5 Pairs, Tuples, Cartesian Products
		1.6 Russell's Paradox
		Summary
		Problems
	2. Relations
		2.1 Relations as Sets
		2.2 Special Properties of Relations
		2.3 Equivalence Relations
		2.4 Orders
		2.5 Graphs
		2.6 Operations on Relations
		Summary
		Problems
	3. Functions
		3.1 Basics
		3.2 Kinds of Functions
		3.3 Functions as Relations
		3.4 Inverses of Functions
		3.5 Composition of Functions
		3.6 Partial Functions
		Summary
		Problems
	4. The Size of Sets
		4.1 Introduction
		4.2 Enumerations and Countable Sets
		4.3 Cantor's Zig-Zag Method
		4.4 Pairing Functions and Codes
		4.5 An Alternative Pairing Function
		4.6 Uncountable Sets
		4.7 Reduction
		4.8 Equinumerosity
		4.9 Sets of Different Sizes, and Cantor's Theorem
		4.10 The Notion of Size, and Schröder–Bernstein
		Summary
		Problems
II. First-order Logic
	5. Introduction to First-Order Logic
		5.1 First-Order Logic
		5.2 Syntax
		5.3 Formulas
		5.4 Satisfaction
		5.5 Sentences
		5.6 Semantic Notions
		5.7 Substitution
		5.8 Models and Theories
		5.9 Soundness and Completeness
	6. Syntax of First-Order Logic
		6.1 Introduction
		6.2 First-Order Languages
		6.3 Terms and Formulas
		6.4 Unique Readability
		6.5 Main operator of a Formula
		6.6 Subformulas
		6.7 Formation Sequences
		6.8 Free Variables and Sentences
		6.9 Substitution
		Summary
		Problems
	7. Semantics of First-Order Logic
		7.1 Introduction
		7.2 Structures for First-order Languages
		7.3 Covered Structures for First-order Languages
		7.4 Satisfaction of a Formula in a Structure
		7.5 Variable Assignments
		7.6 Extensionality
		7.7 Semantic Notions
		Summary
		Problems
	8. Theories and Their Models
		8.1 Introduction
		8.2 Expressing Properties of Structures
		8.3 Examples of First-Order Theories
		8.4 Expressing Relations in a Structure
		8.5 The Theory of Sets
		8.6 Expressing the Size of Structures
		Summary
		Problems
	9. Derivation Systems
		9.1 Introduction
		9.2 The Sequent Calculus
		9.3 Natural Deduction
		9.4 Tableaux
		9.5 Axiomatic Derivations
	10. The Sequent Calculus
		10.1 Rules and Derivations
		10.2 Propositional Rules
		10.3 Quantifier Rules
		10.4 Structural Rules
		10.5 Derivations
		10.6 Examples of Derivations
		10.7 Derivations with Quantifiers
		10.8 Proof-Theoretic Notions
		10.9 Derivability and Consistency
		10.10 Derivability and the Propositional Connectives
		10.11 Derivability and the Quantifiers
		10.12 Soundness
		10.13 Derivations with Identity predicate
		10.14 Soundness with Identity predicate
		Summary
		Problems
	11. Natural Deduction
		11.1 Rules and Derivations
		11.2 Propositional Rules
		11.3 Quantifier Rules
		11.4 Derivations
		11.5 Examples of Derivations
		11.6 Derivations with Quantifiers
		11.7 Proof-Theoretic Notions
		11.8 Derivability and Consistency
		11.9 Derivability and the Propositional Connectives
		11.10 Derivability and the Quantifiers
		11.11 Soundness
		11.12 Derivations with Identity predicate
		11.13 Soundness with Identity predicate
		Summary
		Problems
	12. The Completeness Theorem
		12.1 Introduction
		12.2 Outline of the Proof
		12.3 Complete Consistent Sets of Sentences
		12.4 Henkin Expansion
		12.5 Lindenbaum's Lemma
		12.6 Construction of a Model
		12.7 Identity
		12.8 The Completeness Theorem
		12.9 The Compactness Theorem
		12.10 A Direct Proof of the Compactness Theorem
		12.11 The Löwenheim–Skolem Theorem
		Summary
		Problems
	13. Beyond First-order Logic
		13.1 Overview
		13.2 Many-Sorted Logic
		13.3 Second-Order logic
		13.4 Higher-Order logic
		13.5 Intuitionistic Logic
		13.6 Modal Logics
		13.7 Other Logics
III. Turing Machines
	14. Turing Machine Computations
		14.1 Introduction
		14.2 Representing Turing Machines
		14.3 Turing Machines
		14.4 Configurations and Computations
		14.5 Unary Representation of Numbers
		14.6 Halting States
		14.7 Disciplined Machines
		14.8 Combining Turing Machines
		14.9 Variants of Turing Machines
		14.10 The Church-Turing Thesis
		Summary
		Problems
	15. Undecidability
		15.1 Introduction
		15.2 Enumerating Turing Machines
		15.3 Universal Turing Machines
		15.4 The Halting Problem
		15.5 The Decision Problem
		15.6 Representing Turing Machines
		15.7 Verifying the Representation
		15.8 The Decision Problem is Unsolvable
		15.9 Trakthenbrot's Theorem
		Summary
		Problems
A. Proofs
	A.1 Introduction
	A.2 Starting a Proof
	A.3 Using Definitions
	A.4 Inference Patterns
	A.5 An Example
	A.6 Another Example
	A.7 Proof by Contradiction
	A.8 Reading Proofs
	A.9 I Can't Do It!
	A.10 Other Resources
	Problems
B. Induction
	B.1 Introduction
	B.2 Induction on N
	B.3 Strong Induction
	B.4 Inductive Definitions
	B.5 Structural Induction
	B.6 Relations and Functions
	Problems
C. Biographies
	C.1 Georg Cantor
	C.2 Alonzo Church
	C.3 Gerhard Gentzen
	C.4 Kurt Gödel
	C.5 Emmy Noether
	C.6 Bertrand Russell
	C.7 Alfred Tarski
	C.8 Alan Turing
	C.9 Ernst Zermelo
D. The Greek Alphabet
Glossary
Photo Credits
Bibliography
About the Open Logic Project