Compactness theorem

From Wikipedia, the free encyclopedia

In mathematical logic, the compactness theorem states that a (possibly infinite) set of first-order sentences has a model, iff every finite subset of it has a model. There is a generalization of compactness for languages that are of higher order than first-order ones. With respect to theories based on logics that are strictly stronger than first-order logic, compactness is seen to be too strong a property.

The compactness theorem for the propositional calculus is a result of Tychonoff's theorem (which says that the product of compact spaces is compact) applied to compact Stone spaces^[1]; hence the theorem's name.

Contents 1 Applications 2 Proofs 3 See also 4 Notes 5 References 6 Further reading

[edit] Applications

From the theorem it follows for instance that if some first-order sentence holds for every field of characteristic zero, then there exists a constant p such that the sentence holds for every field of characteristic larger than p. This can be seen as follows: suppose φ is the sentence under consideration. Then its negation ¬φ, together with the field axioms and the infinite series of sentences 1+1 ≠ 0, 1+1+1 ≠ 0, … is not satisfiable by assumption. Therefore a finite subset of these sentences is not satisfiable, meaning that φ holds in those fields which have large enough characteristic.

Also, it follows from the theorem that any theory that has an infinite model has models of arbitrary large cardinality (this is the Upward Löwenheim–Skolem theorem). So, for instance, there are nonstandard models of Peano arithmetic with uncountably many 'natural numbers'.

The compactness theorem implies that there are "nonstandard" models of the real numbers, that is, consistent extensions of the theory of the real numbers that contain "infinitesimal" numbers. To see this, let Σ be an axiomatization of the theory of the real numbers. Consider the theory obtained by adding a new constant symbol ε to the language and adjoining to Σ the axiom ε > 0 and the axioms ε < 1/n for all positive integers n. Clearly, the standard real numbers R are a model for every finite subset of these axioms, because the real numbers satisfy everything in Σ and, by suitable choice of ε, can be made to satisfy any finite subset of the axioms about ε. By the compactness theorem, there is a model *R that satisfies Σ and also contains an infinitesimal element ε. A similar argument, adjoining axioms ω > 0, ω > 1, etc., shows that the existence of infinitely large integers cannot be ruled out by any axiomatization Σ of the reals.^[2]

[edit] Proofs

One can prove the compactness theorem using Gödel's completeness theorem, which establishes that a set of sentences is satisfiable if and only if no contradiction can be proven from it. Since proofs are always finite and therefore involve only finitely many of the given sentences, the compactness theorem follows. In fact, the compactness theorem is equivalent to Gödel's completeness theorem, and both are equivalent to the ultrafilter lemma, a weak form of the axiom of choice.^[3]

Gödel originally proved the compactness theorem in just this way, but later some "purely semantic" proofs of the compactness theorem were found, i.e., proofs that refer to truth but not to provability. One of those proofs relies on ultraproducts hinging on the axiom of choice as follows:

Proof: Fix a first-order language L, and let Σ be a collection of L-sentences such that every finite subcollection of L-sentences, i ⊆ Σ of it has a model . Also let be the direct product of the structures and I be the collection of finite subsets of Σ. For each i in I let A_i := { j ∈ I : j ⊇ i}. The family of all these sets A_i generates a filter, so there is an ultrafilter U containing all sets of the form A_i.

Now for any formula φ in Σ we have:

• the set A_{φ} is in U
• whenever j ∈ A_{φ}, then φ ∈ j, hence φ holds in
• the set of all j with the property that φ holds in is a superset of A_{φ}, hence also in U

Using Łoś's theorem we see that φ holds in the ultraproduct . So this ultraproduct satisfies all formulas in Σ.

[edit] See also

• List of Boolean algebra topics
• Löwenheim-Skolem theorem
• Lindström's theorem
• Herbrand's theorem

[edit] Notes

1. ^ See Truss (1997).
2. ^ Goldblatt, Robert (1998). Lectures on the Hyperreals. New York: Springer, 10–11. ISBN 038798464X. 
3. ^ See Hodges (1993), who proves the equivalence of the compactness theorem to the boolean prime ideal theorem.

[edit] References

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computability and Logic, fourth edition, "Cambridge University Press. 
• Chang, C.C.; Keisler, H. Jerome (1989). Model Theory, third edition, Elsevier. ISBN 0-7204-0692-7. 
• Dawson, John W. junior (1993). "The compactness of first-order logic: From Gödel to Lindström". History and Philosophy of Logic 14: 15-37. 
• Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0-521-30442-3. 
• Marker, David (2002). Model Theory: An Introduction, Graduate Texts in Mathematics 217. Springer. ISBN 0-387-98760-6. 
• Truss, John K. (1997). Foundations of Mathematical Analysis. Oxford University Press. ISBN 0198533756. 

[edit] Further reading

• Hummel, Christoph (1997). Gromov's compactness theorem for pseudo-holomorphic curves. Basel, Switzerland: Birkhäuser. ISBN 3-7643-5735-5.