5.2 Partial isomorphisms and back-and-forth constructions

Partial isomorphisms and back-and-forth constructions are powerful tools for comparing structures in model theory. They allow us to map subsets between structures while preserving relations and operations, helping us understand similarities and differences.

These techniques are crucial for proving elementary equivalence between structures. By building sequences of partial isomorphisms, we can show that two structures share the same first-order properties, even if they're not fully isomorphic.

Partial Isomorphisms for Structures

Definition and Properties

Top images from around the web for Definition and Properties

• 

  Group homomorphism - Online Dictionary of Crystallography View original

  Is this image relevant?

• 

  File:Graphs for isomorphism explanation.svg - Wikimedia Commons View original

  Is this image relevant?

• 

  Codomain - Wikipedia View original

  Is this image relevant?

• 

  Group homomorphism - Online Dictionary of Crystallography View original

  Is this image relevant?

• 

  File:Graphs for isomorphism explanation.svg - Wikimedia Commons View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Properties

• 

  Group homomorphism - Online Dictionary of Crystallography View original

  Is this image relevant?

• 

  File:Graphs for isomorphism explanation.svg - Wikimedia Commons View original

  Is this image relevant?

• 

  Codomain - Wikipedia View original

  Is this image relevant?

• 

  Group homomorphism - Online Dictionary of Crystallography View original

  Is this image relevant?

• 

  File:Graphs for isomorphism explanation.svg - Wikimedia Commons View original

  Is this image relevant?

1 of 3

• Partial isomorphisms create bijective mappings between subsets of two structures preserving relations and operations within their domains
• Finite subsets of the respective structures form the domain and codomain of a partial isomorphism
• Preserve atomic formulas and their negations for all elements in their domain
• Composition of two partial isomorphisms yields another partial isomorphism when the codomain of the first matches the domain of the second
• Inverse of a partial isomorphism maintains the isomorphism property
• Extend partial isomorphisms by adding elements to their domain and codomain while preserving the isomorphism property

Mathematical Foundations

• Formally define partial isomorphisms as functions $f: A \rightarrow B$ where $A \subseteq M$ and $B \subseteq N$ for structures $M$ and $N$
• Satisfy the condition: For any atomic formula $\phi(x_1, \ldots, x_n)$ and elements $a_1, \ldots, a_n \in A$, $M \models \phi(a_1, \ldots, a_n)$ if and only if $N \models \phi(f(a_1), \ldots, f(a_n))$
• Closure properties include restriction (submap of a partial isomorphism remains a partial isomorphism)
• Partial isomorphisms form a category with structures as objects and partial isomorphisms as morphisms

Examples and Applications

• In graph theory, partial isomorphisms map subgraphs while preserving edge relations (vertex mappings between isomorphic subgraphs)
• For algebraic structures, partial isomorphisms preserve operations on subsets (mapping between subgroups of two groups)
• In model theory, use partial isomorphisms to compare finite substructures of models (analyzing local similarities between different models of a theory)

Back-and-Forth Systems for Equivalence

Definition and Properties

• Back-and-forth systems create families of partial isomorphisms between two structures satisfying specific extension properties
• "Forth" property extends any partial isomorphism in the system to include any element from the domain structure
• "Back" property extends any partial isomorphism in the system to include any element from the codomain structure
• Systems remain non-empty and closed under restrictions to subsets of the domain and codomain
• Existence of a back-and-forth system between two structures implies their elementary equivalence
• Construct back-and-forth systems incrementally by alternating between "forth" and "back" steps
• Construction process ensures eventual inclusion of all elements in both structures in some partial isomorphism within the system

Mathematical Formalization

• Define a back-and-forth system $I$ between structures $M$ and $N$ as a set of partial isomorphisms satisfying:
  1. $I$ is non-empty
  2. For any $f \in I$ and $a \in M$, there exists $g \in I$ with $f \subseteq g$ and $a \in dom(g)$ (forth property)
  3. For any $f \in I$ and $b \in N$, there exists $g \in I$ with $f \subseteq g$ and $b \in range(g)$ (back property)
• Prove that the existence of a back-and-forth system implies elementary equivalence using induction on formula complexity

Applications and Examples

• Use back-and-forth systems to prove elementary equivalence of dense linear orders without endpoints (rational numbers and real numbers)
• Apply back-and-forth systems to show elementary equivalence of algebraically closed fields of the same characteristic and infinite transcendence degree
• Employ back-and-forth systems in computer science for bisimulation in process algebras and transition systems

Back-and-Forth Constructions for Equivalence

Construction Process

• Build isomorphisms between countable structures or establish elementary equivalence between uncountable structures
• Involve infinite sequence of steps, alternating between extending the domain and the codomain of partial isomorphisms
• Extend partial isomorphism at each step to include a new element while preserving the isomorphism property
• Ensure eventual inclusion of every element in both structures in the domain or codomain of some partial isomorphism
• For countable structures, union of all partial isomorphisms in the construction yields a full isomorphism between the structures
• Prove elementary equivalence for uncountable structures without necessarily producing a full isomorphism
• Adapt back-and-forth method to prove stronger forms of equivalence (potential isomorphism or $L_{\omega_1\omega}$-equivalence)

Mathematical Details

• For countable structures $M = \{a_0, a_1, \ldots\}$ and $N = \{b_0, b_1, \ldots\}$, construct a sequence of partial isomorphisms $f_0 \subseteq f_1 \subseteq \ldots$
• At odd steps $2n+1$, extend $f_n$ to include $a_n$ in its domain
• At even steps $2n+2$, extend $f_{n+1}$ to include $b_n$ in its range
• Define the full isomorphism as $f = \bigcup_{n<\omega} f_n$
• For uncountable structures, use transfinite induction to construct a family of partial isomorphisms indexed by ordinals

Examples and Applications

• Apply back-and-forth construction to prove Cantor's theorem on the uniqueness of countable dense linear orders without endpoints
• Use back-and-forth method to show elementary equivalence of infinite atomic Boolean algebras
• Employ back-and-forth construction in descriptive set theory to prove the Cantor-Bendixson theorem

Role of Partial Isomorphisms in Equivalence

Theoretical Foundations

• Provide finite approximation of the full elementary equivalence relation between structures
• Existence of arbitrarily large partial isomorphisms between structures implies their elementary equivalence
• Use partial isomorphisms to construct Ehrenfeucht-Fraïssé games, characterizing elementary equivalence in terms of winning strategies
• Allow local analysis of structural similarities between models, focusing on finite substructures
• Form the basis for various model-theoretic concepts (n-equivalence and partial isomorphism classes)
• Reveal limitations in the expressive power of first-order logic (elementarily equivalent structures may not be isomorphic)
• Play crucial role in proving preservation theorems and characterizing classes of structures definable in various logics

Applications in Model Theory

• Use partial isomorphisms to define Scott rank of structures, measuring their complexity
• Apply partial isomorphisms in the study of categoricity in infinitary logics
• Employ partial isomorphisms to analyze the expressive power of different logical formalisms (first-order vs. infinitary logics)
• Utilize partial isomorphisms in the investigation of model-theoretic properties (stability, simplicity, NIP)

Connections to Other Areas

• Relate partial isomorphisms to bisimulation in modal logic and process algebra
• Apply partial isomorphisms in finite model theory for analyzing the expressive power of query languages in databases
• Use partial isomorphisms in theoretical computer science for studying the complexity of graph isomorphism problems