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 moreBack-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 ZeroThe Number ZeroCounting to FiveCounting to 10Counting to 20Counting a Set of Objects Up to 20Cardinality: The Last Number CountedMatching Numerals to QuantitiesSubitizing Small QuantitiesAddition Within 10Number Bonds to 10Addition Within 20Doubles and Near DoublesDoubles Facts Within 10Near Doubles Facts Within 20Mental Math Strategies for AdditionMental Math: Adding and Subtracting TensAddition Within 100Repeated Addition as MultiplicationMultiplication as Equal GroupsMultiplication: ArraysBasic Multiplication Facts (0s, 1s, 2s, 5s, 10s)Multiplication Facts Within 100Division as Equal SharingDivision as Grouping (Measurement Division)Division: Grouping (Repeated Subtraction) ModelDivision: Fair Sharing ModelDivision as Equal SharingDivision as GroupingBasic Division FactsDivision Facts Within 100Multiplication and Division Fact FamiliesRelationship Between Multiplication and DivisionDivision Facts as Inverse of MultiplicationRemainders and Quotients in DivisionDivision Word ProblemsMulti-Step Word ProblemsSolving Multi-Step Word ProblemsMultiplication Word ProblemsDivision Word ProblemsIntroduction to Long DivisionFactors and MultiplesPrime and Composite NumbersEquivalent FractionsRelating Fractions and DecimalsDecimal Place ValueIntegers and the Number LineComparing and Ordering IntegersAbsolute ValueAdding IntegersSubtracting IntegersMultiplying IntegersIntroduction to ExponentsOrder of OperationsInteger Order of OperationsVariable ExpressionsThe Distributive PropertyVariables and Expressions ReviewIntroduction to PolynomialsAdding and Subtracting PolynomialsMultiplying PolynomialsFactorialPermutationsCombinationsCounting Principles: Addition and Multiplication RulesIntroduction to Graph TheoryPropositional Logic FoundationsLogical EquivalencesBoolean AlgebraIntroduction to Propositional LogicIntroduction to Predicate Logic (First-Order Logic)First-Order Logic SyntaxTerms and Atomic Formulas in FOLVariable Binding and ScopeOpen and Closed Formulas in First-Order LogicVariable Substitution and Capture-Avoidance in First-Order LogicQuantifier Instantiation Rules in First-Order Proof SystemsUniversal Quantification: Meaning and ScopeFree Variables and Bound VariablesSubstitution and Instantiation in Predicate LogicTerms and Atomic FormulasFormulas and Well-Formed ExpressionsStructures and InterpretationsModel Interpretation and SatisfactionModel Instantiation and Structure RealizationEmbeddings and Preservation of FormulasIsomorphisms and Structural EquivalenceElementary Equivalence and Logical Indistinguishability

Longest path: 88 steps · 486 total prerequisite topics

Prerequisites (4)

Leads To (5)