HOME

TheInfoList



OR:

In
model theory In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, a branch of
mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, two
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 ...
s ''M'' and ''N'' of the same
signature A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
''σ'' are called elementarily equivalent if they satisfy the same
first-order In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
''σ''-sentences. If ''N'' is a substructure of ''M'', one often needs a stronger condition. In this case ''N'' is called an elementary substructure of ''M'' if every first-order ''σ''-formula ''φ''(''a''1, …, ''a''''n'') with parameters ''a''1, …, ''a''''n'' from ''N'' is true in ''N'' if and only if it is true in ''M''. If ''N'' is an elementary substructure of ''M'', then ''M'' is called an elementary extension of ''N''. An
embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is gi ...
''h'': ''N'' → ''M'' is called an elementary embedding of ''N'' into ''M'' if ''h''(''N'') is an elementary substructure of ''M''. A substructure ''N'' of ''M'' is elementary if and only if it passes the Tarski–Vaught test: every first-order formula ''φ''(''x'', ''b''1, …, ''b''''n'') with parameters in ''N'' that has a solution in ''M'' also has a solution in ''N'' when evaluated in ''M''. One can prove that two structures are elementarily equivalent with the Ehrenfeucht–Fraïssé games.


Elementarily equivalent structures

Two structures ''M'' and ''N'' of the same signature ''σ'' are elementarily equivalent if every first-order sentence (formula without free variables) over ''σ'' is true in ''M'' if and only if it is true in ''N'', i.e. if ''M'' and ''N'' have the same
complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
first-order theory. If ''M'' and ''N'' are elementarily equivalent, one writes ''M'' ≡ ''N''. A first-order
theory A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be s ...
is complete if and only if any two of its models are elementarily equivalent. For example, consider the language with one binary relation symbol '<'. The model R of
real numbers In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
with its usual order and the model Q of
rational numbers In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
with its usual order are elementarily equivalent, since they both interpret '<' as an unbounded dense
linear ordering In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexi ...
. This is sufficient to ensure elementary equivalence, because the theory of unbounded dense linear orderings is complete, as can be shown by the
Łoś–Vaught test In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in th ...
. More generally, any first-order theory with an infinite model has non-isomorphic, elementarily equivalent models, which can be obtained via the
Löwenheim–Skolem theorem In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. It implies that if a countable first-order t ...
. Thus, for example, there are non-standard models 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 nearly u ...
, which contain other objects than just the numbers 0, 1, 2, etc., and yet are elementarily equivalent to the standard model.


Elementary substructures and elementary extensions

''N'' is an elementary substructure of ''M'' if ''N'' and ''M'' are structures of the same
signature A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
 ''σ'' such that for all first-order ''σ''-formulas ''φ''(''x''1, …, ''x''''n'') with free variables ''x''1, …, ''x''''n'', and all elements ''a''1, …, ''a''n of ''N'', ''φ''(''a''1, …, ''a''n) holds in ''N'' if and only if it holds in ''M'': N \models \varphi(a_1, \dots, a_n) \text M \models \varphi(a_1, \dots, a_n). It follows that ''N'' is a substructure of ''M''. If ''N'' is a substructure of ''M'', then both ''N'' and ''M'' can be interpreted as structures in the signature ''σ''''N'' consisting of ''σ'' together with a new constant symbol for every element of ''N''. Then ''N'' is an elementary substructure of ''M'' if and only if ''N'' is a substructure of ''M'' and ''N'' and ''M'' are elementarily equivalent as ''σ''''N''-structures. If ''N'' is an elementary substructure of ''M'', one writes ''N'' \preceq ''M'' and says that ''M'' is an elementary extension of ''N'': ''M'' \succeq ''N''. The downward
Löwenheim–Skolem theorem In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. It implies that if a countable first-order t ...
gives a countable elementary substructure for any infinite first-order structure in at most countable signature; the upward Löwenheim–Skolem theorem gives elementary extensions of any infinite first-order structure of arbitrarily large cardinality.


Tarski–Vaught test

The Tarski–Vaught test (or Tarski–Vaught criterion) is a necessary and sufficient condition for a substructure ''N'' of a structure ''M'' to be an elementary substructure. It can be useful for constructing an elementary substructure of a large structure. Let ''M'' be a structure of signature ''σ'' and ''N'' a substructure of ''M''. Then ''N'' is an elementary substructure of ''M'' if and only if for every first-order formula ''φ''(''x'', ''y''1, …, ''y''''n'') over ''σ'' and all elements ''b''1, …, ''b''''n'' from ''N'', if ''M'' \models ''x'' ''φ''(''x'', ''b''1, …, ''b''''n''), then there is an element ''a'' in ''N'' such that ''M'' \models ''φ''(''a'', ''b''1, …, ''b''''n'').


Elementary embeddings

An elementary embedding of a structure ''N'' into a structure ''M'' of the same signature ''σ'' is a map ''h'': ''N'' → ''M'' such that for every first-order ''σ''-formula ''φ''(''x''1, …, ''x''''n'') and all elements ''a''1, …, ''a''n of ''N'', :''N'' \models ''φ''(''a''1, …, ''a''''n'') if and only if ''M'' \models ''φ''(''h''(''a''1), …, ''h''(''a''''n'')). Every elementary embedding is a strong homomorphism, and its image is an elementary substructure. Elementary embeddings are the most important maps in model theory. In
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, elementary embeddings whose domain is ''V'' (the universe of set theory) play an important role in the theory of
large cardinals In the mathematical field of set theory, a large cardinal property is a certain kind of property of Transfinite number, transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, big ...
(see also Critical point).


References

* . * . * {{DEFAULTSORT:Elementary Equivalence Equivalence (mathematics) Mathematical logic Model theory