indiscernible sequence?
Morley sequence?
Ramsey theorem?
Erdos-Rado theorem?
Ehrenfeucht-Fraïssé games (back-and-forth games)
Hrushovski construction?
generic predicate?
The compactness theorem is a fundamental result of model theory on the existence of models of first-order theories.
Historically it goes back to work of Gödel and Mal’cev in the 1930s.
Lindström's theorem uses the compactness and the Löwenheim-Skolem theorem to characterize classical first-order logic. The validity or non-validity of the compactness theorem in logical systems other than first-order logic plays under the name of compactness property an important role in abstract model theory.
Briefly, the compactness theorem states that a set of first-order formulas has a model precisely iff every finite subset of has a model.
There are different proofs for the compactness theorem e.g. an entirely ‘semantic’ one using ultraproducts. A particularly transparent one relies on the completeness theorem for first-order logic and the essential finitude of the notion of formal proof1: Suppose has no model, due to completeness this implies that there is a contradiction with but such a deduction of can involve only a finite subset hence and would have no model as well.
Despite the intuitive appeal, this approach obliges one to establish the completeness theorem, which depends on fiddly details of formal proofs and deductive systems to make rigorous.
The motivation for the terminology stems from the observation that the compactness theorem literally expresses the compactness of a suitable topology on first-order structures.
As the compactness theorem is arguably the most fundamental result of model theory, there are too many examples of its use for us to do it much justice here. But perhaps a few examples here will help illustrate some typical uses.
Every set can be totally ordered.
Of course this trivially follows from the stronger result that every set can be well-ordered, if we permit the axiom of choice. But part of our point here is that we don’t need the full strength of the axiom of choice: the result can be derived from the weaker “choice principle” called the ultrafilter theorem, on which the compactness theorem depends.
Introduce a language (i.e., signature) with a constant symbol for each and a binary relation symbol , and for a theory take axioms whenever in and the usual axioms to make a total order (reflexivity, transitivity, antisymmetry, and connectedness). This theory is finitely satisfiable: any finite subset of the axioms has a model, by interpreting each occurring in an inequality axiom belonging to simply as , and totally ordering those finitely many in some way to interpret ; the remaining can be interpreted as the bottom element of that total order without any harm. By the compactness theorem, this theory has a model , and the restriction of the total order on to the set of all constants in is used to totally order all the .
With slightly more effort, a similar argument can be given to show that every partial order can be extended to a total order. We just proved the case where the partial order is discrete.
Again, we assume the ultrafilter principle but do not assume the axiom of choice.
If is surjective and every fiber is finite, then has a section .
Use Proposition to totally order . Each fiber inherits a total order; being finite, it is well-order. Then choose for to be the least element in the fiber (which is nonempty because is surjective).
A countable disjoint union of finite sets is again countable.
Let be the countable family and let be the union; again we have a fibering with fiber over . Using Proposition , totally order ; each inherits an order from , and since total orders on finite sets are well-orders, we have chosen a countable family of well-orders. Now put the lexicographic order on the set of pairs . This is a well-ordering, and clearly the projection is a bijection, so we obtain a well-ordering of by transport of structure (differing, probably, from the original total ordering of which has done its job but is of no further use). Then we can define a partial map by induction: is the bottom of , and is (if it exists) the bottom of the complement of . This defines a bijection from an initial segment of onto , which is what we wanted.
(Weak König’s lemma) Every infinite tree for which there is finite branching at each node has an infinite branch.
A tree is by definition the category of elements of a presheaf where has its usual order and is terminal. A descendant of an element is an element that maps to , i.e., an element with and . A child of is such a descendant with .
By the branching hypothesis, the set of elements is finite. By Proposition , the set of nodes or elements is countable, i.e., is enumerated by some bijection . Then an infinite branch (a global section of ) is given by recursion as follows: is the root (the unique element of ). The root has infinitely many descendants since the tree is infinite. Given that has infinitely many descendants, let be the first of its children in the enumeration that also has infinitely many descendants (such children exist since has only finitely many children by the branching hypothesis).
Weak König’s lemma lends its name to one the so-called Big Five systems of reverse mathematics, namely , and (over a certain weak fragment of second-order arithmetic) is equivalent to many results in classical elementary analysis.
Actually, the WKL as stated above is stronger than another result that goes by that name, namely that an infinite subtree of the infinite binary tree (consisting of finite 0-1 sequences or words, where the root is the empty word and the parent of a nonempty word is obtained by leaving off the last binary digit) has an infinite branch. This is provable in ZF without choice or other choice-free forms of set theory; the key point is that , and subtrees thereof, already have enumerations ready to hand; we don’t need an argument like Proposition to construct one. From there, the recursive construction of a branch in the proof of Corollary can be performed without making choices.
In the German literature the compactness theorem is therefore also called ‘Endlichkeitssatz’. ↩
Last revised on July 26, 2023 at 20:15:41. See the history of this page for a list of all contributions to it.