Sets, Logic, Computation: An Open Introduction to Metalogic
Sets, Logic, Computation: An Open Introduction to Metalogic is an open textbook by Richard Zach and the Open Logic Project. It provides an introduction to metalogic—the study of the formal systems used to represent and reason about logic.
The book is designed for undergraduate students who already have some exposure to formal logic. The official project describes it as a textbook covering set theory, first-order logic, proof systems, major metatheorems, Turing machines, and undecidability.
Unlike a typical programming book, this resource focuses on the mathematical and logical foundations that sit underneath computer science, automated reasoning, programming languages, and theoretical computation.
Download the PDF for free: https://slc.openlogicproject.org/
What Is Metalogic?
Logic studies how arguments and reasoning can be represented formally.
Metalogic goes one level higher.
Instead of only asking whether an argument is valid, metalogic asks questions about the logical system itself.
For example:
What makes a logical system consistent?
Can every logically valid statement be formally proved?
What happens when a logical system is given additional assumptions?
Are there problems that no algorithm can solve?
What are the limits of formal reasoning?
These questions connect logic directly with the foundations of computer science.
Sets as a Foundation
The book begins with naive set theory, introducing concepts such as sets, relations, functions, and the ways collections of objects can be studied formally.
Sets are fundamental because many mathematical and computational structures can be represented using them.
For computer science students, this provides a useful foundation for understanding:
Data structures
Relations
Functions
Mathematical models
Formal systems
Computation
The emphasis is not simply on manipulating sets but on understanding how they support later logical reasoning.
Relations and Functions
Relations describe connections between objects, while functions describe structured mappings between collections.
These concepts are important throughout mathematics and computer science.
They appear naturally in:
Databases
Graph theory
Programming languages
Automata theory
Algorithms
Formal verification
Understanding them in a logical setting gives students a stronger foundation for later theoretical topics.
First-Order Logic
One of the major sections of the book introduces first-order logic.
First-order logic provides a formal language for talking about objects, their properties, and relationships between them.
The book explores both the syntax and semantics of first-order logic.
Syntax
Syntax describes how well-formed logical expressions are constructed.
It is concerned with the formal structure of statements.
Semantics
Semantics deals with meaning.
It asks whether a statement is true under a particular interpretation or structure.
Understanding the distinction between syntax and semantics is essential for studying formal logic.
Proof Systems
The book introduces formal proof systems, including natural deduction and sequent calculus.
These systems provide precise rules for constructing mathematical and logical proofs.
Instead of relying only on intuition, students learn how reasoning can be represented as a sequence of formally justified steps.
This is particularly useful for students interested in:
Automated theorem proving
Formal verification
Programming language theory
Mathematical logic
AI reasoning systems
Natural Deduction
Natural deduction attempts to represent logical reasoning in a way that resembles ordinary mathematical argumentation.
Students learn how assumptions can be introduced, manipulated, and eventually discharged through formal inference rules.
This gives learners a structured way to understand how logical conclusions are derived.
Sequent Calculus
Sequent calculus provides another formal approach to proof construction.
It organizes logical reasoning into formal inference rules and provides a different perspective from natural deduction.
Studying multiple proof systems helps students understand that the same logical reasoning can be represented in different formal frameworks.
Completeness
One of the major theoretical topics is the completeness theorem.
At a high level, completeness establishes an important relationship between semantic truth and formal provability in first-order logic.
This is a central result in mathematical logic because it tells us something fundamental about the relationship between what is logically true and what can be formally derived.
Compactness
The book also discusses the compactness theorem.
Compactness provides a powerful way of reasoning about collections of logical statements.
Roughly speaking, it connects properties of an entire collection of statements with properties of its finite subsets.
The theorem has applications throughout mathematical logic and model theory.
Löwenheim-Skolem Theorems
Another advanced topic covered in the book is the Löwenheim-Skolem theorems.
These results reveal surprising facts about the models of first-order theories.
For students, this section demonstrates an important lesson of mathematical logic:
Formal systems can have properties that are very different from what our intuitive interpretation might initially suggest.
Turing Machines
The book then connects logic with computation through Turing machines.
A Turing machine is an abstract model of computation that provides a mathematical way to describe what algorithms can do.
Although extremely simple in structure, Turing machines are powerful enough to represent general computation.
They provide a foundation for studying the limits of algorithms.
Computability
Computability theory asks an important question:
Which problems can actually be solved by an algorithm?
This is different from asking whether a problem is easy or difficult.
A problem may be extremely difficult but still computable.
Other problems may be fundamentally uncomputable, meaning no general algorithm can solve them.
This distinction is one of the most important ideas in theoretical computer science.
The Halting Problem
One of the central topics is the undecidability of the halting problem.
The halting problem asks whether it is possible to create a general algorithm that can examine any program and determine whether that program will eventually stop or continue running forever.
The theory demonstrates that no such universal algorithm exists.
This is a foundational result because it establishes a fundamental limit on computation.
Undecidability of First-Order Logic
The book also discusses the undecidability of first-order logic.
This connects two major areas:
Formal Logic + Computation
It demonstrates that there are limits not only to algorithms but also to what can be mechanically determined within logical systems.
Induction
The appendices include material on induction, including ordinary induction, strong induction, inductive definitions, and structural induction.
Structural induction is particularly relevant to computer science because many computational objects have recursive structures.
For example, recursive data structures and formal expressions can often be analyzed using similar reasoning techniques.
Connection to Computer Science
Although this is a logic textbook, its ideas are deeply connected to computer science.
Algorithms
Computability theory helps explain what algorithms can and cannot accomplish.
Programming Languages
Formal logic is used to describe programming-language syntax and semantics.
Artificial Intelligence
Logic provides foundations for automated reasoning and symbolic AI.
Formal Verification
Proof systems can be used to establish properties of software and hardware.
Theoretical Computer Science
Turing machines, computability, and undecidability are fundamental parts of theoretical CS.
Open and Free Resource
One of the strongest aspects of the book is its open-access nature.
The official Open Logic Project provides the current PDF, and the textbook is licensed under Creative Commons Attribution 4.0 International (CC BY 4.0). The project explicitly states that the current PDF can be downloaded and distributed under the license.
The project also maintains archived versions, including Fall 2025, Fall 2021, Fall 2019, and Fall 2016.
This makes it especially useful for students and instructors looking for a legitimate free textbook.
Companion Logic Tools
The book's material is also supported by Carnap, a free online logic teaching application. The text notes that Carnap can support exercises involving natural deduction, sequent calculus, logical structures, and symbolization.
This adds a practical component to what is otherwise a highly theoretical subject.
Who Should Read This Book?
Sets, Logic, Computation is particularly suitable for:
Computer science students
Mathematics students
Logic students
AI and symbolic reasoning learners
Students studying theoretical computer science
Programming-language researchers
Students interested in computability
Readers who already know basic formal logic
It is not primarily a first introduction to programming. Some background in formal logic is recommended by the authors.
Strengths
1. Strong Theoretical Foundation
The book connects sets, logic, proof systems, and computation into one coherent learning path.
2. Important CS Concepts
Turing machines and undecidability provide a strong foundation for theoretical computer science.
3. Proof-Oriented Learning
Natural deduction and sequent calculus help students develop rigorous reasoning skills.
4. Open Access
The current textbook is freely available under CC BY 4.0.
5. Exercises and Summaries
The book includes chapter summaries, problems, and a glossary, making it more suitable for structured learning.
Limitations
The main limitation is that this is not a lightweight beginner's logic book.
Readers without prior exposure to formal logic may find the transition into metalogic challenging. The official project specifically describes the intended audience as undergraduates who have already taken a first course in formal logic.
It is also much more theoretical than practical programming resources.
Hard Copy: Sets, Logic, Computation: An Open Introduction to Metalogic (Open Logic Project Textbooks) (Free PDF)
Download the PDF for free: https://slc.openlogicproject.org/
Final Verdict
Sets, Logic, Computation: An Open Introduction to Metalogic is a valuable resource for anyone interested in the mathematical foundations of computer science.
Its progression from sets and relations → first-order logic → proof systems → completeness and compactness → Turing machines → computability and undecidability creates a strong connection between mathematical logic and theoretical computation.
For students interested in AI, algorithms, programming languages, formal verification, or theoretical computer science, the book provides a deeper understanding of the logical foundations behind these fields.
