Elementary equivalence

Elementary equivalence
Name	Elementary equivalence
Field	Mathematical logic
Subfield	Model theory
Introduced	20th century
Notable	Alfred Tarski; Abraham Robinson; Leon Henkin

Elementary equivalence

Elementary equivalence is a relation between first-order structures indicating they satisfy precisely the same sentences of a given first-order language. It sits alongside related notions such as isomorphism, bi-interpretability, and elementary embedding in the development of model theory and connects to work by figures like Alfred Tarski, Abraham Robinson, Leon Henkin, Kurt Gödel, and Alfred North Whitehead. The concept plays a role in investigations tied to the Löwenheim–Skolem theorem, the Compactness theorem, and classification theory such as stability theory and o-minimality.

Definition

Two structures A and B in the same first-order language L are elementarily equivalent if for every L-sentence φ, A ⊨ φ iff B ⊨ φ. The definition hinges on the syntax of L as developed in texts influenced by mathematicians and logicians like David Hilbert, Wilhelm Ackermann, Emil Post, Alonzo Church, and Stephen Kleene. Elementary equivalence is coarser than isomorphism: isomorphic structures are elementarily equivalent, but elementarily equivalent structures need not be isomorphic, a phenomenon studied by Ehrenfeucht and others in connection with games and invariants.

Examples

- Non-isomorphic but elementarily equivalent models of arithmetic arise in investigations related to Kurt Gödel's incompleteness phenomena and were constructed with tools from Skolem's methods; such models share all first-order truths about Peano arithmetic but differ in non-first-order features. - Dense linear orders without endpoints like the rational order (ℚ, <) and many countable models produced by back-and-forth arguments are elementarily equivalent, a fact tied to work by Felix Hausdorff and refined in model theoretic accounts by Saharon Shelah. - Algebraic examples include algebraically closed fields of fixed characteristic: by the Ax–Kochen theorem and elimination theorems developed by Julia Robinson and Alfred Tarski, fields such as the complex numbers and other algebraically closed fields of the same characteristic share first-order theory. - Ultraproduct constructions introduced by Jerzy Łoś produce elementarily equivalent ultraproducts and ultralimits used by Jerome Keisler and H. Jerome Keisler in nonstandard analysis, connecting to models of the real numbers and nonstandard models studied by Edward Nelson.

Model-theoretic properties

Elementary equivalence interacts with key results: by the Compactness theorem, consistency of sets of sentences yields models that can be chosen to be elementarily equivalent to given structures; by the Löwenheim–Skolem theorem, elementary equivalence admits models of various cardinalities, a theme connected to the work of Thoralf Skolem and Leopold Löwenheim. Ehrenfeucht–Fraïssé games, developed by André Ehrenfeucht and Roland Fraïssé, provide combinatorial criteria to test elementary equivalence or distinguishability between structures. Stability-theoretic invariants from classification theory due to Saharon Shelah determine when families of elementarily equivalent models exhibit tameness or wildness, with further refinement in notions like superstability and simplicity studied by Morley and others.

Characterizations and criteria

Several characterizations facilitate verification of elementary equivalence. Łoś's theorem characterizes sentences preserved under ultraproducts and yields a criterion: two structures are elementarily equivalent iff they have isomorphic ultrapowers for some ultrafilter, a perspective developed by H. Jerome Keisler and applied in research by Chang and Keisler. Back-and-forth methods and partial isomorphisms underpin classic characterizations for countable structures traced to Fraïssé's theory; Ehrenfeucht–Fraïssé games give a finite-round criterion that has been exploited by logicians including Ronald Fagin and Michael V. Saks in finite model theory contexts. Quantifier-elimination results, as used in the study of real closed fields and algebraically closed fields by Alfred Tarski and James Ax, provide syntactic routes to establishing elementary equivalence.

Preservation and transfer results

Preservation theorems such as the Łoś–Tarski principle, the Keisler–Shelah isomorphism results, and various interpolation theorems articulate how elementary equivalence is preserved under constructions: ultraproducts, elementary chains, and reducts or expansions under definitional equivalence studied by Solomon Feferman and Michael O. Rabin. Transfer principles in number theory and algebra, typified by the Ax–Kochen theorem and applications to diophantine problems considered by John Tate and Jean-Pierre Serre, exploit elementary equivalence to move first-order properties between disparate structures, often via model-completion or model-companion techniques developed by Svenonius and Robinson.

Applications and significance

Elementary equivalence has broad applications: it underpins nonstandard analysis initiated by Abraham Robinson and deployed by Edward Nelson; it guides classification efforts in algebraic geometry via model-theoretic tools used by Denef and Hrushovski; it informs algebraic number theory through results of Ax and Kochen; and it shapes computational model theory and finite model theory work by researchers like Neil Immerman and Moshe Vardi. The notion illuminates limits of first-order expressibility identified by Alfred Tarski and Kurt Gödel and continues to influence modern inquiries into definability, decidability, and the structure of mathematical theories pursued by logicians at institutions such as Princeton University, University of California, Berkeley, Hebrew University of Jerusalem, and University of Oxford.

Category:Model theory