Model theory - Citizendia

This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model. Note The term model has a different meaning in Model theory, a branch of Mathematical logic.

In mathematics, model theory is the study of (classes of) mathematical structures such as groups, fields, graphs or even models of set theory using tools from mathematical logic. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Universal algebra and in Model theory, a structure consists of an underlying set along with a collection of Finitary functions and relations In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics and Computer science, a graph is the basic object of study in Graph theory. Mathematical logic is a subfield of Logic and Mathematics with close connections to Computer science and Philosophical logic. Model theory has close ties to algebra and universal algebra. Algebra is a branch of Mathematics concerning the study of structure, relation, and Quantity. Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models"

This article focuses on finitary first order model theory of infinite structures. First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science The model theoretic study of finite structures (for which see finite model theory) diverges significantly from the study of infinite structures in both the problems studied and the techniques used. Finite model theory is a subfield of Model theory that focuses on properties of logical languages such as First-order logic, over finite structures such as Model theory in higher-order logics or infinitary logics is hampered by the fact that completeness does not in general hold for these logics. In Mathematics, higher-order logic is distinguished from First-order logic in a number of ways Those unfamiliar with Mathematical logic or the concept of Ordinals are advised to consult those articles first Gödel's completeness theorem is a fundamental theorem in Mathematical logic that establishes a correspondence between semantic truth and syntactic provability in However, a great deal of study has also been done in such languages.

The role of model theory

Model theory recognises and is intimately concerned with a duality: It examines semantical elements by means of syntactical elements of a corresponding language. Semantics is the study of meaning in communication The word derives from Greek σημαντικός ( semantikos) "significant" from In Linguistics, syntax (from Ancient Greek grc συν- syn-, "together" and grc τάξις táxis, "arrangement" is the To quote the first page of Chang and Keisler (1990):

universal algebra + logic = model theory. H Jerome Keisler is an American Mathematician, currently professor emeritus at University of Wisconsin-Madison. Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models" Logic is the study of the principles of valid demonstration and Inference.

In a similar way as proof theory, model theory is situated in an area of interdisciplinarity between mathematics, philosophy, and computer science. Proof theory is a branch of Mathematical logic that represents proofs as formal Mathematical objects facilitating their analysis by mathematical techniques In Academia, Pedagogy, Physical sciences, Earth sciences, Human sciences and Social sciences Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Philosophy is the study of general problems concerning matters such as existence knowledge truth beauty justice validity mind and language Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their The most important professional organization in the field of model theory is the Association for Symbolic Logic. The Association for Symbolic Logic ("ASL" is an International organization of specialists in Mathematical logic and Philosophical logic —the

The areas of model theory

An incomplete and somewhat arbitrary subdivision of model theory is into classical model theory, model theory applied to groups and fields, and geometric model theory. A missing subdivision is computable model theory, but this can arguably be viewed as an independent subfield of logic. Computable model theory is a branch of Model theory which deals with questions of Computability as they apply to model-theoretical structures Examples of early theorems from classical model theory include Gödel's completeness theorem, the upward and downward Löwenheim–Skolem theorems, Vaught's two cardinal theorem, Scott's isomorphism theorem, the omitting types theorem, and the Ryll-Nardzewski theorem. Gödel's completeness theorem is a fundamental theorem in Mathematical logic that establishes a correspondence between semantic truth and syntactic provability in In Mathematical logic, the Löwenheim–Skolem theorem states that if a countable first-order theory has an infinite model then for every infinite Cardinal number In Functional analysis, the Ryll-Nardzewski fixed point theorem states that if E is a Normed vector space and K is a nonempty convex Examples of early results from model theory applied to fields are Tarski's elimination of quantifiers for real closed fields, Ax's theorem on pseudo-finite fields, and Robinson's development of nonstandard analysis. In Mathematics, a real closed field is a field F in which any of the following equivalent conditions are true There is a Total order An important step in the evolution of classical model theory occurred with the birth of stability theory (through Morley's theorem on totally categorical theories and Shelah's classification program), which developed a calculus of independence and rank based on syntactical conditions satisfied by theories. In Model theory, a branch of Mathematical logic, a theory is &kappa- categorical (or categorical in &kappa) if it has exactly one model of During the last several decades applied model theory has repeatedly merged with the more pure stability theory. The result of this synthesis is called geometric model theory in this article (which is taken to include o-minimality, for example, as well as classical geometric stability theory). An example of a theorem from geometric model theory is Hrushovski's proof of the Mordell-Lang conjecture for function fields. This is a glossary of arithmetic and Diophantine geometry in Mathematics, areas growing out of the traditional study of Diophantine equations to encompass large parts The ambition of geometric model theory is to provide a geography of mathematics by embarking on a detailed study of definable sets in various mathematical structures, aided by the substantial tools developed in the study of pure model theory.

Universal algebra

Main article: universal algebra

Fundamental concepts in universal algebra are signatures σ and σ-algebras. Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models" In Logic, especially Mathematical logic, a signature lists and describes the Non-logical symbols of a Formal language. Since these concepts are formally defined in the article on structures, the present article can content itself with an informal introduction which consists in examples of how these terms are used. In Universal algebra and in Model theory, a structure consists of an underlying set along with a collection of Finitary functions and relations

The standard signature of rings is σ_ring = {×,+,−,0,1}, where × and + are binary, − is unary, and 0 and 1 are nullary.

The standard signature of (multiplicative) groups is σ_grp = {×,⁻¹,1}, where × is binary, ⁻¹ is unary and 1 is nullary.

The standard signature of monoids is σ_mnd = {×,1}.

A ring is a σ_ring-structure which satisfies the identities u + (v+w) = (u+v) + w, u+0 = u, 0+u=u, u+(-u)=0, (-u)+u=0, u × (v×w) = (u×v) × w, u×1 = u, 1×u =u, u × (v+w) = (u×v) + (u×w) and (v+w) × u = (v × u) + (w × u). In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real

A group is a σ_grp-structure which satisfies the identities u×(v×w)=(u×v)×w, u×1=u, 1×u=u, u×u⁻¹=1 and u⁻¹×u=1. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, the term identity has several different important meanings An identity is an equality that remains true regardless of the values of

A monoid is a σ_mnd-structure which satisfies the identities u×(v×w)=(u×v)×w, u×1 = u and 1×u =u. In Abstract algebra, a branch of Mathematics, a monoid is an Algebraic structure with a single Associative Binary operation

A semigroup is a σ_mnd-structure which satisfies the identity u×(v×w)=(u×v)×w. In Mathematics, a semigroup is an Algebraic structure consisting of a nonempty set S together with an Associative Binary operation

A magma is just a {×}-structure. In Abstract algebra, a magma (or groupoid) is a basic kind of Algebraic structure.

This is a very efficient way to define most classes of algebraic structures, because there is also the concept of σ-homomorphism, which correctly specializes to the usual notions of homomorphism for groups, semigroups, magmas and rings. In Algebra, a branch of Pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, In Universal algebra and in Model theory, a structure consists of an underlying set along with a collection of Finitary functions and relations For this to work, the signature must be chosen well.

Using σ-congruences (equivalence relations that respect the operations of σ), which play the role of kernels of homomorphisms, universal algebra can state and prove the isomorphism theorems in great generality:

For every homomorphism h: A → B, Im(A) is isomorphic to A/ker(h). In Mathematics, the isomorphism theorems are three Theorems applied widely in the realm of Universal algebra, stating the existence of certain Natural

If $\delta\subseteq\epsilon$ are two congruence relations on A, then (A/δ) / (ε/δ) is isomorphic to A/ε.

Terms such as the σ_ring-term t=t(u,v,w) given by (u + (v×w)) − 1 are used to define identities t=t', but also to construct free algebras. An equational class is a class of structures which, like the examples above and many others, is defined as the class of all σ-structures which satisfy a certain set of identities. In Universal algebra, a variety of algebras is the class of all Algebraic structures of a given signature satisfying a given set of identities

An important non-trivial tool in universal algebra are ultraproducts $\Pi_{i\in I}A_i/U$ , where I is an infinite set indexing a system of σ-structures A_i, and U is an ultrafilter on I. An ultraproduct is a mathematical construction of which the ultrapower (defined below is a special case In the mathematical field of Set theory, an ultrafilter on a set X is a collection of Subsets of X that is a filter, that They are used in the proof of Birkhoff's theorem:

A class of σ-structures is an equational class iff it is not empty and closed under subalgebras, homomorphic images, and direct products. ↔

While model theory is generally considered a part of mathematical logic, universal algebra, which grew out of Alfred North Whitehead's (1898) work on abstract algebra, is part of algebra. Mathematical logic is a subfield of Logic and Mathematics with close connections to Computer science and Philosophical logic. Alfred North Whitehead, OM ( February 15 1861, Ramsgate, Kent, England &ndash December 30 1947, Abstract algebra is the subject area of Mathematics that studies Algebraic structures such as groups, rings, fields, modules Algebra is a branch of Mathematics concerning the study of structure, relation, and Quantity. This is reflected by their respective MSC classifications. The Mathematics Subject Classification (MSC is an alphanumerical Classification scheme formulated by the American Mathematical Society based on the coverage of two Nevertheless model theory can be seen as an extension of universal algebra.

Finite model theory

Main article: finite model theory

Finite model theory is the area of model theory which has the closest ties to universal algebra. Finite model theory is a subfield of Model theory that focuses on properties of logical languages such as First-order logic, over finite structures such as Like some parts of universal algebra, and in contrast with the other areas of model theory, it is mainly concerned with finite algebras, or more generally, with finite σ-structures for signatures σ which may contain relation symbols as in the following example:

The standard signature for graphs is σ_grph={E}, where E is a binary relation symbol. In Universal algebra and in Model theory, a structure consists of an underlying set along with a collection of Finitary functions and relations

A graph is a σ_grph-structure satisfying the sentences $\forall u \forall v(uEv \rightarrow vEu)$ and $\forall u\neg(uEu)$ .

A σ-homomorphism is a map that commutes with the operations and preserves the relations in σ. This definition gives rise to the usual notion of graph homomorphism, which has the interesting property that a bijective homomorphism need not be invertible. In the mathematical field of Graph theory a graph homomorphism is a mapping between two graphs that respects their structure Structures are also a part of universal algebra; after all, some algebraic structures such as ordered groups have a binary relation <. In Algebra, a branch of Pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, What distinguishes finite model theory from universal algebra is its use of more general logical sentences (as in the example above) in place of identities. (In a model-theoretic context an identity t=t' is written as a sentence $\forall u_1u_2\dots u_n(t=t')$ . )

The logics employed in finite model theory are often substantially more expressive than first-order logic, the standard logic for model theory of infinite structures.

First-order logic

Main article: first-order logic

Whereas universal algebra provides the semantics for a signature, logic provides the syntax. First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science Semantics is the study of meaning in communication The word derives from Greek σημαντικός ( semantikos) "significant" from In Logic, especially Mathematical logic, a signature lists and describes the Non-logical symbols of a Formal language. Mathematical logic is a subfield of Logic and Mathematics with close connections to Computer science and Philosophical logic. In Linguistics, syntax (from Ancient Greek grc συν- syn-, "together" and grc τάξις táxis, "arrangement" is the With terms, identities and quasi-identities, even universal algebra has some limited syntactic tools; first-order logic is the result of making quantification explicit and adding negation into the picture. In Universal algebra, a quasiidentity is an implication of the form s 1 = t 1 ∧ … ∧ s n

A first-order formula is built out of atomic formulas such as R(f(x,y),z) or y = x + 1 by means of the Boolean connectives $\neg,\land,\lor,\rightarrow$ and prefixing of quantifiers $\forall v$ or $\exists v$ . In Mathematical logic, an atomic formula (also known simply as an atom) is a formula with no deeper Propositional structure that is a formula Logical connectiveIn Logic, a set of symbols is commonly used to express logical representation A sentence is a formula in which each occurrence of a variable is in the scope of a corresponding quantifier. Examples for formulas are φ (or φ(x) to mark the fact that at most x is an unbound variable in φ) and ψ defined as follows:

$\phi \;=\; \forall u\forall v(\exists w (x\times w=u\times v)\rightarrow(\exists w(x\times w=u)\lor\exists w(x\times w=v)))$

$\psi \;=\; \forall u\forall v((u\times v=x)\rightarrow (u=x)\lor(v=x)).$

(Note that the equality symbol has a double meaning here. ) It is intuitively clear how to translate such formulas into mathematical meaning. In the σ_ring-structure $\mathcal N$ of the natural numbers, for example, an element n satisfies the formula φ iff it n a prime number. ↔ The formula ψ similarly defines irreducibility. Tarski gave a rigorous definition, sometimes called "Tarski's definition of truth", for the satisfaction relation $\models$ , so that one easily proves:

$\mathcal N\models\phi(n) \iff n$ is a prime number. The T-schema (also known as Convention T) is the Inductive definition that lies at the heart of any realisation of Alfred Tarski 's Semantic theory

$\mathcal N\models\psi(n) \iff n$ is irreducible.

A set T of sentences is called a (first-order) theory. In Mathematical logic, a theory is a set of sentences in a Formal language. A theory is satisfiable if it has a model $\mathcal M\models T$ , i. e. a structure (of the appropriate signature) which satisfies all the sentences in the set T. Consistency of a theory is usually defined in a syntactical way, but in first-order logic by the completeness theorem there is no need to distinguish between satisfiability and consistency. Gödel's completeness theorem is a fundamental theorem in Mathematical logic that establishes a correspondence between semantic truth and syntactic provability in Therefore model theorists often use "consistent" as a synonym for "satisfiable".

A theory is called categorical if it determines a structure up to isomorphism, but it turns out that this definition is not useful, due to serious restrictions in the expressivity of first-order logic. The Löwenheim-Skolem theorem implies that for every theory T^[1] which has an infinite model and for every infinite cardinal number κ, there is a model $\mathcal M\models T$ such that the number of elements of $\mathcal M$ is exactly κ. In Mathematical logic, the Löwenheim–Skolem theorem states that if a countable first-order theory has an infinite model then for every infinite Cardinal number This article describes cardinal numbers in mathematics For cardinals in linguistics see Names of numbers in English. Therefore only finite structures can be described by a categorical theory.

Lack of expressivity (when compared to higher logics such as second-order logic) has its advantages, though. In Logic and Mathematics second-order logic is an extension of First-order logic, which itself is an extension of Propositional logic. For model theorists the Löwenheim-Skolem theorem is an important practical tool rather than the source of Skolem's paradox. Skolem's paradox is the mathematical fact that every countable Axiomatisation of Set theory in First-order logic, if Consistent, has First-order logic is in some sense the most expressive logic for which both the Löwenheim-Skolem theorem and the compactness theorem hold:

Compactness theorem

Every inconsistent first-order theory has a finite inconsistent subset. In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every

This important theorem, due to Gödel, is of central importance in infinite model theory, where the words "by compactness" are commonplace. Kurt Gödel (kʊɐ̯t ˈgøːdl̩ (April 28 1906 – January 14 1978 was an Austrian American Logician, Mathematician and Philosopher One way to prove it is by means of ultraproducts. An ultraproduct is a mathematical construction of which the ultrapower (defined below is a special case

An important question when one wants to apply model theory to a specific class of structures is whether this class is an elementary class, i. In the branch of Mathematical logic called Model theory, an elementary class (or axiomatizable class) is a class consisting of all e. whether its members can be characterized as those structures which satisfy a first-order theory.

Axiomatizability, elimination of quantifiers, and model-completeness

The first step, often trivial, for applying the methods of model theory to a class of mathematical objects such as groups, or trees in the sense of graph theory, is to choose a signature σ and represent the objects as σ-structures. The next step is to show that the class is axiomatizable, i. e. there is a theory T such that a σ-structure is in the class if and only if it satisfies T. (This step fails for the trees, since connectedness cannot be expressed in first order. ) Axiomatizability ensures that model theory can speak about the right objects. Quantifier elimination can be seen as a condition which ensures that model theory does not say too much about the objects.

A theory T has quantifier elimination if every first-order formula φ(x₁,. . . ,x_n) over its signature is equivalent modulo T to a first-order formula ψ(x₁,. . . ,x_n) without quantifiers, i. e. $\forall x_1\dots\forall x_n(\phi(x_1,\dots,x_n)\leftrightarrow \psi(x_1,\dots,x_n))$ holds in all models of T. For example the theory of algebraically closed fields in the signature σ_ring=(×,+,−,0,1) has quantifier elimination because every formula is equivalent to a Boolean combination of equations between polynomials.

A substructure of a σ-structure is a subset of its domain, closed under all functions in its signature σ, which is regarded as a σ-structure by restricting all functions and relations in σ to the subset. An embedding of a σ-structure $\mathcal A$ into another σ-structure $\mathcal B$ is a map f: A → B between the domains which can be written as an isomorphism of $\mathcal A$ with a substructure of $\mathcal B$ . Every embedding is an injective homomorphism, but the converse holds only if the signature contains no relation symbols.

If T has quantifier elimination, then every substructure of a model of T again satisfies T, and in fact something stronger holds: For every formula φ(x₁,. . . ,x_n) and every tuple a₁,. . . ,a_n in the substructure, φ(a₁,. . . ,a_n) is true in the substructure if and only if it is true in the bigger structure. A substructure with this property is called an elementary substructure.

If a theory does not have quantifier elimination, one can add additional symbols to its signature so that it does. Early model theory spent much effort on proving axiomatizability and quantifier elimination results for specific theories, especially in algebra. But often instead of quantifier elimination a weaker property suffices:

A theory T is called model-complete if every substructure of a model of T which is itself a model of T is an elementary substructure. There is a useful criterion for testing whether a substructure is an elementary substructure, called the Tarski-Vaught test. The Tarski-Vaught test (sometimes called Tarski's criterion) is a result in Model theory which characterizes the Elementary substructures of a given It follows from this criterion that a theory T is model-complete if and only if every first-order formula φ(x₁,. . . ,x_n) over its signature is equivalent modulo T to an existential first-order formula, i. e. a formula of the following form:

$\forall v_1\dots\forall v_m\psi(x_1,\dots,x_n,v_1,\dots,v_m)$ ,

where ψ is quantifier free.

Model theory and set theory

Set theory (which is expressed in a countable language) has a countable model; this is known as Skolem's paradox, since there are sentences in set theory which postulate the existence of uncountable sets and yet these sentences are true in our countable model. Skolem's paradox is the mathematical fact that every countable Axiomatisation of Set theory in First-order logic, if Consistent, has Particularly the proof of the independence of the continuum hypothesis requires considering sets in models which appear to be uncountable when viewed from within the model, but are countable to someone outside the model. In Mathematics, the continuum hypothesis (abbreviated CH) is a Hypothesis, advanced by Georg Cantor, about the possible sizes of Infinite

The model-theoretic viewpoint has been useful in set theory; for example in Kurt Gödel's work on the constructible universe, which, along with the method of forcing developed by Paul Cohen can be shown to prove the (again philosophically interesting) independence of the axiom of choice and the continuum hypothesis from the other axioms of set theory. Kurt Gödel (kʊɐ̯t ˈgøːdl̩ (April 28 1906 – January 14 1978 was an Austrian American Logician, Mathematician and Philosopher Paul Joseph Cohen ( April 2, 1934 &ndash March 23, 2007) was an American Mathematician best known for his proof of In Mathematical logic, a sentence &sigma is called independent of a given first-order theory T if T neither proves nor In Mathematics, the axiom of choice, or AC, is an Axiom of Set theory. In Mathematics, the continuum hypothesis (abbreviated CH) is a Hypothesis, advanced by Georg Cantor, about the possible sizes of Infinite

Computable model theory

Main article: Computable model theory

Other basic notions of model theory

Maps between structures

Fix a language $L$ , and let $M$ and $N$ be two $L$ -structures. Computable model theory is a branch of Model theory which deals with questions of Computability as they apply to model-theoretical structures For symbols from the language, such as a constant $c$ , let $c M$ be the interpretation of $c$ in $M$ and similarly for the other classes of symbols (functions and relations).

A map $h$ from the domain of $M$ to the domain of $N$ is a homomorphism if the following conditions hold:

for every constant symbol $c \in L$ , we have $h (c M) = c N,$
for every n-ary function symbol $f \in L$ and $a_1,\ldots,a_n \in M^n$ , we have $h(f^M(a_1,\ldots,a_n))=f^N(h(a_1),\ldots,h(a_n)),$ and
for every n-ary relation symbol $R \in L$ and $a_1,\ldots,a_n \in M^n$ , we have $M \models R(a_1,\ldots,a_n) \Rightarrow N \models R(h(a_1),\ldots,h(a_n)).$

If in addition, the map $j$ is injective and the third condition is modified to read:

for every n-ary relation symbol $R \in L$ and $a_1,\ldots,a_n \in M^n,$ we have $M \models R(a_1,\ldots,a_n) \Leftrightarrow N \models R(h(a_1),\ldots,h(a_n)),$

then the map $h$ is an embedding (of $M$ into $N$ ).

Equivalent definitions of homomorphism and embedding are:

If for all atomic formulas $φ$ and sequences of elements from $M$ , $\bar{a} = (a_1,a_2,\ldots,a_n)$

$M \models \phi [\bar{a}] \Rightarrow N \models \phi [\bar{b}]$

where $\bar{b}$ is the image of $\bar{a}$ under $h$ :

$\bar{b} = (b_1,b_2,\ldots,b_n) = (h(a_1),h(a_2),\ldots,h(a_n)) = h(\bar{a})$

then $h$ is a homomorphism. In Mathematical logic, an atomic formula (also known simply as an atom) is a formula with no deeper Propositional structure that is a formula If instead:

$M \models \phi [\bar{a}] \Leftrightarrow N \models \phi [\bar{b}]$

then $h$ is an embedding.

Formulae and definable sets

We said earlier that when we fix an $L$ -structure, all the sentences and formulae are given a meaning. The sentences are either true or false, but the formulae have a different meaning. Formulae contain free variables, and these must be assigned a meaning before we can ascertain their veracity. An example in plain English is the following: 'it is red' (applied to the real world). Only when we substitute the name of a particular object can we ascertain whether this formula is true. The above formula divides the world into the set of things which are red, and the set of things which are not red. This is the function of formulae: for a given $L$ -formula $\phi(x_1,\ldots,x_n)$ , $L$ -structure $M$ , and elements $m_1,\ldots,m_n$ of $M$ , we write $m_1,\ldots,m_n \models \phi(x_1,\ldots,x_n)$ if $m_1,\ldots,m_n$ satisfy $\phi(x_1,\ldots,x_n)$ . Then we call $\{m_1,\ldots,m_n \in M^n:m_1,\ldots,m_n \models \phi(x_1,\ldots,x_n)\}$ the set defined by $φ$ in $M$ .

Thus for each formula in $L$ , and each $L$ -structure $M$ we have the set defined by the formula. For any given $M$ , the collection of definable sets is the important semantical notion corresponding to the collection of formulae.

Elimination of quantifiers and model completeness

A theory T is said to admit elimination of quantifiers if every formula is provably equivalent to a quantifier-free formula under T. The theory T is model complete if every formula is provably equivalent to an existential formula. In Model theory, a theory is called model complete if every embedding of models is an elementary equivalence

These definitions concerning the syntactics of T can be shown to be equivalent to the following statement concerning the models of T (i. e. the semantics of T):

T has quantifier elimination if and only if for any two models B and C of T and for any common substructure A of B and C, B and C are elementarily equivalent in the language of T augmented with constants from A. In fact, it is sufficient to show that any sentence with only existential quantifiers have the same truth value for B and C.

T is model complete if and only if for every A and B models of T, and L-embedding of A into B, we have that the embedding is elementary. In Mathematics, an embedding (or imbedding) is one instance of some Mathematical structure contained within another instance such as a group In Model theory, an elementary embedding is a special case of an embedding that preserves all first-order formulas

One can see from the definition that quantifier elimination is stronger than model completeness. This is because formulas in model complete theories are equivalent containing only existential quantifiers. Any formula in a theory that admits quantifier elimination is equivalent to a quantifier-free formula which can be viewed as a special kind of existential formula.

In early model theory, quantifier elimination was used to demonstrate that various theories possess certain model-theoretic properties like decidability and completeness. A common technique was to show first that a theory admits elimination of quantifiers and thereafter prove decidability or completeness by considering only the quantifier-free formulas. This technique is used to show that Presburger arithmetic, i. e. the theory of the additive natural numbers, is decidable. The demonstration of the decidability of Presburger arithmetic already hints at the limitations of this technique. Theories could be decidable yet not admit quantifier elimination. Strictly speaking, the theory of the additive natural numbers did not admit quantifier elimination, but it was an expansion of the additive natural numbers that was shown to be decidable. Example: Nullstellensatz in ACF and DCF

Interpretability

Given a mathematical structure, there are very often associated structures which can be constructed as a quotient of part of the original structure via an equivalence relation. In Mathematics, a field F is said to be algebraically closed if every Polynomial in one Variable of degree at least 1 with Coefficients In Mathematics, a Differential field K is differentially closed if every finite system of Differential equations with a solution in some differential An important example is a quotient group of a group.

One might say that to understand the full structure one must understand these quotients. When the equivalence relation is definable, we can give the previous sentence a precise meaning. We say that these structures are interpretable. In Model theory, a structure N is called interpretable in M if all the components ( universe, functions, relations

A key fact is that one can translate sentences from the language of the interpreted structures to the language of the original structure. Thus one can show that if a structure M interprets another whose theory is undecidable, then M itself is undecidable. In Logic, the term decidable refers to the existence of an Effective method for determining membership in a set of formulas

Ultraproduct constructions

Main article: Ultraproduct

An ultraproduct is a quotient of the direct product of a family of structures of the same signature. An ultraproduct is a mathematical construction of which the ultrapower (defined below is a special case To use the ultraproduct construction, one chooses a suitable ultrafilter $\mathcal U$ on the index set $I$ of a family $\{\mathbb A_i | i \in I\}$ of structures, all with the same language. In the mathematical field of Set theory, an ultrafilter on a set X is a collection of Subsets of X that is a filter, that In Mathematics, the elements of a set A may be indexed or labeled by means of a set J that is on that account called an index Then one forms the product $\Pi_{i\in I}\mathbb A_i$ of the given family, and factors out the equivalence relation $\sim_{\mathcal U}$ that is defined on $\mathbb A$ by the rule

$\vec x\sim_U\vec y \iff \{i\in I | x_i=y_i\}\in\mathcal U$

The resulting structure is denoted by $\Pi_{i\in I}\mathbb A_i/\mathcal U$ . A subset $X$ of the family $\{\mathbb A_i | i \in I\}$ of structures is said to be almost all of them if $X$ is an element of the ultrafilter $\mathcal U$ . Thus, in the definition of the equivalence relation above, two (usually infinitely long, in most applications) vectors, $\vec x$ and $\vec y$ are identified iff their projections onto almost all of the axes $\mathbb A_i$ are identical.

The choice of which ultrafilter to use is dependent upon the application, and for many applications of model theory, the first and foremost criterion for choosing an ultrafilter is somehow related to cardinality. (For example, a frequently used type of ultrafilter is a uniform ultrafilter. An ultrafilter $\mathcal U$ on a set $I$ is uniform provided that every element of $\mathcal U$ is a set of the same cardinality as the set $I$ . ) However, there are some `trivial' cases that are essentially always avoided: non-proper ultrafilters (which many authors do not even call ultrafilters at all), and principal ultrafilters. (Here again, cardinality comes into play, because every (ultra)filter on a finite set is necessarily principal. )

A most important tool in the application of ultraproducts is a theorem of Łoś, which states that for any sentence $σ$ in the language appropriate for the given structures, $\Pi_{i\in I}\mathbb A_i/\mathcal U$ satisfies $σ$ if and only if $σ$ holds in almost all of the given structures.

Some striking applications of ultraproducts include very elegant proofs of the compactness theorem and the completeness theorem, Keisler's ultrapower theorem, which gives an algebraic characterization of the semantic notion of elementary equivalence, and the Robinson-Zakon presentation of the use of superstructures and their monomorphisms to construct nonstandard models of analysis, leading to the growth of the area of nonstandard analysis, which was pioneered (as an application of the compactness theorem) by Abraham Robinson. In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every Gödel's completeness theorem is a fundamental theorem in Mathematical logic that establishes a correspondence between semantic truth and syntactic provability in Non-standard analysis is a branch of Mathematics that formulates analysis using a rigorous notion of an Infinitesimal number Abraham Robinson ( October 6, 1918 &ndash April 11, 1974) was a Mathematician who is most widely known for development of Non-standard

Using the compactness and completeness theorems

Gödel's completeness theorem (not to be confused with his incompleteness theorems) says that a theory has a model if and only if it is consistent, i. Gödel's completeness theorem is a fundamental theorem in Mathematical logic that establishes a correspondence between semantic truth and syntactic provability in In Mathematical logic, Gödel's incompleteness theorems, proved by Kurt Gödel in 1931 are two Theorems stating inherent limitations of all but the most e. no contradiction is proved by the theory. This is the heart of model theory as it lets us answer questions about theories by looking at models and vice-versa. One should not confuse the completeness theorem with the notion of a complete theory. A complete theory is a theory that contains every sentence or its negation. This article is a technical mathematical article in the area of predicate logic Importantly, one can find a complete consistent theory extending any consistent theory. However, as shown by Gödel's incompleteness theorems only in relatively simple cases will it be possible to have a complete consistent theory that is also recursive, i. In Mathematical logic, Gödel's incompleteness theorems, proved by Kurt Gödel in 1931 are two Theorems stating inherent limitations of all but the most e. that can be described by a recursively enumerable set of axioms. In Computability theory, traditionally called Recursion theory, a set S of Natural numbers is called recursively enumerable, computably In particular, the theory of natural numbers has no recursive complete and consistent theory. Non-recursive theories are of little practical use, since it is undecidable if a proposed axiom is indeed an axiom, making proof-checking practically impossible. Undecidable has more than one meaning;In Mathematical logic: A Decision problem is called (recursively undecidable if no Algorithm can

The compactness theorem states that a set of sentences S is satisfiable if every finite subset of S is satisfiable. In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every In the context of proof theory the analogous statement is trivial, since every proof can have only a finite number of antecedents used in the proof. Proof theory is a branch of Mathematical logic that represents proofs as formal Mathematical objects facilitating their analysis by mathematical techniques In the context of model theory, however, this proof is somewhat more difficult. There are two well known proofs, one by Gödel (which goes via proofs) and one by Malcev (which is more direct and allows us to restrict the cardinality of the resulting model). Kurt Gödel (kʊɐ̯t ˈgøːdl̩ (April 28 1906 – January 14 1978 was an Austrian American Logician, Mathematician and Philosopher Anatoly Ivanovich Maltsev (Malcev ( Russian: Анато́лий Ива́нович Ма́льцев 27 November N

Model theory is usually concerned with first-order logic, and many important results (such as the completeness and compactness theorems) fail in second-order logic or other alternatives. First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science Gödel's completeness theorem is a fundamental theorem in Mathematical logic that establishes a correspondence between semantic truth and syntactic provability in In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every In Logic and Mathematics second-order logic is an extension of First-order logic, which itself is an extension of Propositional logic. In first-order logic all infinite cardinals look the same to a language which is countable. This is expressed in the Löwenheim-Skolem theorems, which state that any countable theory with an infinite model $\mathfrak{A}$ has models of all infinite cardinalities (at least that of the language) which agree with $\mathfrak{A}$ on all sentences, i. In Mathematical logic, the Löwenheim–Skolem theorem states that if a countable first-order theory has an infinite model then for every infinite Cardinal number e. they are 'elementarily equivalent'. In Mathematics, specifically Model theory, two structures for a given language are said to be elementarily equivalent if any sentence

Types

Fix an $L$ -structure $M$ , and a natural number $n$ . The set of definable subsets of $M n$ over some parameters $A$ is a Boolean algebra. In Abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. By Stone's representation theorem for Boolean algebras there is a natural dual notion to this. In Mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is Isomorphic to a Field of sets. One can consider this to be the topological space consisting of maximal consistent sets of formulae over $A$ . Topology ( Greek topos, "place" and logos, "study" is the branch of Mathematics that studies the properties of We call this the space of (complete) $n$ -types over $A$ , and write $S n (A)$ . In Model theory, a type is a set of first-order formulas in a language L with free variables x_1x_2\ldotsx_n which are true of a sequence of

Now consider an element $m \in M^n$ . Then the set of all formulae $φ$ with parameters in $A$ in free variables $x_1,\ldots,x_n$ so that $M \models \phi(m)$ is consistent and maximal such. It is called the type of $m$ over $A$ .

One can show that for any $n$ -type $p$ , there exists some elementary extension $N$ of $M$ and some $a \in N^n$ so that $p$ is the type of $a$ over $A$ .

Many important properties in model theory can be expressed with types. Further many proofs go via constructing models with elements that contain elements with certain types and then using these elements.

Illustrative Example: Suppose $M$ is an algebraically closed field. In Mathematics, a field F is said to be algebraically closed if every Polynomial in one Variable of degree at least 1 with Coefficients The theory has quantifier elimination . This allows us to show that a type is determined exactly by the polynomial equations it contains. Thus the space of $n$ -types over a subfield $A$ is bijective with the set of prime ideals of the polynomial ring $A[x_1,\ldots,x_n]$ . In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property In Mathematics, a prime ideal is a Subset of a ring which shares many important properties of a Prime number in the Ring of integers In Mathematics, especially in the field of Abstract algebra, a polynomial ring is a ring formed from the set of Polynomials in one or more variables This is the same set as the spectrum of $A[x_1,\ldots,x_n]$ . In Abstract algebra and Algebraic geometry, the spectrum of a Commutative ring R, denoted by Spec( R) is defined to be the set of Note however that the topology considered on the type space is the constructible topology: a set of types is basic open iff it is of the form $\{p: f(x)=0 \in p\}$ or of the form $\{p: f(x) \neq 0 \in p\}$ . In Metric topology and related fields of Mathematics, a set U is called open if intuitively speaking starting from any point x in This is finer than the Zariski topology. In Mathematics, namely Algebraic geometry, the Zariski topology is a particular Topology chosen for algebraic varieties that reflects the algebraic

Categoricity

If $T$ is a first order theory in the language $L$ and $κ$ is a cardinal, then $T$ is said to be $κ$ -categorical iff any two models of $T$ which are of cardinality $κ$ are isomorphic. This article describes cardinal numbers in mathematics For cardinals in linguistics see Names of numbers in English. In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective Categorical theories are from many points of view the most well behaved theories. The study of categoricity led on to the wider programme of stability. In Model theory, a complete theory is called stable if it does not have too many types For more detail see Morley's categoricity theorem. In Model theory, a branch of Mathematical logic, a theory is &kappa- categorical (or categorical in &kappa) if it has exactly one model of

Model completion, model companions

Given first-order σ-theories T and T', T' is a model companion for T if

i) T' is model complete

ii) Every model of T has an extension that is a model of T'

iii) Every model of T' has an extension that is a model of T

If $T'$ is a model companion for $T$ and $T' \cup Diag(\mathcal{M})$ is complete for any $\mathcal{M} \models T$ then $T'$ is a model completion for $T$

from Marker page 106

Early history of model theory

Model theory as a subject exists since approximately the middle of the 20th century. However some earlier research, especially in mathematical logic, is often regarded as being of a model-theoretical nature in retrospect. Mathematical logic is a subfield of Logic and Mathematics with close connections to Computer science and Philosophical logic. The first significant result in what is now model theory was a special case of the downward Löwenheim-Skolem theorem, published by Leopold Löwenheim in 1915. In Mathematical logic, the Löwenheim–Skolem theorem states that if a countable first-order theory has an infinite model then for every infinite Cardinal number Leopold Löwenheim (1878 Krefeld Germany - 1957 Berlin) was a German Mathematician, known for his work in Mathematical logic. The compactness theorem was implicit in work by Thoralf Skolem,^[2] but it was first published in 1930, as a lemma in Kurt Gödel's proof of his completeness theorem. In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every Thoralf Albert Skolem ( May 23, 1887 – March 23, 1963) (ˈtɔɾɑlf ˈskuləm was a Norwegian Mathematician known Kurt Gödel (kʊɐ̯t ˈgøːdl̩ (April 28 1906 – January 14 1978 was an Austrian American Logician, Mathematician and Philosopher Gödel's completeness theorem is a fundamental theorem in Mathematical logic that establishes a correspondence between semantic truth and syntactic provability in The Löwenheim-Skolems theorem and the compactness theorem received their respective general forms in 1936 and 1941 from Anatoly Maltsev. Anatoly Ivanovich Maltsev (Malcev ( Russian: Анато́лий Ива́нович Ма́льцев 27 November N

Notes

^ In a countable signature. In the branch of Mathematical logic called Model theory, an elementary class (or axiomatizable class) is a class consisting of all In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every Descriptive complexity is a branch of Finite model theory, a subfield of Computational complexity theory and Mathematical logic, which seeks to characterize In Model theory, an elementary embedding is a special case of an embedding that preserves all first-order formulas Finite model theory is a subfield of Model theory that focuses on properties of logical languages such as First-order logic, over finite structures such as In Mathematical logic, a first-order theory is given by a set of axioms in somelanguage In the mathematical discipline of Set theory, forcing is a technique invented by Paul Cohen, for proving Consistency and independence results Institutional model theory generalizes a large portion of first-order Model theory to an arbitrary Logical system. Kripke semantics (also known as relational semantics or frame semantics, and often confused with Possible world semantics) is a formal Semantics In Mathematical logic, the Löwenheim–Skolem theorem states that if a countable first-order theory has an infinite model then for every infinite Cardinal number Proof theory is a branch of Mathematical logic that represents proofs as formal Mathematical objects facilitating their analysis by mathematical techniques In Mathematical logic, and in particular Model theory, a saturated model M is one which realizes as many Complete types as may be "reasonably Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models" The theorem has a straightforward generalization to uncountable signatures.
^ All three commentators [i. e. Vaught, van Heijenoort and Dreben] agree that both the completeness and compactness theorems were implicit in Skolem 1923 [. . . ], Dawson (1993).

References

Canonical textbooks

Chang, Chen Chung & Keisler, H. Jerome (1990), Model Theory (3rd ed. H Jerome Keisler is an American Mathematician, currently professor emeritus at University of Wisconsin-Madison. ), Studies in Logic and the Foundations of Mathematics, Elsevier, ISBN 978-0-444-88054-3
Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6

Other textbooks

Bell, John L. Wilfrid Hodges (born 1941 is a British Mathematician, known for his work in Model theory. Cambridge University Press (known colloquially as CUP is a Publisher given a Royal Charter by Henry VIII in 1534 ; Slomson, Alan B. [1969] (2006). Models and Ultraproducts: An Introduction, reprint of 1974 edition, Dover Publications. Dover Publications is an American book Publisher founded in 1941 by Hayward Cirker and his wife Blanche ISBN 0-486-44979-3.
Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Mathematical Logic. Springer. Springer Science+Business Media or Springer (ˈʃpʁɪŋɐ is a worldwide Publishing company based in Germany, which publishes textbooks academic ISBN 0-38794258-0.
Hinman, Peter G. (2005). Fundamentals of Mathematical Logic. A K Peters. A K Peters Ltd is a publisher of scientific and technical books specializing in Mathematics and in Computer graphics, Robotics, and other fields of ISBN 1-568-81262-0.
Hodges, Wilfrid (1993). Wilfrid Hodges (born 1941 is a British Mathematician, known for his work in Model theory. Model theory. Cambridge University Press. Cambridge University Press (known colloquially as CUP is a Publisher given a Royal Charter by Henry VIII in 1534 ISBN 0-521-30442-3.
Marker, David (2002). Model Theory: An Introduction, Graduate Texts in Mathematics 217. Graduate Texts in Mathematics (GTM is a series of graduate-level Textbooks in Mathematics published by Springer-Verlag. Springer. ISBN 0-387-98760-6.
Poizat, Bruno (2000). A Course in Model Theory. Springer. Springer Science+Business Media or Springer (ˈʃpʁɪŋɐ is a worldwide Publishing company based in Germany, which publishes textbooks academic ISBN 0-387-98655-3.
Rothmaler, Philipp (2000). Introduction to Model Theory, new edition, Taylor & Francis. Taylor & Francis Group is an international company originating in the United Kingdom which publishes books and academic journals ISBN 9056993135.

Free online texts

Chatzidakis, Zoe (2001). Introduction to Model Theory, 26 pages in DVI format. DVI stands for device independent There also is an article about Device independent.
Pillay, Anand (2002). Lecture Notes – Model Theory, 61 pages.
Hodges, Wilfrid, First-order Model theory. Wilfrid Hodges (born 1941 is a British Mathematician, known for his work in Model theory. The Stanford Encyclopedia Of Philosophy, E. Zalta (ed. ).
Simmons, Harold (2004), An introduction to Good old fashioned model theory. Notes of an introductory course for postgraduates (with exercises).

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents