Finite model theory

Finite model theory is a subarea of <a href="/facts/Model_theory/vLWVV8sQ">model theory</a>. Model theory is the branch of <a href="/facts/Logic/8JnpJLtt">logic</a> which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to <a href="/facts/Interpretation_(logic)/goPmjjQG">interpretations</a> on finite <a href="/facts/Structure_(mathematical_logic)/GsMx1fEb">structures</a>, which have a finite universe.
Since many central theorems of model theory do not hold when restricted to finite structures, finite model theory is quite different from model theory in its methods of proof. Central results of classical model theory that fail for finite structures under finite model theory include the <a href="/facts/Compactness_theorem/8tHVkdeK">compactness theorem</a>, <a href="/facts/G%25C3%25B6del%2527s_completeness_theorem/yq02MUyw">Gödel's completeness theorem</a>, and the method of <a href="/facts/Ultraproduct/d4cT10hd">ultraproducts</a> for <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a> (FO). These invalidities all follow from <a href="/facts/Trakhtenbrot%2527s_theorem/Xjz7VWd4">Trakhtenbrot's theorem</a>.
While model theory has many applications to <a href="/facts/Abstract_algebra/YNNE1CNz">mathematical algebra</a>, finite model theory became an "unusually effective" instrument in computer science. In other words: "In the history of mathematical logic most interest has concentrated on infinite structures. [...] Yet, the objects computers have and hold are always finite. To study computation we need a theory of finite structures." Thus the main application areas of finite model theory are: <a href="/facts/Descriptive_complexity/Ec5F9CnT">descriptive complexity theory</a>, <a href="/facts/Database_theory/unyQa3cK">database theory</a> and <a href="/facts/Formal_language/crDTyP8q">formal language theory</a>.

Finite model theory open-in-new

Finite model theory