Compactness theorem

related topics
{math, number, function}

In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful method for constructing models of any set of sentences that is finitely consistent.

The compactness theorem for the propositional calculus is a consequence 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. Likewise, it is analogous to the finite intersection property characterization of compactness in topological spaces: a collection of closed sets in a compact space has a non-empty intersection if every finite subcollection has a non-empty intersection.

The compactness theorem is one of the two key properties, along with the downward Löwenheim–Skolem theorem, that is used in Lindström's theorem to characterize first-order logic. Although there are some generalizations of the compactness theorem to non-first-order logics, the compactness theorem itself does not hold in them.

Contents

Applications

The compactness theorem has many applications in model theory; a few typical results are sketched here.

The compactness theorem implies Robinson's principle: If a first-order sentence holds in 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 a sentence that holds in every field of characteristic zero. Then its negation ¬φ, together with the field axioms and the infinite sequence of sentences 1+1 ≠ 0, 1+1+1 ≠ 0, … , is not satisfiable (because there is no field of characteristic 0 in which ¬φ holds, and the infinite sequence of sentences ensures any model would be a field of characteristic 0). Therefore, there is a finite subset A of these sentences that is not satisfiable. We can assume that A contains ¬φ, the field axioms, and, for some k, the first k sentences of the form 1+1+...+1 ≠ 0 (because adding more sentences doesn't change unsatisfiability). Let B contains all the sentences of A except ¬φ. Then any model of B is a field of characteristic greater than k, and ¬φ together with B is not satisfiable. This means that φ must hold in every model of B, which means precisely that φ holds in every field of characteristic greater than k.

A second application of the compactness theorem shows that any theory that has arbitrarily large finite models, or a single 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'. To achieve this, let T be the initial theory and let κ be any cardinal number. Add to the language of T one constant symbol for every element of κ. Then add to T a collection of sentences that say that the objects denoted by any two distinct constant symbols from the new collection are distinct (this is a collection of κ2 sentences). Since every finite subset of this new theory is satisfiable by a sufficiently large finite model of T, or by any infinite model, the entire extended theory is satisfiable. But any model of the extended theory has cardinality at least κ

Full article ▸

related documents
Integral domain
Bolzano–Weierstrass theorem
Pauli matrices
Union (set theory)
Compact space
Constructible number
Elliptic integral
Chain complex
Perfect number
Arity
Linear search
Procedural programming
Free variables and bound variables
Closure (topology)
Jacobi symbol
Diophantine equation
Sylow theorems
Riesz representation theorem
Stirling's approximation
Octal
Decimal
Cumulative distribution function
Associative algebra
Interpolation search
Hyperbolic function
1 (number)
Gram–Schmidt process
Berry paradox
Legendre polynomials
Depth-first search