Toward logic, set theory and model theory

Suppose someone proposes a collection of first-order axioms whose models are exactly the finite structures. For each positive integer $n$, add a sentence saying that at least $n$ distinct objects exist. Any finite portion of the enlarged collection still has a model: choose a sufficiently large finite structure. Compactness would then produce a model satisfying the entire collection, which would have to be both finite and infinite. The contradiction reveals a limitation of first-order axiomatization. Logic studies such limitations by making languages, interpretations, and proofs into mathematical objects in their own right.

Learn a formal language, then study it

For the main route, use Richard Zach's Sets, Logic, Computation. It connects the set-theoretic language needed to discuss formal systems with first-order syntax, semantics, derivations, and the completeness theorem. Work toward Chapter 12, particularly Sections 12.8–12.11 on completeness, compactness, and Löwenheim–Skolem. The opening example becomes a worthwhile destination: reconstruct the argument with an explicit sentence for each lower bound on the size of the domain. Notice that compactness concerns satisfiability of finite subsets of sentences; it is not a claim about compact topological spaces made without further translation.

This book is an introduction to metalogic and expects some prior formal logic. Test that preparation by translating a sentence with alternating quantifiers, negating it correctly, and giving an interpretation in which it is false. You should also be able to distinguish a formula with a free variable from a sentence, and a derivation from a truth-table calculation. Readers who need that practice can start with forall x: Calgary, by P. D. Magnus, Tim Button, Robert Trueman, and Richard Zach. Parts V–VII develop first-order language, interpretations, and natural deduction. Its earlier parts provide a slower entry through arguments and truth-functional logic.

The two books serve different purposes. Use forall x when the immediate difficulty is choosing a quantifier, understanding an interpretation, or applying a deduction rule. Use Sets, Logic, Computation when you can perform those operations and want to prove general facts about them. If ordinary set notation, functions, and relations are already comfortable, sample the opening exercises and skip the corresponding review. Keep structural induction in view: a formula is built recursively, so proofs about every formula often follow its construction. This is a more useful readiness test than knowing a long list of logical symbols.

Keep a small structure beside the definitions

Work on a tiny language throughout the course. Take one binary relation and interpret it as an order on two or three objects. Write a sentence asserting transitivity, construct a counterinterpretation, and compare semantic validity with derivability in the chosen calculus. Later, interpret the same formal language in an infinite structure. Small examples make the distinction between symbols and their meanings tangible, while infinite examples show why metatheorems have consequences beyond mechanical proof checking.

Three different continuations

After completeness, the route divides. Model theory follows the relationship between theories and their structures; compactness is an early working tool, and groups or fields supply useful examples once abstract algebra is available. Computability follows the possibility and limits of algorithms; the later Turing-machine and undecidability material in Zach's text provides a continuation. Set theory asks about axioms governing sets, ordinals, cardinals, and constructions of mathematical universes. The opening naive set theory supports the common language, but further axiomatic set theory requires a separate sustained course. Algebra is helpful for one branch rather than an entrance requirement for all three.

Which completeness theorem?

Two confusions are especially costly. Completeness of first-order logic is different from completeness of a particular theory, and a theorem proved about a formal calculus is different from a theorem proved inside it. Keep separate pages for a system's rules and the mathematical arguments establishing properties of that system. A productive next step is to apply one metatheorem to an unfamiliar example and write out every hypothesis. That turns foundational vocabulary into a usable method.

Suggest an edit · Report a correction

Original introduction: CC BY-SA 4.0.