You are currently browsing the tag archive for the ‘Godel completeness theorem’ tag.
Theorem 1 (Gödel completeness theorem, informal statement) Let be a first-order theory (a formal language , together with a set of axioms, i.e. sentences assumed to be true), and let be a sentence in the formal language. Assume also that the language has at most countably many symbols. Then the following are equivalent:
- (i) (Syntactic consequence) can be deduced from the axioms in by a finite number of applications of the laws of deduction in first order logic. (This property is abbreviated as .)
- (ii) (Semantic consequence) Every structure which satisfies or models , also satisfies . (This property is abbreviated as .)
- (iii) (Semantic consequence for at most countable models) Every structure which is at most countable, and which models , also satisfies .
One can also formulate versions of the completeness theorem for languages with uncountably many symbols, but I will not do so here. One can also force other cardinalities on the model by using the Löwenheim-Skolem theorem.
To state this theorem even more informally, any (first-order) result which is true in all models of a theory, must be logically deducible from that theory, and vice versa. (For instance, any result which is true for all groups, must be deducible from the group axioms; any result which is true for all systems obeying Peano arithmetic, must be deducible from the Peano axioms; and so forth.) In fact, it suffices to check countable and finite models only; for instance, any first-order statement which is true for all finite or countable groups, is in fact true for all groups! Informally, a first-order language with only countably many symbols cannot “detect” whether a given structure is countably or uncountably infinite. Thus for instance even the ZFC axioms of set theory must have some at most countable model, even though one can use ZFC to prove the existence of uncountable sets; this is known as Skolem’s paradox. (To resolve the paradox, one needs to carefully distinguish between an object in a set theory being “externally” countable in the structure that models that theory, and being “internally” countable within that theory.)
Of course, a theory may contain undecidable statements – sentences which are neither provable nor disprovable in the theory. By the completeness theorem, this is equivalent to saying that is satisfied by some models of but not by other models. Thus the completeness theorem is compatible with the incompleteness theorem: recursively enumerable theories such as Peano arithmetic are modeled by the natural numbers , but are also modeled by other structures also, and there are sentences satisfied by which are not satisfied by other models of Peano arithmetic, and are thus undecidable within that arithmetic.
An important corollary of the completeness theorem is the compactness theorem:
- (i) is consistent, i.e. it is not possible to logically deduce a contradiction from the axioms in .
- (ii) is satisfiable, i.e. there exists a structure that models .
- (iii) There exists a structure which is at most countable, that models .
- (iv) Every finite subset of is consistent.
- (v) Every finite subset of is satisfiable.
- (vi) Every finite subset of is satisfiable with an at most countable model.
Indeed, the equivalence of (i)-(iii), or (iv)-(vi), follows directly from the completeness theorem, while the equivalence of (i) and (iv) follows from the fact that any logical deduction has finite length and so can involve at most finitely many of the axioms in . (Again, the theorem can be generalised to uncountable languages, but the models become uncountable also.)
There is a consequence of the compactness theorem which more closely resembles the sequential concept of compactness. Given a sequence be a sequence of structures for , and another structure for , let us say that converges elementarily to if every sentence which is satisfied by , is also satisfied by for sufficiently large . (Replacing by its negation , we also see that every sentence that is not satisfied by , is not satisfied by for sufficiently large .) Note that the limit is only unique up to elementary equivalence. Clearly, if each of the models some theory , then the limit will also; thus for instance the elementary limit of a sequence of groups is still a group, the elementary limit of a sequence of rings is still a ring, etc.
Corollary 3 (Sequential compactness theorem) Let be a language with at most countably many symbols, and let be a sequence of structures for . Then there exists a subsequence which converges elementarily to a limit which is at most countable.
Proof: For each structure , let be the theory of that structure, i.e. the set of all sentences that are satisfied by that structure. One can view that theory as a point in , where is the set of all sentences in the language . Since has at most countably many symbols, is at most countable, and so (by the sequential Tychonoff theorem) is sequentially compact in the product topology. (This can also be seen directly by the usual Arzelá-Ascoli diagonalisation argument.) Thus we can find a subsequence which converges in the product topology to a limit theory , thus every sentence in is satisfied by for sufficiently large (and every sentence not in is not satisfied by for sufficiently large ). In particular, any finite subset of is satisfiable, hence consistent; by the compactness theorem, itself is therefore consistent, and has an at most countable model . Also, each of the theories is clearly complete (given any sentence , either or is in the theory), and so is complete as well. One concludes that is the theory of , and hence is the elementary limit of the as claimed.
[It is also possible to state the compactness theorem using the topological notion of compactness, as follows: let be the space of all structures of a given language , quotiented by elementary equivalence. One can define a topology on by taking the sets as a sub-base, where ranges over all sentences. Then the compactness theorem is equivalent to the assertion that is topologically compact.]
One can use the sequential compactness theorem to build a number of interesting “non-standard” models to various theories. For instance, consider the language used by Peano arithmetic (which contains the operations and the successor operation , the relation , and the constant ), and adjoint a new constant to create an expanded language . For each natural number , let be a structure for which consists of the natural numbers (with the usual interpretations of , , etc.) and interprets the symbol as the natural number . By the compactness theorem, some subsequence of must converge elementarily to a new structure of , which still models Peano arithmetic, but now has the additional property that for every (standard) natural number ; thus we have managed to create a non-standard model of Peano arithmetic which contains a non-standardly large number (one which is larger than every standard natural number).
The sequential compactness theorem also lets us construct infinitary limits of various sequences of finitary objects; for instance, one can construct infinite pseudo-finite fields as the elementary limits of sequences of finite fields. I recently discovered that other several correspondence principles between finitary and infinitary objects, such as the Furstenberg correspondence principle between sets of integers and dynamical systems, or the more recent correspondence principles concerning graph limits, can be viewed as special cases of the sequential compactness theorem; it also seems possible to encode much of the sum-product theory in finite fields in an infinitary setting using this theorem. I hope to discuss these points in more detail in a later post. In this post, I wish to review (partly for my own benefit) the proof of the completeness (and hence compactness) theorem. The material here is quite standard (I basically follow the usual proof of Henkin, and taking advantage of Skolemisation), but perhaps the concept of an elementary limit is not as well-known outside of logic as it might be. (The closely related concept of an ultraproduct is better known, and can be used to prove most of the compactness theorem already, thanks to Los’s theorem, but I do not know how to use ultraproducts to ensure that the limiting model is countable. However, one can think (intuitively, at least), of the limit model in the above theorem as being the set of “constructible” elements of an ultraproduct of the .)
In order to emphasise the main ideas in the proof, I will gloss over some of the more technical details in the proofs, relying instead on informal arguments and examples at various points.