Tag Archive

You are currently browsing the tag archive for the ‘compactness theorem’ tag.

The completeness and compactness theorems of first-order logic

10 April, 2009 in expository, math.LO | Tags: compactness theorem, Godel completeness theorem, Skolemization | by Terence Tao | 35 comments

The famous Gödel completeness theorem in logic (not to be confused with the even more famous Gödel incompleteness theorem) roughly states the following:

Theorem 1 (Gödel completeness theorem, informal statement) Let ${\Gamma}$ be a first-order theory (a formal language ${{\mathcal L}}$ , together with a set of axioms, i.e. sentences assumed to be true), and let ${\phi}$ be a sentence in the formal language. Assume also that the language ${{\mathcal L}}$ has at most countably many symbols. Then the following are equivalent:

(i) (Syntactic consequence) ${\phi}$ can be deduced from the axioms in ${\Gamma}$ by a finite number of applications of the laws of deduction in first order logic. (This property is abbreviated as ${\Gamma \vdash \phi}$ .)

(ii) (Semantic consequence) Every structure ${{\mathfrak U}}$ which satisfies or models ${\Gamma}$ , also satisfies ${\phi}$ . (This property is abbreviated as ${\Gamma \models \phi}$ .)

(iii) (Semantic consequence for at most countable models) Every structure ${{\mathfrak U}}$ which is at most countable, and which models ${\Gamma}$ , also satisfies ${\phi}$ .

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 ${{\mathfrak U}}$ 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 ${\Gamma}$ may contain undecidable statements ${\phi}$ – sentences which are neither provable nor disprovable in the theory. By the completeness theorem, this is equivalent to saying that ${\phi}$ is satisfied by some models of ${\Gamma}$ 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 ${{\mathbb N}}$ , but are also modeled by other structures also, and there are sentences satisfied by ${{\mathbb N}}$ 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:

Corollary 2 (Compactness theorem, informal statement) Let ${\Gamma}$ be a first-order theory whose language has at most countably many symbols. Then the following are equivalent:

(i) ${\Gamma}$ is consistent, i.e. it is not possible to logically deduce a contradiction from the axioms in ${\Gamma}$ .

(ii) ${\Gamma}$ is satisfiable, i.e. there exists a structure ${{\mathfrak U}}$ that models ${\Gamma}$ .

(iii) There exists a structure ${{\mathfrak U}}$ which is at most countable, that models ${\Gamma}$ .

(iv) Every finite subset ${\Gamma'}$ of ${\Gamma}$ is consistent.

(v) Every finite subset ${\Gamma'}$ of ${\Gamma}$ is satisfiable.

(vi) Every finite subset ${\Gamma'}$ of ${\Gamma}$ 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 ${\Gamma}$ . (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 ${{\mathfrak U}_1, {\mathfrak U}_2, \ldots}$ be a sequence of structures for ${{\mathcal L}}$ , and another structure ${{\mathfrak U}}$ for ${{\mathcal L}}$ , let us say that ${{\mathfrak U}_n}$ converges elementarily to ${{\mathfrak U}}$ if every sentence ${\phi}$ which is satisfied by ${{\mathfrak U}}$ , is also satisfied by ${{\mathfrak U}_n}$ for sufficiently large ${n}$ . (Replacing ${\phi}$ by its negation ${\neg \phi}$ , we also see that every sentence that is not satisfied by ${{\mathfrak U}}$ , is not satisfied by ${{\mathfrak U}_n}$ for sufficiently large ${n}$ .) Note that the limit ${{\mathfrak U}}$ is only unique up to elementary equivalence. Clearly, if each of the ${{\mathfrak U}_n}$ models some theory ${\Gamma}$ , then the limit ${{\mathfrak U}}$ 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 ${{\mathcal L}}$ be a language with at most countably many symbols, and let ${{\mathfrak U}_1, {\mathfrak U}_2, \ldots}$ be a sequence of structures for ${{\mathcal L}}$ . Then there exists a subsequence ${{\mathfrak U}_{n_j}}$ which converges elementarily to a limit ${{\mathfrak U}}$ which is at most countable.

Proof: For each structure ${{\mathfrak U}_n}$ , let ${\hbox{Th}({\mathfrak U}_n)}$ 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 ${\{0,1\}^{{\mathcal S}}}$ , where ${{\mathcal S}}$ is the set of all sentences in the language ${{\mathcal L}}$ . Since ${{\mathcal L}}$ has at most countably many symbols, ${{\mathcal S}}$ is at most countable, and so (by the sequential Tychonoff theorem) ${\{0,1\}^{{\mathcal S}}}$ 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 ${\hbox{Th}({\mathfrak U}_{n_j})}$ which converges in the product topology to a limit theory ${\Gamma \in \{0,1\}^{{\mathcal S}}}$ , thus every sentence in ${\Gamma}$ is satisfied by ${{\mathfrak U}_{n_j}}$ for sufficiently large ${j}$ (and every sentence not in ${\Gamma}$ is not satisfied by ${{\mathfrak U}_{n_j}}$ for sufficiently large ${j}$ ). In particular, any finite subset of ${\Gamma}$ is satisfiable, hence consistent; by the compactness theorem, ${\Gamma}$ itself is therefore consistent, and has an at most countable model ${{\mathfrak U}}$ . Also, each of the theories ${\hbox{Th}({\mathfrak U}_{n_j})}$ is clearly complete (given any sentence ${\phi}$ , either ${\phi}$ or ${\neg \phi}$ is in the theory), and so ${\Gamma}$ is complete as well. One concludes that ${\Gamma}$ is the theory of ${{\mathfrak U}}$ , and hence ${{\mathfrak U}}$ is the elementary limit of the ${{\mathfrak U}_{n_j}}$ as claimed. $\Box$

[It is also possible to state the compactness theorem using the topological notion of compactness, as follows: let ${X}$ be the space of all structures of a given language ${{\mathcal L}}$ , quotiented by elementary equivalence. One can define a topology on ${X}$ by taking the sets ${\{ {\mathfrak U} \in X: {\mathfrak U} \models \phi \}}$ as a sub-base, where ${\phi}$ ranges over all sentences. Then the compactness theorem is equivalent to the assertion that ${X}$ 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 ${{\mathcal L}}$ used by Peano arithmetic (which contains the operations ${+, \times}$ and the successor operation ${S}$ , the relation ${=}$ , and the constant ${0}$ ), and adjoint a new constant ${N}$ to create an expanded language ${{\mathcal L} \cup \{N\}}$ . For each natural number ${n \in {\Bbb N}}$ , let ${{\Bbb N}_n}$ be a structure for ${{\mathcal L} \cup \{N\}}$ which consists of the natural numbers ${{\Bbb N}}$ (with the usual interpretations of ${+}$ , ${\times}$ , etc.) and interprets the symbol ${N}$ as the natural number ${n}$ . By the compactness theorem, some subsequence of ${{\Bbb N}_n}$ must converge elementarily to a new structure ${*{\Bbb N}}$ of ${{\mathcal L} \cup \{N\}}$ , which still models Peano arithmetic, but now has the additional property that ${N>n}$ for every (standard) natural number ${n}$ ; 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 ${{\mathfrak U}}$ in the above theorem as being the set of “constructible” elements of an ultraproduct of the ${{\mathfrak U}_n}$ .)

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.

Read the rest of this entry »

	Mauricio Calvao on A mathematical formalisation o…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Bisogna essere un ge… on Ask yourself dumb questions –…
	Bisogna essere un ge… on Enjoy your work
	Bisogna essere un ge… on Be sceptical of your own …
	Bisogna essere un ge… on Be patient
	Bisogna essere un ge… on Attend talks and conferences,…
	Bisogna essere un ge… on Don’t be afraid to learn thing…
	Bisogna essere un ge… on Learn and relearn your fi…
	Bisogna essere un ge… on Work hard
	Sì, però, non è che… on Ask yourself dumb questions –…
	Sara on 245C, Notes 3: Distributi…
	the perfect pointe b… on Career advice
	Terence Tao on A mathematical formalisation o…
	Mauricio Calvao on A mathematical formalisation o…

Tag Archive

The completeness and compactness theorems of first-order logic

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

For commenters

Follow “What's new”