Misplaced Pages

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (February 2023) (Learn how and when to remove this message)

In model theory, a branch of mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-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₁, …, a_n) with parameters a₁, …, 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 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₁, …, 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.

Elementary embeddings are used in the study of large cardinals, including rank-into-rank.

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 first-order theory. If M and N are elementarily equivalent, one writes M ≡ N.

A first-order theory 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 with its usual order and the model Q of rational numbers with its usual order are elementarily equivalent, since they both interpret '<' as an unbounded dense linear ordering. 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.

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. Thus, for example, there are non-standard models of Peano arithmetic, 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 or elementary submodel of M if N and M are structures of the same signature σ such that for all first-order σ-formulas φ(x₁, …, x_n) with free variables x₁, …, x_n, and all elements a₁, …, a_n of N, φ(a₁, …, a_n) holds in N if and only if it holds in M: $${\displaystyle N\models \varphi (a_{1},\dots ,a_{n}){\text{ if and only if }}M\models \varphi (a_{1},\dots ,a_{n}).}$$

This definition first appears in Tarski, Vaught (1957). 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 ${\displaystyle \preceq }$ M and says that M is an elementary extension of N: M ${\displaystyle \succeq }$ N.

The downward Löwenheim–Skolem theorem 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₁, …, y_n) over σ and all elements b₁, …, b_n from N, if M ${\displaystyle \models }$ ${\displaystyle \exists }$x φ(x, b₁, …, b_n), then there is an element a in N such that M ${\displaystyle \models }$ φ(a, b₁, …, 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₁, …, x_n) and all elements a₁, …, a_n of N,

N ${\displaystyle \models }$ φ(a₁, …, a_n) if and only if M ${\displaystyle \models }$ φ(h(a₁), …, 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, elementary embeddings whose domain is V (the universe of set theory) play an important role in the theory of large cardinals (see also Critical point).

References

1. E. C. Milner, The use of elementary substructures in combinatorics (1993). Appearing in Discrete Mathematics, vol. 136, issues 1--3, 1994, pp.243--252.

• Chang, Chen Chung; Keisler, H. Jerome (1990) , Model Theory, Studies in Logic and the Foundations of Mathematics (3rd ed.), Elsevier, ISBN 978-0-444-88054-3.
• Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6.
• Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, New York • Heidelberg • Berlin: Springer Verlag, ISBN 0-387-90170-1

v t e Mathematical logic
General	Axiom list Cardinality First-order logic Formal proof Formal semantics Foundations of mathematics Information theory Lemma Logical consequence Model Theorem Theory Type theory
Theorems (list)  and paradoxes	Gödel's completeness and incompleteness theorems Tarski's undefinability Banach–Tarski paradox Cantor's theorem, paradox and diagonal argument Compactness Halting problem Lindström's Löwenheim–Skolem Russell's paradox
Logics	Traditional Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram Propositional Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞ Predicate First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus
Set theory	Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities Types of sets Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann Maps and cardinality Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary Set theories Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive
Formal systems (list), language and syntax	Alphabet Arity Automata Axiom schema Expression ground Extension by definition conservative Relation Formation rule Grammar Formula atomic closed ground open Free/bound variable Language Metalanguage Logical connective ¬ ∨ ∧ → ↔ = Predicate functional variable propositional variable Proof Quantifier ∃ ! ∀ rank Sentence atomic spectrum Signature String Substitution Symbol function logical/constant non-logical variable Term Theory list Example axiomatic systems (list) of arithmetic: Peano second-order elementary function primitive recursive Robinson Skolem of the real numbers Tarski's axiomatization of Boolean algebras canonical minimal axioms of geometry: Euclidean: Elements Hilbert's Tarski's non-Euclidean Principia Mathematica
Proof theory	Formal proof Natural deduction Logical consequence Rule of inference Sequent calculus Theorem Systems axiomatic deductive Hilbert list Complete theory Independence (from ZFC) Proof of impossibility Ordinal analysis Reverse mathematics Self-verifying theories
Model theory	Interpretation function of models Model equivalence finite saturated spectrum submodel Non-standard model of arithmetic Diagram elementary Categorical theory Model complete theory Satisfiability Semantics of logic Strength Theories of truth semantic Tarski's Kripke's T-schema Transfer principle Truth predicate Truth value Type Ultraproduct Validity
Computability theory	Church encoding Church–Turing thesis Computably enumerable Computable function Computable set Decision problem decidable undecidable P NP P versus NP problem Kolmogorov complexity Lambda calculus Primitive recursive function Recursion Recursive set Turing machine Type theory
Related	Abstract logic Algebraic logic Automated theorem proving Category theory Concrete/Abstract category Category of sets History of logic History of mathematical logic timeline Logicism Mathematical object Philosophy of mathematics Supertask
Mathematics portal

• Equivalence (mathematics)
• Mathematical logic
• Model theory