Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Compactness theorem
Summary
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, 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.
Kurt Gödel proved the countable compactness theorem in 1930. Anatoly Maltsev proved the uncountable case in 1936.
The compactness theorem has many applications in model theory; a few typical results are sketched here.
The compactness theorem implies the following result, stated by Abraham Robinson in his 1949 dissertation.
Robinson's principle: If a first-order sentence holds in every field of characteristic zero, then there exists a constant such that the sentence holds for every field of characteristic larger than 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
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).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (2)
Regularity of solutions for a fourth-order elliptic system via Conservation law
In this paper, we obtain interior Holder continuity for solutions of the fourth-order elliptic system Delta(2)u = Delta(V center dot del u) + div(w del u) + W center dot del u formulated by Lamm and R
2019Existence for a Stationary Model of Binary Alloy Solidification
A proof of existence is given for a stationary model of alloy solidification. The system is composed of heat equation, solute equation and Navier-Stokes equations. In rite latter Carman-Kozeny penaliz
1995Related concepts (41)
Ultrafilter on a set
In the mathematical field of set theory, an ultrafilter on a set is a maximal filter on the set In other words, it is a collection of subsets of that satisfies the definition of a filter on and that is maximal with respect to inclusion, in the sense that there does not exist a strictly larger collection of subsets of that is also a filter. (In the above, by definition a filter on a set does not contain the empty set.) Equivalently, an ultrafilter on the set can also be characterized as a filter on with the property that for every subset of either or its complement belongs to the ultrafilter.
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, hence the theorem's name.
Second-order logic
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies only variables that range over individuals (elements of the domain of discourse); second-order logic, in addition, also quantifies over relations. For example, the second-order sentence says that for every formula P, and every individual x, either Px is true or not(Px) is true (this is the law of excluded middle).
Related courses (4)
MATH-381: Mathematical logic
Branche des mathématiques en lien avec le fondement des mathématiques et l'informatique théorique. Le cours est centré sur la logique du 1er ordre et l'articulation entre syntaxe et sémantique.
MATH-483: Gödel and recursivity
Gödel incompleteness theorems and mathematical foundations of computer science
MATH-318: Set theory
Set Theory as a foundational system for mathematics. ZF, ZFC and ZF with atoms. Relative consistency of the Axiom of Choice, the Continuum Hypothesis, the reals as a countable union of countable sets,