# Compactness theorem

Compactness theorem 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 (but generally not effective) 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, except for a very limited number of examples.[2] Contents 1 History 2 Applications 2.1 Robinson's principle 2.2 Upward Löwenheim–Skolem theorem 2.3 Non-standard analysis 3 Proofs 4 See also 5 Notes 6 References 7 External links History Kurt Gödel proved the countable compactness theorem in 1930. Anatoly Maltsev proved the uncountable case in 1936.[3][4] Applications The compactness theorem has many applications in model theory; a few typical results are sketched here.

Robinson's principle The compactness theorem implies the following result, stated by Abraham Robinson in his 1949 dissertation.

Robinson's principle:[5][6] If a first-order sentence holds in every field of characteristic zero, then there exists a constant {displaystyle p} such that the sentence holds for every field of characteristic larger than {displaystyle p.} This can be seen as follows: suppose {displaystyle varphi } is a sentence that holds in every field of characteristic zero. Then its negation {displaystyle lnot varphi ,} together with the field axioms and the infinite sequence of sentences {displaystyle 1+1neq 0,;;1+1+1neq 0,;ldots } is not satisfiable (because there is no field of characteristic 0 in which {displaystyle lnot varphi } holds, and the infinite sequence of sentences ensures any model would be a field of characteristic 0). Therefore, there is a finite subset {displaystyle A} of these sentences that is not satisfiable. {displaystyle A} must contain {displaystyle lnot varphi } because otherwise it would be satisfiable. Because adding more sentences to {displaystyle A} does not change unsatisfiability, we can assume that {displaystyle A} contains the field axioms and, for some {displaystyle k,} the first {displaystyle k} sentences of the form {displaystyle 1+1+cdots +1neq 0.} Let {displaystyle B} contain all the sentences of {displaystyle A} except {displaystyle lnot varphi .} Then any field with a characteristic greater than {displaystyle k} is a model of {displaystyle B,} and {displaystyle lnot varphi } together with {displaystyle B} is not satisfiable. This means that {displaystyle varphi } must hold in every model of {displaystyle B,} which means precisely that {displaystyle varphi } holds in every field of characteristic greater than {displaystyle k.} This completes the proof.