While this submission is a draft, it cannot be used by other submissions.

Ehrenfeucht–Fraïssé games

Lax945089.EhrenfeuchtGames · concepts/Lax945089/EhrenfeuchtGames.lean · lax-945089

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    The quantifier depth of a first-order formula is the maximal nesting of its quantifiers. A position of the Ehrenfeucht–Fraïssé game on two structures MM and NN over a relational vocabulary is a pair of tuples of the same length, one in each structure; it is legal when the two tuples satisfy the same equalities and the same atomic relations, that is, when matching them coordinate by coordinate is a partial isomorphism. The duplicator survives nn rounds from a position when the position is legal and, if n>0n > 0, whichever element the spoiler appends to one of the tuples, the duplicator can append an element to the other so as to survive n−1n - 1 rounds from the new position. The structures MM and NN are nn-round equivalent when the duplicator survives nn rounds from the empty position.

    Concept map
    1 concept; 13 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.ModelTheory.Semantics
    2import Mathlib.Data.Fin.Tuple.Basic
    3
    4/-!
    5---
    6title: Ehrenfeucht–Fraïssé games
    7type: definition
    8---
    9The quantifier depth of a first-order formula is the maximal nesting of its
    10quantifiers. A position of the Ehrenfeucht–Fraïssé game on two structures
    11MM and NN over a relational vocabulary is a pair of tuples of the same
    12length, one in each structure; it is legal when the two tuples satisfy the
    13same equalities and the same atomic relations, that is, when matching them
    14coordinate by coordinate is a partial isomorphism. The duplicator survives
    15nn rounds from a position when the position is legal and, if n>0n > 0,
    16whichever element the spoiler appends to one of the tuples, the duplicator
    17can append an element to the other so as to survive n−1n - 1 rounds from the
    18new position. The structures MM and NN are nn-round equivalent when the
    19duplicator survives nn rounds from the empty position.
    20-/
    21
    22namespace Lax945089.EhrenfeuchtGames
    23
    24open FirstOrder
    25
    26open Language Structure
    27
    28/-- The quantifier depth of a bounded formula: the number of pebbles the
    29invariance argument spends on it. -/
    30def qdepth {L : Language.{0, 0}} {α : Type*} : ∀ {n : ℕ}, L.BoundedFormula α n → ℕ
    31 | _, .falsum => 0
    32 | _, .equal _ _ => 0
    33 | _, .rel _ _ => 0
    34 | _, .imp f₁ f₂ => max (qdepth f₁) (qdepth f₂)
    35 | _, .all f => qdepth f + 1
    36
    37/-- A **legal position** of the Ehrenfeucht–Fraïssé game: two tuples of equal
    38length, one on each side, satisfying the same equalities between their
    39coordinates and the same base relations at every selection of coordinates.
    40Equivalently, matching coordinate to coordinate is a partial isomorphism. -/
    41def PartialIso (L : Language.{0, 0}) {M N : Type} [L.Structure M] [L.Structure N] {j : ℕ}
    42 (a : Fin j → M) (b : Fin j → N) : Prop :=
    43 (∀ i i' : Fin j, a i = a i' ↔ b i = b i') ∧
    44 ∀ (l : ℕ) (R : L.Relations l) (g : Fin l → Fin j),
    45 ((RelMap R fun p => a (g p)) ↔ RelMap R fun p => b (g p))
    46
    47/-- **The stages of the Ehrenfeucht–Fraïssé refinement**: `efStage L n a b`
    48says that from the position `(a, b)` the duplicator survives `n` further
    49rounds – the position is legal, and whichever element the spoiler appends on
    50either side, the duplicator can append one on the other and survive `n - 1`
    51more rounds. -/
    52def efStage (L : Language.{0, 0}) {M N : Type} [L.Structure M] [L.Structure N] :
    53 ℕ → ∀ {j : ℕ}, (Fin j → M) → (Fin j → N) → Prop
    54 | 0, _, a, b => PartialIso L a b
    55 | n + 1, _, a, b =>
    56 PartialIso L a b ∧
    57 (∀ c : M, ∃ d : N, efStage L n (Fin.snoc a c) (Fin.snoc b d)) ∧
    58 (∀ d : N, ∃ c : M, efStage L n (Fin.snoc a c) (Fin.snoc b d))
    59
    60/-- **`n`-round equivalence**: the duplicator survives `n` rounds of the
    61Ehrenfeucht–Fraïssé game on `M` and `N` played from the empty position. -/
    62def EFEquiv (L : Language.{0, 0}) (M N : Type) [L.Structure M] [L.Structure N] (n : ℕ) : Prop :=
    63 efStage L n (default : Fin 0 → M) (default : Fin 0 → N)
    64
    65end Lax945089.EhrenfeuchtGames
    66

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…