5.1 Definition and properties of elementary equivalence

Elementary equivalence is a powerful tool in model theory for comparing structures based on their logical properties. It allows us to identify structures that share the same first-order sentences, even if they're not isomorphic.

This concept plays a crucial role in understanding the relationships between mathematical structures. It helps us analyze how different structures can have similar logical behaviors, which is essential in various branches of math and computer science.

Elementary Equivalence of Structures

Definition and Notation

Top images from around the web for Definition and Notation

• 

  Set notation - Dave Tang's blog View original

  Is this image relevant?

• 

  A fresh look for the standard model - Theory And Practice View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

• 

  Set notation - Dave Tang's blog View original

  Is this image relevant?

• 

  A fresh look for the standard model - Theory And Practice View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Notation

• 

  Set notation - Dave Tang's blog View original

  Is this image relevant?

• 

  A fresh look for the standard model - Theory And Practice View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

• 

  Set notation - Dave Tang's blog View original

  Is this image relevant?

• 

  A fresh look for the standard model - Theory And Practice View original

  Is this image relevant?

1 of 3

• Elementary equivalence compares truth of sentences between two structures in model theory
• Two structures A and B are elementarily equivalent when they satisfy same sentences in first-order language L
• Notation A ≡ B denotes structures A and B are elementarily equivalent
• Applies to structures with same signature (language)
• Relies on satisfaction (⊨) in model theory (A ⊨ φ means sentence φ is true in structure A)
• Considers all first-order sentences (includes quantifiers and logical connectives)
• Extends to theories (two theories elementarily equivalent if same models up to elementary equivalence)

Scope and Application

• Fundamental concept in model theory for comparing structures
• Allows comparison of structures based on their logical properties
• Useful for analyzing relationships between different mathematical structures
• Helps identify structures with similar logical behavior
• Applied in various branches of mathematics (algebra, analysis, topology)
• Used in computer science for formal verification and database theory
• Provides framework for studying properties preserved under certain transformations

Properties of Elementary Equivalence

Basic Properties

• Reflexivity establishes every structure A is elementarily equivalent to itself (A ≡ A)
• Symmetry shows if A is elementarily equivalent to B, then B is elementarily equivalent to A (A ≡ B implies B ≡ A)
• Transitivity demonstrates if A ≡ B and B ≡ C, then A ≡ C
• These properties establish elementary equivalence as equivalence relation on class of structures with given signature
• Proofs rely on definition of elementary equivalence and basic logical principles
• Law of excluded middle crucial in proving properties (ensures for any sentence φ, either φ or its negation true in structure)

Advanced Properties and Implications

• Preservation of cardinality not guaranteed (elementarily equivalent structures may have different sizes)
• Elementarily equivalent structures share same theory (set of all sentences true in both structures)
• Downward Löwenheim-Skolem theorem applies (if infinite structure has elementarily equivalent structure, it has one of every infinite cardinality)
• Elementary equivalence preserves algebraic properties expressible in first-order logic (group axioms, field axioms)
• Topological properties not always preserved (connectedness, compactness may differ in elementarily equivalent structures)
• Elementarily equivalent structures may have different automorphism groups
• Preservation of model-theoretic properties (stability, saturation) between elementarily equivalent structures

Determining Elementary Equivalence

Analytical Methods

• Comparison of truth values systematically checks if both structures satisfy same sentences in given language
• Elementary diagrams construction and comparison determines equivalence
• Ehrenfeucht-Fraïssé games apply game-theoretic techniques to establish elementary equivalence
• Automorphism arguments utilize structure automorphisms to prove or disprove elementary equivalence
• Quantifier elimination compares structures based on quantifier-free formulas in applicable theories
• Ultraproduct construction establishes elementary equivalence in certain cases
• Model-theoretic invariants analysis distinguishes structures based on preserved properties under elementary equivalence

Practical Approaches and Examples

• Direct sentence comparison (check truth of specific sentences in both structures)
• Induction on formula complexity (prove equivalence for atomic formulas, then build up)
• Use of elementary extensions (show structures have isomorphic elementary extensions)
• Partial isomorphisms method (construct family of partial isomorphisms between structures)
• Analysis of definable sets (compare sets definable by formulas in both structures)
• Examination of elementary substructures (compare elementary substructures of given structures)
• Application to specific mathematical structures (number systems, algebraic structures, ordered sets)

Elementary Equivalence vs Isomorphism

Relationship and Distinctions

• Isomorphism implies elementary equivalence (isomorphic structures necessarily elementarily equivalent)
• Converse not true (elementary equivalence does not imply isomorphism in general)
• Łoś-Vaught Test states for countable structures, elementary equivalence with no finite models implies isomorphism
• Categoricity in categorical theory means all models of same cardinality are isomorphic (strengthens connection between elementary equivalence and isomorphism)
• Saturation and homogeneity can bridge gap between elementary equivalence and isomorphism in certain cases
• Back-and-forth method establishes both isomorphism and elementary equivalence (highlights their relationship)
• Limitations of first-order logic unable to distinguish between elementarily equivalent non-isomorphic structures (motivates study of stronger logics)

Examples and Applications

• Real closed fields ($\mathbb{R}$ and $\mathbb{R}_{\text{alg}}$ elementarily equivalent but not isomorphic)
• Dense linear orders without endpoints ($\mathbb{Q}$ and $\mathbb{R}$ elementarily equivalent but not isomorphic)
• Infinite models of Peano arithmetic (elementarily equivalent models of different cardinalities)
• Algebraically closed fields (elementarily equivalent fields of same characteristic may not be isomorphic)
• Atomless Boolean algebras (elementarily equivalent but may have different cardinalities)
• Ultraproducts (often elementarily equivalent to their factors but not necessarily isomorphic)
• Non-standard models of arithmetic (elementarily equivalent to standard model but not isomorphic)