🧠Model Theory Unit 5 – Elementary Equivalence and Isomorphism

Key Concepts and Definitions

• Elementary equivalence two structures satisfy the same first-order sentences
• Isomorphism a bijective function between two structures that preserves relations and functions
• First-order logic a formal system for reasoning about structures using logical connectives, quantifiers, and variables
• Signature a set of symbols used to define a structure, including constant symbols, function symbols, and relation symbols
• Theory a set of first-order sentences closed under logical consequence
  • Complete theory a theory that contains either $\phi$ or $\neg\phi$ for every sentence $\phi$
• Axiomatization a set of sentences that generate a theory
• Compactness theorem if every finite subset of a set of sentences has a model, then the entire set has a model

Formal Language and Structures

• Formal language consists of a set of symbols and rules for combining them into well-formed formulas
  • Symbols include variables, constant symbols, function symbols, and relation symbols
  • Rules specify how to form terms, atomic formulas, and complex formulas using logical connectives and quantifiers
• Structure an interpretation of a formal language, consisting of a domain and interpretations for the symbols
  • Domain a non-empty set of elements
  • Interpretation assigns meaning to the symbols, mapping constant symbols to elements, function symbols to functions, and relation symbols to relations
• Satisfaction a structure $\mathcal{A}$ satisfies a formula $\phi$ if $\phi$ is true in $\mathcal{A}$ under every variable assignment
• Model a structure that satisfies a set of sentences
• Homomorphism a function between two structures that preserves relations and functions
• Embedding an injective homomorphism

Elementary Equivalence Explained

• Elementary equivalence two structures $\mathcal{A}$ and $\mathcal{B}$ are elementarily equivalent if they satisfy the same first-order sentences
  • Denoted $\mathcal{A} \equiv \mathcal{B}$
• Elementarily equivalent structures may have different underlying sets and functions but behave the same way with respect to first-order properties
• Elementary equivalence is weaker than isomorphism isomorphic structures are always elementarily equivalent, but the converse is not true
• Fraïssé's theorem two structures are elementarily equivalent if and only if they have isomorphic ultrapowers
• Elementary extension a structure $\mathcal{B}$ is an elementary extension of $\mathcal{A}$ if $\mathcal{A}$ is a substructure of $\mathcal{B}$ and $\mathcal{A} \equiv \mathcal{B}$
  • Denoted $\mathcal{A} \preceq \mathcal{B}$
• Löwenheim-Skolem theorem if a countable first-order theory has an infinite model, then it has models of every infinite cardinality
  • Upward Löwenheim-Skolem theorem if a theory has an infinite model, then it has models of arbitrarily large cardinality
  • Downward Löwenheim-Skolem theorem if a theory has an infinite model, then it has a countable model

Isomorphism Basics

• Isomorphism a bijective function $f: \mathcal{A} \to \mathcal{B}$ between two structures that preserves relations and functions
  • For every constant symbol $c$, $f(c^\mathcal{A}) = c^\mathcal{B}$
  • For every function symbol $g$ and tuple $\bar{a}$ in $\mathcal{A}$, $f(g^\mathcal{A}(\bar{a})) = g^\mathcal{B}(f(\bar{a}))$
  • For every relation symbol $R$ and tuple $\bar{a}$ in $\mathcal{A}$, $\bar{a} \in R^\mathcal{A}$ if and only if $f(\bar{a}) \in R^\mathcal{B}$
• Isomorphic structures have the same cardinality and are structurally identical
• Isomorphism is an equivalence relation it is reflexive, symmetric, and transitive
• Automorphism an isomorphism from a structure to itself
• Categoricity a theory is categorical in a cardinal $\kappa$ if all models of the theory of cardinality $\kappa$ are isomorphic
  • $\aleph_0$-categorical theory has a unique countable model up to isomorphism
• Rigid structure a structure with no non-trivial automorphisms

Comparing Elementary Equivalence and Isomorphism

• Isomorphism implies elementary equivalence isomorphic structures satisfy the same first-order sentences
• Elementary equivalence does not imply isomorphism elementarily equivalent structures may not be isomorphic
  • Example dense linear orders $(\mathbb{Q}, <)$ and $(\mathbb{R}, <)$ are elementarily equivalent but not isomorphic
• Elementary equivalence preserves first-order properties, while isomorphism preserves all properties expressible in the language
• Isomorphic structures are indistinguishable within the language, while elementarily equivalent structures may have different higher-order properties
• Elementary equivalence is a coarser notion of similarity than isomorphism it identifies more structures as "the same"
• Isomorphism is a structural notion, while elementary equivalence is a logical notion

Proof Techniques and Examples

• Back-and-forth method to prove elementary equivalence, construct a sequence of partial isomorphisms between the structures
  • Forth for every element in the first structure, find a corresponding element in the second structure that satisfies the same formulas
  • Back for every element in the second structure, find a corresponding element in the first structure that satisfies the same formulas
• Ehrenfeucht-Fraïssé games a game-theoretic characterization of elementary equivalence
  • Players alternate choosing elements from two structures
  • The second player wins if the chosen elements satisfy the same atomic formulas
  • Structures are elementarily equivalent if and only if the second player has a winning strategy for all game lengths
• Ultraproducts a construction that combines a family of structures into a single structure using an ultrafilter
  • Łoś's theorem a first-order sentence holds in an ultraproduct if and only if it holds in almost all component structures
• Quantifier elimination a theory has quantifier elimination if every formula is equivalent to a quantifier-free formula
  • Structures of theories with quantifier elimination are elementarily equivalent if and only if they satisfy the same atomic sentences
• Examples
  • Dense linear orders $(\mathbb{Q}, <)$ and $(\mathbb{R}, <)$ are elementarily equivalent (back-and-forth)
  • Algebraically closed fields of the same characteristic are elementarily equivalent (Łoś's theorem and ultraproducts)
  • Real closed fields are elementarily equivalent to $(\mathbb{R}, +, \times, 0, 1, <)$ (quantifier elimination)

Applications in Model Theory

• Classification theory studies the structure and properties of models of a theory
  • Stability theory investigates stable theories, where types over sets have unique non-forking extensions
  • Simplicity theory generalizes stability to simple theories, where types over sets have amalgamation properties
• Homogeneous structures structures where any isomorphism between finite substructures extends to an automorphism
  • Fraïssé limits a method for constructing countable homogeneous structures as limits of finite structures
• O-minimality studies ordered structures where every definable subset of the domain is a finite union of points and intervals
  • O-minimal structures have tame topological and geometric properties
• Valued fields structures equipped with a valuation map that measures the "size" of elements
  • Model theory of valued fields has applications in algebraic and arithmetic geometry
• Model-theoretic algebra applies model-theoretic techniques to study algebraic structures
  • Examples groups, rings, modules, and fields
• Model-theoretic geometry studies geometric structures using model-theoretic tools
  • Examples algebraic, differential, and o-minimal geometry

Common Pitfalls and Misconceptions

• Confusing elementary equivalence and isomorphism elementary equivalence is weaker than isomorphism
• Assuming elementary equivalence preserves all properties it only preserves first-order properties
• Misinterpreting the role of cardinality elementary equivalence does not depend on cardinality, while isomorphism does
• Overestimating the strength of first-order logic many properties (e.g., finiteness, completeness) are not first-order expressible
• Underestimating the complexity of model-theoretic constructions ultraproducts, Fraïssé limits, and other constructions can be technically challenging
• Neglecting the importance of the signature and language the choice of signature determines which structures are elementarily equivalent or isomorphic
• Misapplying compactness and Löwenheim-Skolem theorems these theorems have specific hypotheses that must be met
• Ignoring the limitations of quantifier elimination not all theories have quantifier elimination, and it may not be possible to eliminate quantifiers effectively