Sets, Logic, Computation: An Open Introduction to Metalogic

✍ Scribed by Richard Zach

• Year: 2022
• Tongue: English
• Leaves: 431
• Category: Library

✦ Synopsis

"Sets, Logic, Computation is an introductory textbook on metalogic. 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. The audience is undergraduate students with some background in formal logic."

✦ Table of Contents

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