Type (model theory)
   HOME

TheInfoList



OR:

In
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...
and related areas of
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a type is an object that describes how a (real or possible) element or finite collection of elements in a
mathematical structure In mathematics, a structure on a set (or on some sets) refers to providing or endowing it (or them) with certain additional features (e.g. an operation, relation, metric, or topology). Τhe additional features are attached or related to the ...
might behave. More precisely, it is a set of first-order formulas in a language ''L'' with
free variable In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a variable may be said to be either free or bound. Some older books use the terms real variable and apparent variable for f ...
s ''x''1, ''x''2,..., ''x''''n'' that are true of a set of ''n''-tuples of an ''L''-structure \mathcal. Depending on the context, types can be complete or partial and they may use a fixed set of constants, ''A'', from the structure \mathcal. The question of which types represent actual elements of \mathcal leads to the ideas of saturated models and omitting types.


Formal definition

Consider a
structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
\mathcal for a
language Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
''L''. Let ''M'' be the
universe The universe is all of space and time and their contents. It comprises all of existence, any fundamental interaction, physical process and physical constant, and therefore all forms of matter and energy, and the structures they form, from s ...
of the structure. For every ''A'' ⊆ ''M'', let ''L''(''A'') be the language obtained from ''L'' by adding a constant ''c''''a'' for every ''a'' ∈ ''A''. In other words, :L(A) = L \cup \. A 1-type (of \mathcal) over ''A'' is a set ''p''(''x'') of formulas in ''L''(''A'') with at most one free variable ''x'' (therefore 1-type) such that for every finite subset ''p''0(''x'') ⊆ ''p''(''x'') there is some ''b'' ∈ ''M'', depending on ''p''0(''x''), with \mathcal \models p_0(b) (i.e. all formulas in ''p''0(''x'') are true in \mathcal when ''x'' is replaced by ''b''). Similarly an ''n''-type (of \mathcal) over ''A'' is defined to be a set ''p''(''x''1,...,''x''''n'') = ''p''(''x'') of formulas in ''L''(''A''), each having its free variables occurring only among the given ''n'' free variables ''x''1,...,''x''''n'', such that for every finite subset ''p''0(''x'') ⊆ ''p''(''x'') there are some elements ''b''1,...,''b''''n'' ∈ ''M'' with \mathcal\models p_0(b_1,\ldots,b_n). A complete type of \mathcal over ''A'' is one that is maximal with respect to inclusion. Equivalently, for every \phi(\boldsymbol) \in L(A,\boldsymbol) either \phi(\boldsymbol) \in p(\boldsymbol) or \lnot\phi(\boldsymbol) \in p(\boldsymbol). Any non-complete type is called a partial type. So, the word type in general refers to any ''n''-type, partial or complete, over any chosen set of parameters (possibly the empty set). An ''n''-type ''p''(''x'') is said to be realized in \mathcal if there is an element ''b'' ∈ ''M''''n'' such that \mathcal\models p(\boldsymbol). The existence of such a realization is guaranteed for any type by the
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 generall ...
, although the realization might take place in some elementary extension of \mathcal, rather than in \mathcal itself. If a complete type is realized by ''b'' in \mathcal, then the type is typically denoted tp_n^(\boldsymbol/A) and referred to as the complete type of ''b'' over ''A''. A type ''p''(''x'') is said to be isolated by ''\varphi'', for \varphi \in p(x), if for all \psi(\boldsymbol) \in p(\boldsymbol), we have \operatorname(\mathcal M) \models \varphi(\boldsymbol) \rightarrow \psi(\boldsymbol). Since finite subsets of a type are always realized in \mathcal, there is always an element ''b'' ∈ ''M''''n'' such that ''φ''(''b'') is true in \mathcal; i.e. \mathcal \models \varphi(\boldsymbol), thus ''b'' realizes the entire isolated type. So isolated types will be realized in every elementary substructure or extension. Because of this, isolated types can never be omitted (see below). A model that realizes the maximum possible variety of types is called a saturated model, and the
ultrapower The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All fact ...
construction provides one way of producing saturated models.


Examples of types

Consider the language ''L'' with one binary relation symbol, which we denote as \in. Let \mathcal be the structure \langle \omega, \in_\rangle for this language, which is the ordinal \omega with its standard well-ordering. Let \mathcal denote the
first-order theory In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, giving rise to a formal system that combines the language with deduct ...
of \mathcal. Consider the set of ''L''(ω)-formulas p(x):=\ . First, we claim this is a type. Let p_0(x)\subseteq p(x) be a finite subset of p(x). We need to find a b\in\omega that satisfies all the formulas in p_0. Well, we can just take the successor of the largest ordinal mentioned in the set of formulas p_0(x). Then this will clearly contain all the ordinals mentioned in p_0(x). Thus we have that p(x) is a type. Next, note that p(x) is not realized in \mathcal. For, if it were there would be some n\in\omega that contains every element of \omega. If we wanted to realize the type, we might be tempted to consider the structure \langle \omega+1,\in_\rangle, which is indeed an extension of \mathcal that realizes the type. Unfortunately, this extension is not elementary, for example, it does not satisfy \mathcal. In particular, the sentence \exists x \forall y (y\in x \lor y=x) is satisfied by this structure and not by \mathcal. So, we wish to realize the type in an elementary extension. We can do this by defining a new ''L''-structure, which we will denote \mathcal'. The domain of the structure will be \omega \cup \mathbb' where \mathbb' is the set of integers adorned in such a way that \mathbb'\cap\omega=\emptyset. Let < denote the usual order of \mathbb'. We interpret the symbol \in in our new structure by \in_ = \in_ \cup < \cup \,(\omega \times \mathbb'). The idea being that we are adding a "\mathbb-chain", or copy of the integers, above all the finite ordinals. Clearly any element of \mathbb' realizes the type p(x). Moreover, one can verify that this extension is elementary. Another example: the complete type of the number 2 over the empty set, considered as a member of the natural numbers, would be the set of all first-order statements (in the language of
Peano arithmetic In mathematical logic, the Peano axioms (, ), also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nea ...
), describing a variable ''x'', that are true when ''x'' = 2. This set would include formulas such as \,\!x\ne 1+1+1, x\le 1+1+1+1+1, and \exists y(y. This is an example of an isolated type, since, working over the theory of the naturals, the formula x = 1+1 implies all other formulas that are true about the number 2. As a further example, the statements :\forall y(y^2<2 \implies y and :\forall y((y>0 \land y^2>2) \implies y>x) describing the
square root of 2 The square root of 2 (approximately 1.4142) is the positive real number that, when multiplied by itself or squared, equals the number 2. It may be written as \sqrt or 2^. It is an algebraic number, and therefore not a transcendental number. Te ...
are consistent with the axioms of
ordered field In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Basic examples of ordered fields are the rational numbers and the real numbers, both with their standard ord ...
s, and can be extended to a complete type. This type is not realized in the ordered field of rational numbers, but is realized in the ordered field of reals. Similarly, the infinite set of formulas (over the empty set) is not realized in the ordered field of real numbers, but is realized in the ordered field of
hyperreals In mathematics, hyperreal numbers are an extension of the real numbers to include certain classes of infinite and infinitesimal numbers. A hyperreal number x is said to be finite if, and only if, , x, for some integer n
. Similarly, we can specify a type \ that is realized by an
infinitesimal In mathematics, an infinitesimal number is a non-zero quantity that is closer to 0 than any non-zero real number is. The word ''infinitesimal'' comes from a 17th-century Modern Latin coinage ''infinitesimus'', which originally referred to the " ...
hyperreal that violates the
Archimedean property In abstract algebra and mathematical analysis, analysis, the Archimedean property, named after the ancient Greek mathematician Archimedes of Syracuse, Italy, Syracuse, is a property held by some algebraic structures, such as ordered or normed g ...
. The reason it is useful to restrict the parameters to a certain subset of the model is that it helps to distinguish the types that can be satisfied from those that cannot. For example, using the entire set of real numbers as parameters one could generate an uncountably infinite set of formulas like x\ne 1, x\ne \pi, ... that would explicitly rule out every possible real value for ''x'', and therefore could never be realized within the real numbers.


Stone spaces

It is useful to consider the set of complete ''n''-types over ''A'' as a
topological space In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...
. Consider the following
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...
on formulas in the free variables ''x''1,..., ''x''''n'' with parameters in ''A'': :\psi \equiv \phi \Leftrightarrow \mathcal \models \forall x_1,\ldots,x_n (\psi(x_1,\ldots,x_n) \leftrightarrow \phi(x_1,\ldots,x_n)). One can show that \psi \equiv \phi if and only if they are contained in exactly the same complete types. The set of formulas in free variables ''x''1,...,''x''''n'' over ''A'' up to this equivalence relation is a
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
(and is canonically
isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to the set of ''A''-definable subsets of ''M''''n''). The complete ''n''-types correspond to
ultrafilter In the Mathematics, mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a Maximal element, maximal Filter (mathematics), filter on P; that is, a proper filter on P th ...
s of this Boolean algebra. The set of complete ''n''-types can be made into a topological space by taking the sets of types containing a given formula as a basis of open sets. This constructs the Stone space associated to the Boolean algebra, which is a
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact, a type of agreement used by U.S. states * Blood compact, an ancient ritual of the Philippines * Compact government, a t ...
, Hausdorff, and totally disconnected space. Example. The complete theory of
algebraically closed field In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in . In other words, a field is algebraically closed if the fundamental theorem of algebra ...
s of characteristic 0 has
quantifier elimination Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement "\exists x such that ..." can be viewed as a question "When is there an x such ...
, which allows one to show that the possible complete 1-types (over the empty set) correspond to: *
Root In vascular plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
s of a given irreducible non-constant polynomial over the rationals with leading coefficient 1. For example, the type of square roots of 2. Each of these types is an
isolated point In mathematics, a point is called an isolated point of a subset (in a topological space ) if is an element of and there exists a neighborhood of that does not contain any other points of . This is equivalent to saying that the singleton i ...
of the Stone space. * Transcendental elements, which are not roots of any non-zero polynomial. This type is a point in the Stone space that is closed but not isolated. In other words, the 1-types correspond exactly to the
prime ideal In algebra, a prime ideal is a subset of a ring (mathematics), ring that shares many important properties of a prime number in the ring of Integer#Algebraic properties, integers. The prime ideals for the integers are the sets that contain all th ...
s of the
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates (traditionally also called variables) with coefficients in another ring, ...
Q 'x''over the rationals Q: if ''r'' is an element of the model of type ''p'', then the ideal corresponding to ''p'' is the set of polynomials with ''r'' as a root (which is only the zero polynomial if ''r'' is transcendental). More generally, the complete ''n''-types correspond to the prime ideals of the polynomial ring Q 'x''1,...,''x''n in other words to the points of the
prime spectrum In commutative algebra, the prime spectrum (or simply the spectrum) of a commutative ring R is the set of all prime ideals of R, and is usually denoted by \operatorname; in algebraic geometry it is simultaneously a topological space equipped with ...
of this ring. (The Stone space topology can in fact be viewed as the
Zariski topology In algebraic geometry and commutative algebra, the Zariski topology is a topology defined on geometric objects called varieties. It is very different from topologies that are commonly used in real or complex analysis; in particular, it is not ...
of a
Boolean ring In mathematics, a Boolean ring is a ring for which for all in , that is, a ring that consists of only idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean algebra, with ring multiplicat ...
induced in a natural way from the Boolean algebra. While the Zariski topology is not in general Hausdorff, it is in the case of Boolean rings.) For example, if ''q''(''x'',''y'') is an irreducible polynomial in two variables, there is a 2-type whose realizations are (informally) pairs (''x'',''y'') of elements with ''q''(''x'',''y'')=0.


Omitting types theorem

Given a complete ''n''-type ''p'' one can ask if there is a model of the theory that omits ''p'', in other words there is no ''n''-tuple in the model that realizes ''p''. If ''p'' is an
isolated point In mathematics, a point is called an isolated point of a subset (in a topological space ) if is an element of and there exists a neighborhood of that does not contain any other points of . This is equivalent to saying that the singleton i ...
in the Stone space, i.e. if is an open set, it is easy to see that every model realizes ''p'' (at least if the theory is complete). The omitting types theorem says that conversely if ''p'' is not isolated then there is a countable model omitting ''p'' (provided that the language is countable). Example: In the theory of algebraically closed fields of characteristic 0, there is a 1-type represented by elements that are transcendental over the
prime field In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers. A field is thus a fundamental algebraic structure which is wid ...
Q. This is a non-isolated point of the Stone space (in fact, the only non-isolated point). The field of algebraic numbers is a model omitting this type, and the algebraic closure of any transcendental extension of the rationals is a model realizing this type. All the other types are "algebraic numbers" (more precisely, they are the sets of first-order statements satisfied by some given algebraic number), and all such types are realized in all algebraically closed fields of characteristic 0.


References

* * * {{Mathematical logic Concepts in logic Mathematical logic Model theory