Model theory

This item has been on the quality assurance side of the portal mathematics entered. This is done in order to bring the quality of the mathematics articles to an acceptable level .

Please help fix the shortcomings in this article and please join the discussion ! ( Enter article )

The model theory is a branch of mathematical logic . The content of model theory is the relationship between the purely formal expressions of a language ( syntactic level ) and their meaning ( semantic level ). This relationship is established through so-called interpretations and a mathematical relationship called the fulfillment relationship .

Generally speaking, model theory deals with the construction and classification of all (possible) structures and classes of structures, in particular with those structures that correspond to axiomatizable languages or theories. It is u. a. the task of constructing models for a given system of axioms - it is often about models with additional properties that cannot be specified in the system of axioms, e.g. B. the cardinality of the model. Furthermore, model theory deals with the equivalence of models , for example the question of whether the same statements apply in them and the question of how many (non-isomorphic) models of an axiom system there are.

Basic concepts of model theory

A model in the sense of model theory is a set with a certain structure (called universe, area of individuals, carrier set or domain) to which a set of statements applies.

The fact that the support set has a structure means that certain relations are defined, i.e. subsets of Cartesian products . The tuple of the universe and the relations is called structure. A structure is called a model of a statement if the statement can be interpreted as a statement about the structure and is fulfilled there. ${\ displaystyle ~ {\ mathcal {U}} ~}$ ${\ displaystyle ~ {\ mathcal {U}} ~}$ ${\ displaystyle ~ {\ mathcal {U}} ^ {k}, ~ k \ in \ mathbb {N}}$ ${\ displaystyle ~ {\ mathcal {U}} ~}$

Example. The simplest structures include graphs . A graph is a tuple with . The universe would be here and the (in this case only) relation would be . In order to interpret a statement like "Julian and Chelsea are friends" in , one could (in this case, since there is no other relation) interpret it as a friendship relation; Julian and Chelsea would have to be identified with individuals from the universe . If then , the statement would be satisfied in the structure and would be a model for the statement. But if it were empty, there would be no way to vote in such a way that they are friends, and the proposition would not be fulfilled in this structure . ${\ displaystyle G}$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle E \ subseteq V ^ {2}}$ ${\ displaystyle V}$ ${\ displaystyle E}$ ${\ displaystyle G}$ ${\ displaystyle E}$ ${\ displaystyle v_ {1}, v_ {2}}$ ${\ displaystyle V}$ ${\ displaystyle (v_ {1}, v_ {2}) \ in E}$ ${\ displaystyle (V, E)}$ ${\ displaystyle G}$ ${\ displaystyle E}$ ${\ displaystyle v_ {1}, v_ {2}}$ ${\ displaystyle G = (V, E)}$

More generally, not just one statement but a set of statements in a language is considered. Model theory deals with the question of which models fulfill each statement of the set or whether the set has a model at all.

The first difficulty is deciding which structures can be used as models for the statements of a language. For this purpose, the concept of the signature was introduced, which seeks to divide every sentence of the language into subject and predicate. Subjects could be proper names (every language speaks about certain objects and sometimes uses proper names for them), variables (pronouns, so to speak, they are not proper names but refer to the objects the language is talking about) or terms (other possible subjects). The basic idea in model theory is,

- variables with zero-digit relations,

- Proper names with single-digit relations that contain only one element,

- Terms with functions (these are left total, right unambiguous relations) and

- Predicates with the other relations

to associate. How general the definitions are made depends on the context: in category theory one tries to proceed very general, in computer science much less general, in mathematics one often restricts oneself to a single language (first level predicate logic). Therefore there are no uniform definitions; for details, please refer to the main entries.

signature

A signature is a tuple consisting of three sets and a function. ${\ displaystyle \ sigma}$ ${\ displaystyle \ sigma = (R, F, K, Ar)}$

${\ displaystyle R}$ is the set of symbols for relations,
${\ displaystyle F}$ is the set of symbols for functions,
${\ displaystyle K}$ is the set of symbols for constants,
${\ displaystyle Ar}$ is a function that assigns an arity to each symbol .

The sets and must be pairwise disjoint, but may be empty. In principle they can also be infinite, but as a rule they are finite. The elements from are called non-logical symbols . ${\ displaystyle R, F}$ ${\ displaystyle K}$ ${\ displaystyle R \ cup F \ cup K}$

structure

Be a signature. A - structure is a tuple consisting of: ${\ displaystyle \ sigma = (R, F, K, Ar)}$ ${\ displaystyle \ sigma}$ ${\ displaystyle {\ mathcal {A}}}$

a non-empty crowd , the universe , ${\ displaystyle ~ {\ mathcal {U}}}$

a k-place relation for each k-place relation symbol ,

{\ displaystyle r \ subseteq {\ mathcal {U}} ^ {k}}

{\ displaystyle R}

a k-digit function for each k-digit function symbol ,

{\ displaystyle f \ subseteq {\ mathcal {U}} ^ {k} \ times U}

{\ displaystyle F}

one element for each constant symbol from K.

{\ displaystyle c \ in {\ mathcal {U}} ^ {1}}

interpretation

Be a language with variables, proper names, terms and predicates. One interpretation of in a structure is an association ${\ displaystyle L}$ ${\ displaystyle w \ in L}$ ${\ displaystyle {\ mathcal {A}}}$

the individual name to the constants of , ${\ displaystyle {\ mathcal {A}}}$
the terms on the functions of , ${\ displaystyle {\ mathcal {A}}}$
of the predicates on the other relations of . ${\ displaystyle {\ mathcal {A}}}$

An assignment is an assignment

of the variables on the universe of . ${\ displaystyle {\ mathcal {A}}}$

An interpretation is therefore possible if the language matches the signature. The interpretation and assignment make a statement about the structure . Mostly the assignment is defined as part of the interpretation. ${\ displaystyle w}$ ${\ displaystyle {\ mathcal {A}}}$

Model and the satisfiability relation

Be any language and a subset of the language. A structure is called a model of if there is an interpretation (with an assignment) such that each element corresponds to a statement that is fulfilled in the structure. Symbolically:, spoken: fulfilled , or also is true in . ${\ displaystyle L}$ ${\ displaystyle T \ subseteq L}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle {\ mathcal {A}} \ models T}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle {\ mathcal {A}}}$

Model theoretical conclusion

In terms of model theory, it is said that a statement follows from a statement if every model of is also a model for . Symbolically . ${\ displaystyle \ phi _ {2}}$ ${\ displaystyle \ phi _ {1}}$ ${\ displaystyle \ phi _ {1}}$ ${\ displaystyle \ phi _ {2}}$ ${\ displaystyle \ phi _ {1} \ models \ phi _ {2}}$

The corollary relation is then extended to any set of statements: In terms of model theory, a set of statements follows from a set of statements if every model of is a model for . Symbolically . ${\ displaystyle \ models}$ ${\ displaystyle \ Phi _ {2}}$ ${\ displaystyle \ Phi _ {1}}$ ${\ displaystyle \ Phi _ {1}}$ ${\ displaystyle \ Phi _ {2}}$ ${\ displaystyle \ Phi _ {1} \ models \ Phi _ {2}}$

The theory of a model is the set of all statements that apply in it. Every theory of a model is complete , that is, there is either or for every statement . ${\ displaystyle T}$ ${\ displaystyle \ varphi}$ ${\ displaystyle \ varphi \ in T}$ ${\ displaystyle \ neg \ varphi \ in T}$

On the importance of models

A set of axioms can often be given more easily as a theory of a model than in an enumerated form.
The existence of a model proves that the axioms are not contradicting each other, so they are consistent. A logic has the property of completeness if, conversely, every consistent set of statements has a model (this applies to first-order predicate logic , see below ).
If there are models with a certain property as well as models that do not have this property, then the logical independence of the property from the axioms is proven. That is, this property does not follow from the axioms and cannot be refuted on the basis of the axioms.
Every sentence of a formal language induces a set of finite models that satisfy it. Every language can thus be viewed as the union of all models which are fulfilled by the sentences of the language. A language is called definable in a logic if there is a proposition of logic that is fulfilled by the same set of models. In descriptive complexity theory , the relationship between the complexity class of a language and its definability in certain logics is examined.

Examples of models

Dense orders

The ordered set of rational numbers is a model for the axioms of the dense open strict total orders :

${\ displaystyle \ forall x, y: (x <y) \ vee (x = y) \ vee (y <x)}$ (Trichotomy)
${\ displaystyle \ forall x, y: [(x <y) \ rightarrow \ neg (y <x)]}$ (Antisymmetry)
${\ displaystyle \ forall x, y, z: [(x <y) \ wedge (y <z) \ rightarrow (x <z)]}$ (Transitivity)
${\ displaystyle \ forall x \ exists y, z: (x <y, z <x)}$ (Openness)
${\ displaystyle \ forall x, y: [x <y \ rightarrow \ exists z: (x <z \ wedge z <y)]}$ (Tightness)

The ordered set of real numbers and all subsets of real numbers that contain the rational numbers are models. The theory of dense open strict total orders is a standard example in model theory. It has the following properties, among others:

It is finitely axiomatizable, but has no finite models.

It is complete and model-complete .

All countable models are isomorphic (for proof ), in uncountable cardinal numbers there are non-isomorphic models. In the language of model theory this means: It is - categorical , but not categorical in uncountable cardinal numbers: If an uncountable cardinal number, then this theory has non-isomorphic models of power . ${\ displaystyle \ omega}$ ${\ displaystyle \ kappa}$ ${\ displaystyle 2 ^ {\ kappa}}$ ${\ displaystyle \ kappa}$

It is the (uniquely determined) model companion of the theory of the linear order.

With the rational numbers it has a prime model . (This is a model that can be fundamentally embedded in any other model.)

Every model is atomic .

It has quantifier elimination .

It is not stable .

One-element universes

The one-element universe, containing only the constant c, is a model for the axiom above the signature . ${\ displaystyle \ forall x: x = c}$ ${\ displaystyle \ sigma = \ {c \}}$

An example of two-element models

How can a model for the following set of statements about look like? ( be a constant, be a two-digit relation) ${\ displaystyle \ sigma = \ {c, R \}}$ ${\ displaystyle c}$ ${\ displaystyle R}$

${\ displaystyle \ forall x, y, z: [(x = y) \ vee (y = z) \ vee (x = z)]}$
${\ displaystyle \ exists x, y: xRy}$
${\ displaystyle \ nexists x: (xRx)}$
${\ displaystyle \ forall x, y: xRy \ rightarrow \ neg (yRx)}$

The first statement determines that the universe contains a maximum of two elements, the second and third statements together only apply if it contains two elements. Apart from isomorphism, there are only two models ( based on the universe ): ${\ displaystyle U = \ {a, b \}}$

${\ displaystyle M_ {1}:}$ ${\ displaystyle U = \ {a, b \},}$ ${\ displaystyle c = a,}$ ${\ displaystyle R = \ {(a, b) \}}$ and

${\ displaystyle M_ {2}:}$ ${\ displaystyle U = \ {a, b \},}$ ${\ displaystyle c = a,}$ ${\ displaystyle R = \ {(b, a) \}}$

The model

${\ displaystyle M_ {3}:}$ ${\ displaystyle U = \ {a, b \},}$ ${\ displaystyle c = b,}$ ${\ displaystyle R = \ {(a, b) \}}$

is isomorphic to . (There is an isomorphism that on maps and on .) ${\ displaystyle M_ {2}}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle a}$

Unsatisfiable axioms

The set of statements

${\ displaystyle \ forall x: xRx}$
${\ displaystyle \ exists x: \ neg xRx}$

cannot be fulfilled, that is, it has no model.

Important sentences of model theory

Criteria for sets of statements of the first-order predicate logic could be found that guarantee the existence of models.

For example, Gödel's theorem of completeness says that every syntactically consistent theory (i.e. every set of closed formulas from which no logical contradiction can be derived) has a model.
The compactness theorem says that an (infinite) axiom system has a model if and only if every finite subsystem has a model.
The Löwenheim-Skolem theorem also states that every theory (in a countable language of predicate logic) that has an infinite model at all also has a model of every infinite cardinality .

Finite model theory

The finite model theory is a portion of the model theory, the logic on the properties of languages (such as predicate logic ), as well as to finite structures such as finite groups, graphs, and most machine models is focused. One focus is particularly on the relationships between logical languages and the theory of computability . There are also close links to discrete mathematics , complexity theory and the theory of databases .

Typical questions in finite model theory are the cardinalities for which models can be created for a given system of axioms . So this question is completely answered for the axioms of the body : Prime numbers and prime number powers are the only cardinalities of finite models. This set of natural numbers is then called the spectrum of body axioms .

It has not yet been clarified whether the complement of a spectrum is always a spectrum again: We are looking for a set of axioms such that all finite models have a cardinality in the complement of the spectrum. This question is also related to the P-NP problem from complexity theory .

On the history of model theory

The origins of model theory can be found in 19th century algebra, as presented in Ernst Schöder's extensive work : Lectures on the Algebra of Logic (1890–1905). Central was the area of the individual (at that time also called the area of thought ) to which an algebraic expression was applied. Schröder also introduced the concept of structure. But the terms remained undefined. This tradition continued even with mathematicians with a logical and axiomatic disposition, such as Ernst Zermelo , who, when axiomatizing set theory, also left the concept of the individual domain without definition, although his axiomatization was based on the concept. Even Albert Thoralf Skolem , who tried to clarify some of the terms Zermelos, used the term without further explanation.

The first attempt at formalization can be found with Rudolf Carnap. But modern model theory deviates from his view on important points. He related models (as was customary at the time) to axiom systems and not to sets of propositions, so that an axiom system already had a model if the axioms of the system are fulfilled. For important reasons this is no longer necessary in the modern conception. Carnap understood by a model for the axiomatic basic signs of a given axiomatic system with respect to a given area of individuals the following: an evaluation for these signs in such a way that both the area and the evaluation are given without the use of descriptive constants. A model for the basic signs is called a model for an axiom system if it satisfies all axioms, i.e. H. makes true. ${\ displaystyle ~ {\ mathcal {U}} ~}$ ${\ displaystyle ~ {\ mathcal {U}} ~}$

The breakthrough to modern understanding came with Alfred Tarski, who separated the semantics of an axiom system from its syntax and gave semantics priority over syntax: a syntactic conclusion is correct if it is semantically fulfilled. Other important milestones are the Herbrand structure by Jacques Herbrand (1930) and the definition of truth by Tarski and Robert Vaught in Arithmetical extensions of relational systems (1956), which removed some of the inaccessibility of Tarski's original definition of truth from the 1930s. The work of Anatoli Malzew was particularly important for applications in algebra, and from 1936 he already included languages with an uncountable number of logical symbols.

literature

CC Chang, HJ Keisler: Model Theory , Studies in Logic and the Foundations of Mathematics, Volume 73, Elsevier Science 1990, ISBN 0-444-88054-2
Wilfrid Hodges : Model Theory , Cambridge University Press 1993. ISBN 0-521-30442-3
Dirk W. Hoffmann : Limits of Mathematics, Springer Spectrum, 3rd edition, Berlin 2018, ISBN 978-3-662-56616-9 . Chapter 7: Model Theory
David Marker: Model Theory: an introduction , Springer Verlag New York 2002, ISBN 9780387987606
Wolfgang Rautenberg : Introduction to mathematical logic , Vieweg Teubner, 3rd edition, Wiesbaden 2008. ISBN 978-3-8348-0578-2 , Chapter 5: Elements of model theory
Philipp Rothmaler: Introduction to Model Theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5
Wolfram Schwabhäuser : Model Theory I BI University Pocket Books Volume 813, Bibliographisches Institut Mannheim 1971

Wolfram Schwabhäuser: Model Theory II BI University Pocket Books Volume 815, Bibliographisches Institut Mannheim 1972

Herbert Stachowiak: General model theory , Springer Verlag, Vienna, New York 1973, ISBN 3-211-81106-0

Web links

Wilfrid Hodges: Model Theory. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
Wilfrid Hodges: First Order Model Theory. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
Jouko Väänänen. A Short Course on Finite Model Theory (PDF; 221 kB). Department of Mathematics, University of Helsinki. Based on lectures from 1993–1994.
William Weiss, Cherie D'Mello: Fundamentals of Model Theory
Model Theory (Stanford Encyclopedia of Philosophy)
Finite Model Theory Homepage of the RWTH Aachen, including a list of open problems.
Finite Model Theory References ( Memento of February 4, 2006 in the Internet Archive ), a database with references to finite model theory.
Model theory in the lexicon of mathematics on Spektrum.de

Individual evidence

^ Carnap, Rudolf: Introduction to symbolic logic. Springer, Vienna, New York, 3rd ed. 1968, p. 174

[1] Carnap, Rudolf: Introduction to symbolic logic. Springer, Vienna, New York, 3rd ed. 1968, p. 174