Model theory

Please help to eliminate the shortcomings of this article, and please take part you in the discussion! (Insert item)

The model theory is a branch of mathematical logic. Content of the model theory, the relations between the purely formal expressions of a language ( syntactic level) and their meaning (semantic level). This relationship is established via so-called interpretations and one designated as a satisfaction relation mathematical relation.

Broadly speaking, the model theory is concerned with the construction and classification of all (possible) structures and classes of structures that correspond in particular with those structures that axiomatisierbaren languages ​​or theories. This involves inter alia to the task models to construct for a given axiom system - often it comes to models with additional features, but can not be specified in the axiom system, such as the cardinality of the model. Furthermore, the model theory is concerned with the equivalence of models, such as the question of whether the same statements apply to them, and the question of how many ( non-isomorphic ) models of an axiom system there.

Fundamentals of Model Theory

A model in the sense of model theory is provided with a certain amount of structures ( support amount, the universe, individual domain or domain called ) that meet the axioms of the system.

Under a logical or mathematical model for the axiomatic character of a given axiom system with respect to a given domain of individuals D refers to a review of these characters in such a way that both the domain D and the evaluation without the use of descriptive constants is given. A model for the basic character is called a model of an axiom system if it satisfies all the axioms, ie makes true.

Formal models are structures over the language L in which the axioms are formulated. The language is based on a signature with symbols for constants, relations and functions over the support amount.

The model theory is concerned with what models exist for certain systems of axioms. Conversely, one can ask the question, which statements are true in a model. Under the theory of a model is defined as the set of all statements that pertain to it. Each T a model theory is complete, that is, to either or each statement.

It is said that a statement follows from a statement, if applicable in all models.

On the importance of models

• Models illustrate the nature of an axiom system.
• The investigation of models is simpler than that of interpretations, because the models do not have to do with intentions, but only with extensions.
• Formal models have the following meaning: A axioms can often be easier to specify a theory as a model in a enumerative form.
• Proves the existence of a model that does not contradict the axioms, so they are consistent. A logic has the property of completeness, conversely, if every consistent set of propositions has a model (this applies to the first-order logic, see below).
• If there are both models with a certain property as well as those who do not have this property, so therefore is the logical independence of the property from the axioms proved, that is, this property does not follow from the axioms and can also not be based on the axioms refute.

Examples of models

Density systems

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

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

• Finally, it is axiomatizable, but has no finite models.
• It is complete and model complete.
• All countable models are isomorphic (for evidence ), in uncountable cardinal numbers there are not isomorphic models. In the language of model theory that is: it is - categorical, but not categorical in uncountable cardinals: Is an uncountable cardinal number, so this theory has non- isomorphic models of cardinality.
• It is the (uniquely determined ) model companion of the theory of linear order.
• It has the rational numbers a prime model. (This is a model that can be embedded in any other elementary model. )
• Each model is atomic.
• She has quantifier elimination.
• It is not stable.

Singleton universes

The singleton universe which contains only the constant c, is a model for the axiom on the signature.

An example of two-element models

How can a model for the following set of statements to look over? ( Is a constant, is a binary relation )

The first statement is determined that the universe contains more than two elements, the second and third statement together are valid only if it contains two elements. There are up to isomorphism only two models (where we place the universe is based ):

And

The model

Is isomorphic to. (There is an isomorphism, the maps on and on. )

Nichterfüllbare axioms

The set of propositions

Is not satisfiable, that is, it has no model.

Important sets of model theory

It could be found criteria which guarantee the existence of models.

• So says about the Gödel completeness theorem, that any syntactically consistent theory ( ie any set of closed formulas, from which no logical contradiction is derivable ) has a model.
• The compactness theorem states that an ( infinite ) system of axioms has a model if and only if every finite subsystem has a model.
• The Löwenheim - Skolem says about it in addition, that any theory ( in a countable language of predicate logic ), which even has an infinite model, a model has any cardinality.

Finite Model Theory

The finite model theory is a field of model theory, on the properties of logical languages ​​( such as predicate logic ) and is focused on finite structures such as finite groups, graphs, and most machine models. One focus is in particular in the relations between logic languages ​​and computability theory. Furthermore, there are close relations to discrete mathematics, complexity theory and the theory of databases.

Typical questions in finite model theory, to which cardinalities can be created for a given axiom system models. So the question for the field axioms is fully understood: primes and prime powers are the sole cardinalities of finite models. This set of natural numbers then is called spectrum of the field axioms.

It is not yet clear whether the complement of a spectrum always again is a spectrum: ie a Wanted axioms is 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.