Eliminating one priority by a fixed point
Lax369799.ParityFixedPoints · concepts/Lax369799/ParityFixedPoints.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Stop a finite parity game on a set of vertices with priority p. A stopped vertex is winning precisely when the player can force a successor in the parameter set. Repeated visits to that priority select a greatest fixed point when p is even and a least fixed point when p is odd. Priorities above p are allowed only at absorbing vertices; this permits the result to be iterated with previously stopped priorities.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ParityWinningRegions |
| 2 | import Mathlib.Order.FixedPoints |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Eliminating one priority by a fixed point |
| 7 | type: theorem |
| 8 | --- |
| 9 | Stop a finite parity game on a set of vertices with priority p. A stopped |
| 10 | vertex is winning precisely when the player can force a successor in the |
| 11 | parameter set. Repeated visits to that priority select a greatest fixed |
| 12 | point when p is even and a least fixed point when p is odd. Priorities |
| 13 | above p are allowed only at absorbing vertices; this permits the result |
| 14 | to be iterated with previously stopped priorities. |
| 15 | -/ |
| 16 | namespace Lax369799.ParityFixedPoints |
| 17 | open FiniteParityGames ParityWinningRegions |
| 18 | attribute [local instance] Classical.propDecidable |
| 19 | |
| 20 | def Owned {V : Type} (G : Game V) (player : Bool) (v : V) : Prop := |
| 21 | G.eve v ↔ player = true |
| 22 | |
| 23 | def pre {V : Type} (G : Game V) (player : Bool) (X : Set V) : Set V := |
| 24 | {v | (Owned G player v → ∃ w, G.edge v w ∧ w ∈ X) ∧ |
| 25 | (¬ Owned G player v → ∀ w, G.edge v w → w ∈ X)} |
| 26 | |
| 27 | noncomputable def stop {V : Type} (G : Game V) (C W : Set V) : Game V where |
| 28 | eve := G.eve |
| 29 | edge := fun v w => if v ∈ C then w = v else G.edge v w |
| 30 | priority := fun v => if v ∈ C then if v ∈ W then 0 else 1 else G.priority v |
| 31 | total := by |
| 32 | classical |
| 33 | intro v |
| 34 | by_cases h : v ∈ C |
| 35 | · exact ⟨v, by simp [h]⟩ |
| 36 | · obtain ⟨w, hw⟩ := G.total v |
| 37 | exact ⟨w, by simp [h, hw]⟩ |
| 38 | |
| 39 | noncomputable def phase {V : Type} (G : Game V) (C : Set V) (player : Bool) |
| 40 | (X : Set V) : Game V := |
| 41 | stop G C {v | v ∈ pre G player X ↔ player = true} |
| 42 | |
| 43 | axiom greatest {V : Type} [Finite V] (G : Game V) (C : Set V) (p : ℕ) |
| 44 | (hC : ∀ v ∈ C, G.priority v = p) |
| 45 | (hbound : ∀ v, p < G.priority v → ∀ w, G.edge v w → w = v) |
| 46 | (hp : Even p) : (Winning G true : Set V) = (sSup {X : Set V | X ⊆ Winning (phase G C true X) true} : Set V) |
| 47 | |
| 48 | axiom least {V : Type} [Finite V] (G : Game V) (C : Set V) (p : ℕ) |
| 49 | (hC : ∀ v ∈ C, G.priority v = p) |
| 50 | (hbound : ∀ v, p < G.priority v → ∀ w, G.edge v w → w = v) |
| 51 | (hp : ¬ Even p) : (Winning G true : Set V) = (sInf {X : Set V | Set.Subset (Winning (phase G C true X) true) X} : Set V) |
| 52 | |
| 53 | end Lax369799.ParityFixedPoints |
| 54 |
Builds on
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments