A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.

Elementary Equivalence and Logical Indistinguishability

Graduate Depth 87 in the knowledge graph ☐ I know this ☆ Set as goal
63topics build on this
486prerequisites beneath it
See this on the map →
Model Interpretation and SatisfactionEquivalence Relations and Partitions+2 more→→Back-and-Forth Method: Advanced ApplicationsCategorical Theories and Uniqueness of Models+3 more
elementary equivalence indistinguishability sentences logical power

Core Idea

Two structures are elementarily equivalent if they satisfy exactly the same first-order sentences. This is weaker than isomorphism—structures can be elementarily equivalent with different domains—but captures the idea that first-order logic cannot distinguish them. Elementary equivalence is the central notion linking models to the sentences they satisfy.

Explainer

You already know what it means for a structure to satisfy a formula — a model M satisfies φ (written M ⊨ φ) when the interpretation makes the formula true. Elementary equivalence scales this up from single formulas to entire theories: two structures M and N are elementarily equivalent (written M ≡ N) when they satisfy exactly the same set of first-order sentences. No formula in the language can tell them apart. They are, from the perspective of first-order logic, indistinguishable.

This is strictly weaker than isomorphism. Isomorphic structures are always elementarily equivalent — any sentence true in one is true in both, because an isomorphism is a perfect renaming. But the converse fails. Consider the ordered fields (ℝ, +, ·, <, 0, 1) and (ℚ, +, ·, <, 0, 1). These are not isomorphic — ℝ is uncountable and ℚ is countable, and no bijection preserving all operations exists. Yet they are also not elementarily equivalent: the sentence "∃x (x · x = 2)" is true in ℝ but false in ℚ. In contrast, the structures (ℚ, <) and (ℝ, <), viewed purely as dense linear orders without endpoints, *are* elementarily equivalent: every first-order sentence in the language {<} that holds in one holds in the other, because both are models of the complete theory DLO (dense linear order without endpoints).

The deeper point is that first-order logic has limited expressive power — it cannot always detect structural differences that we can see from the outside. Two structures can look different to a set-theorist but look identical to a first-order logician. For example, the standard model of arithmetic (ℕ, +, ·, 0, 1) has nonstandard models — structures that satisfy exactly the same first-order sentences as ℕ but contain elements that behave like "infinitely large" natural numbers. These nonstandard models are elementarily equivalent to ℕ but not isomorphic to it; the "extra" elements are invisible to any individual first-order sentence because first-order logic cannot quantify over all formulas simultaneously (this is essentially what Gödel's incompleteness theorems exploit).

Elementary equivalence is the central equivalence relation of model theory. It partitions the class of all structures into equivalence classes of first-order indistinguishability. A complete theory is one in which every sentence is either a theorem or its negation is — equivalently, all its models are elementarily equivalent. When you study a theory like DLO or the theory of algebraically closed fields of characteristic zero, you are studying a complete theory precisely because any two models of it are elementarily equivalent. This is what makes such theories mathematically clean: the logic fully determines the first-order content of the structure, even if it cannot determine the cardinality.

Practice Questions 5 questions

Prerequisite Chain

Understanding Zero → The Number Zero → Counting to Five → Counting to 10 → Counting to 20 → Counting a Set of Objects Up to 20 → Cardinality: The Last Number Counted → Matching Numerals to Quantities → Subitizing Small Quantities → Addition Within 10 → Number Bonds to 10 → Addition Within 20 → Doubles and Near Doubles → Doubles Facts Within 10 → Near Doubles Facts Within 20 → Mental Math Strategies for Addition → Mental Math: Adding and Subtracting Tens → Addition Within 100 → Repeated Addition as Multiplication → Multiplication as Equal Groups → Multiplication: Arrays → Basic Multiplication Facts (0s, 1s, 2s, 5s, 10s) → Multiplication Facts Within 100 → Division as Equal Sharing → Division as Grouping (Measurement Division) → Division: Grouping (Repeated Subtraction) Model → Division: Fair Sharing Model → Division as Equal Sharing → Division as Grouping → Basic Division Facts → Division Facts Within 100 → Multiplication and Division Fact Families → Relationship Between Multiplication and Division → Division Facts as Inverse of Multiplication → Remainders and Quotients in Division → Division Word Problems → Multi-Step Word Problems → Solving Multi-Step Word Problems → Multiplication Word Problems → Division Word Problems → Introduction to Long Division → Factors and Multiples → Prime and Composite Numbers → Equivalent Fractions → Relating Fractions and Decimals → Decimal Place Value → Integers and the Number Line → Comparing and Ordering Integers → Absolute Value → Adding Integers → Subtracting Integers → Multiplying Integers → Introduction to Exponents → Order of Operations → Integer Order of Operations → Variable Expressions → The Distributive Property → Variables and Expressions Review → Introduction to Polynomials → Adding and Subtracting Polynomials → Multiplying Polynomials → Factorial → Permutations → Combinations → Counting Principles: Addition and Multiplication Rules → Introduction to Graph Theory → Propositional Logic Foundations → Logical Equivalences → Boolean Algebra → Introduction to Propositional Logic → Introduction to Predicate Logic (First-Order Logic) → First-Order Logic Syntax → Terms and Atomic Formulas in FOL → Variable Binding and Scope → Open and Closed Formulas in First-Order Logic → Variable Substitution and Capture-Avoidance in First-Order Logic → Quantifier Instantiation Rules in First-Order Proof Systems → Universal Quantification: Meaning and Scope → Free Variables and Bound Variables → Substitution and Instantiation in Predicate Logic → Terms and Atomic Formulas → Formulas and Well-Formed Expressions → Structures and Interpretations → Model Interpretation and Satisfaction → Model Instantiation and Structure Realization → Embeddings and Preservation of Formulas → Isomorphisms and Structural Equivalence → Elementary Equivalence and Logical Indistinguishability

Longest path: 88 steps · 486 total prerequisite topics

Prerequisites (4)

Leads To (5)