Ehrenfeucht–Fraïssé games
Lax945089.EhrenfeuchtGames · concepts/Lax945089/EhrenfeuchtGames.lean · lax-945089
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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 and 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 rounds from a position when the position is legal and, if , whichever element the spoiler appends to one of the tuples, the duplicator can append an element to the other so as to survive rounds from the new position. The structures and are -round equivalent when the duplicator survives rounds from the empty position.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.ModelTheory.Semantics |
| 2 | import Mathlib.Data.Fin.Tuple.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Ehrenfeucht–Fraïssé games |
| 7 | type: definition |
| 8 | --- |
| 9 | The quantifier depth of a first-order formula is the maximal nesting of its |
| 10 | quantifiers. A position of the Ehrenfeucht–Fraïssé game on two structures |
| 11 | and over a relational vocabulary is a pair of tuples of the same |
| 12 | length, one in each structure; it is legal when the two tuples satisfy the |
| 13 | same equalities and the same atomic relations, that is, when matching them |
| 14 | coordinate by coordinate is a partial isomorphism. The duplicator survives |
| 15 | rounds from a position when the position is legal and, if , |
| 16 | whichever element the spoiler appends to one of the tuples, the duplicator |
| 17 | can append an element to the other so as to survive rounds from the |
| 18 | new position. The structures and are -round equivalent when the |
| 19 | duplicator survives rounds from the empty position. |
| 20 | -/ |
| 21 | |
| 22 | namespace Lax945089.EhrenfeuchtGames |
| 23 | |
| 24 | open FirstOrder |
| 25 | |
| 26 | open Language Structure |
| 27 | |
| 28 | /-- The quantifier depth of a bounded formula: the number of pebbles the |
| 29 | invariance argument spends on it. -/ |
| 30 | def 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 |
| 38 | length, one on each side, satisfying the same equalities between their |
| 39 | coordinates and the same base relations at every selection of coordinates. |
| 40 | Equivalently, matching coordinate to coordinate is a partial isomorphism. -/ |
| 41 | def 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` |
| 48 | says that from the position `(a, b)` the duplicator survives `n` further |
| 49 | rounds – the position is legal, and whichever element the spoiler appends on |
| 50 | either side, the duplicator can append one on the other and survive `n - 1` |
| 51 | more rounds. -/ |
| 52 | def 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 |
| 61 | Ehrenfeucht–Fraïssé game on `M` and `N` played from the empty position. -/ |
| 62 | def 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 | |
| 65 | end Lax945089.EhrenfeuchtGames |
| 66 |
Builds on
none
Used by
Lax945089.EhrenfeuchtMethodologyLax945089.EvenInvarianceLax945089.EvenNotFirstOrderLax945089.FirstOrderBelowACZeroLax945089.FirstOrderBelowTransitiveClosureLax945089.GamesOnLinearOrdersLax945089.GamesOnSetsLax945089.NoDefinableOrderLax945089.OrderFreeInductionMissesPTIMELax945089.ParityInLogSpaceLax945089.PebbleGamesLax945089.PebbleInvarianceLax945089.ReductionsBelowLogSpace
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments