Winning regions and controlled predecessors
Lax369799.ParityWinningRegions · concepts/Lax369799/ParityWinningRegions.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The two positional winning regions of a finite parity game partition its vertices. A single strategy wins throughout each region. Since parity is unaffected by a finite prefix, the winning region is stable under the corresponding controlled predecessor operation.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteParityGames |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Winning regions and controlled predecessors |
| 6 | type: theorem |
| 7 | --- |
| 8 | The two positional winning regions of a finite parity game partition its |
| 9 | vertices. A single strategy wins throughout each region. Since parity is |
| 10 | unaffected by a finite prefix, the winning region is stable under the |
| 11 | corresponding controlled predecessor operation. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.ParityWinningRegions |
| 15 | open FiniteParityGames |
| 16 | |
| 17 | def Winning {V : Type} (G : Game V) (player : Bool) (v : V) : Prop := |
| 18 | ∃ f, G.Legal player f ∧ G.WinsFrom player f v |
| 19 | |
| 20 | def Pre {V : Type} (G : Game V) (X : Set V) : Set V := |
| 21 | {v | (G.eve v → ∃ w, G.edge v w ∧ w ∈ X) ∧ |
| 22 | (¬ G.eve v → ∀ w, G.edge v w → w ∈ X)} |
| 23 | |
| 24 | axiom move {V : Type} (G : Game V) (player : Bool) (f : V → V) (v w : V) |
| 25 | (hv : G.WinsFrom player f v) (he : G.edge v w) |
| 26 | (hf : (G.eve v ↔ player = true) → w = f v) : G.WinsFrom player f w |
| 27 | |
| 28 | axiom disjoint {V : Type} (G : Game V) (v : V) : |
| 29 | ¬ (Winning G true v ∧ Winning G false v) |
| 30 | |
| 31 | axiom uniform {V : Type} [Finite V] (G : Game V) (player : Bool) : |
| 32 | ∃ f, G.Legal player f ∧ ∀ v, Winning G player v → G.WinsFrom player f v |
| 33 | |
| 34 | axiom complementary {V : Type} [Finite V] (G : Game V) (v : V) : |
| 35 | Winning G false v ↔ ¬ Winning G true v |
| 36 | |
| 37 | axiom predecessor {V : Type} [Finite V] (G : Game V) (v : V) : |
| 38 | Winning G true v ↔ v ∈ Pre G (Winning G true) |
| 39 | |
| 40 | end Lax369799.ParityWinningRegions |
| 41 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments