Documentation

CombinatorialGames.Form

def Moves.IsOption' {G : Type v} (moves : Player → G → Set G) (x y : G) :
Equations
Instances For
    class Moves (G : Type v) :
    Instances
      class Form (G : Type (v + 1)) extends Moves G, OfSets G fun (x : Player → Set G) => True, InvolutiveNeg G, AddCommSemigroup G :
      Type (v + 1)
      Instances
        def Moves.IsOption {G : Type (u + 1)} [g_moves : Moves G] (x y : G) :

        IsOption x y means that x is either a Left or a Right option for y.

        Equations
        Instances For
          theorem Moves.IsOption.iff_mem_union {G : Type (u + 1)} [g_moves : Moves G] {x y : G} :
          theorem Moves.IsOption.of_mem_moves {G : Type (u + 1)} [g_moves : Moves G] {x y : G} {p : Player} (h : x ∈ moves p y) :
          instance Moves.instSmallSubtypeIsOption {G : Type (u + 1)} [g_moves : Moves G] (x : G) :
          theorem Moves.isOption_wf {G : Type (u + 1)} [g_moves : Moves G] :
          theorem Moves.IsOption.irrefl {G : Type (u + 1)} [g_moves : Moves G] (x : G) :
          theorem Moves.self_notMem_moves {G : Type (u + 1)} [g_moves : Moves G] (p : Player) (x : G) :
          x ∉ moves p x
          def Moves.Subposition {G : Type (u + 1)} [g_moves : Moves G] :
          G → G → Prop

          A proper subposition is an element of the transitive closure of IsOption. Note that this is not the reflexive-transitive closure! While it is common to say that $G$ is a subposition of $G$ in the literature, here Subposition refers to a proper subposition.

          Equations
          Instances For
            theorem Moves.Subposition.of_isOption {G : Type (u + 1)} [g_moves : Moves G] {x y : G} (h : IsOption x y) :
            theorem Moves.Subposition.of_mem_moves {G : Type (u + 1)} [g_moves : Moves G] {p : Player} {x y : G} (h : x ∈ moves p y) :
            theorem Moves.Subposition.trans {G : Type (u + 1)} [g_moves : Moves G] {x y z : G} (h₁ : Subposition x y) (h₂ : Subposition y z) :
            instance Moves.instSmallSubtypeSubposition {G : Type (u + 1)} [g_moves : Moves G] (x : G) :
            instance Moves.instIsTransSubposition {G : Type (u + 1)} [g_moves : Moves G] :
            @[instance_reducible]
            instance Moves.instWellFoundedRelation {G : Type (u + 1)} [g_moves : Moves G] :
            Equations
            def Form.IsEnd {G : Type (u + 1)} [Moves G] (p : Player) (g : G) :
            Equations
            Instances For
              theorem Form.isEnd_def {G : Type (u + 1)} [Moves G] (p : Player) (g : G) :
              IsEnd p g = (moves p g = ∅)
              theorem Form.not_isEnd_def {G : Type (u + 1)} [Moves G] (p : Player) (g : G) :
              theorem Form.isEndLike_of_isEnd {G : Type (u + 1)} [g_form : Form G] {p : Player} {x : G} (h1 : IsEnd p x) :
              @[simp]
              theorem Form.IsEndLike.add_iff {G : Type (u + 1)} [g_form : Form G] {p : Player} {x y : G} :
              @[simp]
              theorem Form.IsEndLike.neg_iff_neg {G : Type (u + 1)} [g_form : Form G] {g : G} {p : Player} :
              @[simp]
              theorem Form.moves_neg {G : Type (u + 1)} [g_form : Form G] (p : Player) (x : G) :
              moves p (-x) = -moves (-p) x
              @[simp]
              theorem Form.moves_add {G : Type (u + 1)} [g_form : Form G] (p : Player) (x y : G) :
              moves p (x + y) = (fun (x : G) => x + y) '' moves p x ∪ (fun (x_1 : G) => x + x_1) '' moves p y
              instance Form.instSmallElemMoves {G : Type (u + 1)} [g_form : Form G] (p : Player) (x : G) :
              @[simp]
              theorem Form.moves_ofSets {G : Type (u + 1)} [g_form : Form G] (p : Player) (st : Player → Set G) [Small.{u, u + 1} ↑(st Player.left)] [Small.{u, u + 1} ↑(st Player.right)] :
              moves p !{st} = st p
              theorem Form.ofSets_moves_of_not_isEndLike {G : Type (u + 1)} [g_form : Form G] {g : G} (h : ∀ (p : Player), ¬IsEndLike p g) :
              !{fun (p : Player) => moves p g} = g

              Away from end-like positions, a form is determined by its sets of moves.

              @[simp]
              theorem Form.leftMoves_ofSets {G : Type (u + 1)} [g_form : Form G] (s t : Set G) [Small.{u, u + 1} ↑s] [Small.{u, u + 1} ↑t] :
              moves Player.left !{s | t} = s
              @[simp]
              theorem Form.rightMoves_ofSets {G : Type (u + 1)} [g_form : Form G] (s t : Set G) [Small.{u, u + 1} ↑s] [Small.{u, u + 1} ↑t] :
              moves Player.right !{s | t} = t
              @[simp]
              theorem Form.ofSets_inj' {G : Type (u + 1)} [g_form : Form G] {st₁ st₂ : Player → Set G} [Small.{u, u + 1} ↑(st₁ Player.left)] [Small.{u, u + 1} ↑(st₁ Player.right)] [Small.{u, u + 1} ↑(st₂ Player.left)] [Small.{u, u + 1} ↑(st₂ Player.right)] :
              !{st₁} = !{st₂} ↔ st₁ = st₂
              theorem Form.ofSets_inj {G : Type (u + 1)} [g_form : Form G] {s₁ s₂ t₁ t₂ : Set G} [Small.{u, u + 1} ↑s₁] [Small.{u, u + 1} ↑s₂] [Small.{u, u + 1} ↑t₁] [Small.{u, u + 1} ↑t₂] :
              !{s₁ | t₁} = !{s₂ | t₂} ↔ s₁ = s₂ ∧ t₁ = t₂
              @[instance_reducible]
              instance Form.instZero {G : Type (u + 1)} [g_form : Form G] :
              Equations
              theorem Form.zero_def {G : Type (u + 1)} [g_form : Form G] :
              0 = !{fun (x : Player) => ∅}
              @[simp]
              theorem Form.moves_zero {G : Type (u + 1)} [g_form : Form G] (p : Player) :
              moves p 0 = ∅
              @[simp]
              theorem Form.isEnd_zero {G : Type (u + 1)} [g_form : Form G] {p : Player} :
              IsEnd p 0
              def Form.IsZeroLike {G : Type (u + 1)} [g_form : Form G] (g : G) :

              A form is zero-like if it is both a Left and a Right end, just like 0.

              Equations
              Instances For
                @[simp]
                theorem Form.isZeroLike_zero {G : Type (u + 1)} [g_form : Form G] :
                @[simp]
                theorem Form.neg_ofSets {G : Type (u + 1)} [g_form : Form G] (s t : Set G) [Small.{u, u + 1} ↑s] [Small.{u, u + 1} ↑t] :
                -!{s | t} = !{-t | -s}
                @[simp]
                theorem Form.neg_ofSets_const {G : Type (u + 1)} [g_form : Form G] (s : Set G) [Small.{u, u + 1} ↑s] :
                -!{fun (x : Player) => s} = !{fun (x : Player) => -s}
                @[instance_reducible]
                instance Form.instNegZeroClass {G : Type (u + 1)} [g_form : Form G] :
                Equations
                @[instance_reducible]
                instance Form.instInhabited {G : Type (u + 1)} [g_form : Form G] :
                Equations
                @[instance_reducible]
                instance Form.instOne {G : Type (u + 1)} [g_form : Form G] :
                One G
                Equations
                theorem Form.one_def {G : Type (u + 1)} [g_form : Form G] :
                1 = !{{0} | ∅}
                @[simp]
                theorem Form.leftMoves_one {G : Type (u + 1)} [g_form : Form G] :
                @[simp]
                theorem Form.rightMoves_one {G : Type (u + 1)} [g_form : Form G] :
                @[simp]
                theorem Form.moves_small {G : Type (u + 1)} [g_form : Form G] (p : Player) (x : G) :
                theorem Form.exists_moves_neg {G : Type (u + 1)} [g_form : Form G] {P : G → Prop} {p : Player} {x : G} :
                (∃ y ∈ moves p (-x), P y) ↔ ∃ y ∈ moves (-p) x, P (-y)
                @[simp]
                theorem Form.IsEnd.add_iff {G : Type (u + 1)} [g_form : Form G] {g h : G} {p : Player} :
                IsEnd p (g + h) ↔ IsEnd p g ∧ IsEnd p h
                theorem Form.IsEnd.neg_iff_neg {G : Type (u + 1)} [g_form : Form G] {g : G} {p : Player} :
                IsEnd p (-g) ↔ IsEnd (-p) g
                theorem Form.mem_moves_ne_zero {G : Type (u + 1)} [g_form : Form G] {g gl : G} {p : Player} (h1 : gl ∈ moves p g) :
                g ≠ 0
                theorem Form.not_isEnd_ne_zero {G : Type (u + 1)} [g_form : Form G] {g : G} {p : Player} (h1 : ¬IsEnd p g) :
                g ≠ 0
                theorem Form.not_isEnd_exists_move {G : Type (u + 1)} [g_form : Form G] {g : G} {p : Player} (h1 : ¬IsEnd p g) :
                ∃ (gp : G), gp ∈ moves p g
                @[simp]
                theorem Form.not_mem_moves_of_isEnd {G : Type (u + 1)} [g_form : Form G] {p : Player} {g gp : G} (h1 : IsEnd p g) :
                gp ∉ moves p g
                theorem Form.not_isEnd_of_mem_moves {G : Type (u + 1)} [g_form : Form G] {p : Player} {g g' : G} (h1 : g' ∈ moves p g) :
                theorem Form.not_isEnd_add_left {G : Type (u + 1)} [g_form : Form G] {p : Player} {g h : G} (h_not_isEnd : ¬IsEnd p g) :
                ¬IsEnd p (g + h)
                theorem Form.not_isEnd_add_right {G : Type (u + 1)} [g_form : Form G] {p : Player} {g h : G} (h_not_isEnd : ¬IsEnd p h) :
                ¬IsEnd p (g + h)
                theorem Form.add_left_mem_moves_add {G : Type (u + 1)} [g_form : Form G] {p : Player} {x y : G} (h : x ∈ moves p y) (z : G) :
                z + x ∈ moves p (z + y)
                theorem Form.add_right_mem_moves_add {G : Type (u + 1)} [g_form : Form G] {p : Player} {x y : G} (h : x ∈ moves p y) (z : G) :
                x + z ∈ moves p (y + z)
                @[instance_reducible]
                instance Form.instAddCommMonoid {G : Type (u + 1)} [g_form : Form G] :
                Equations
                • One or more equations did not get rendered due to their size.
                @[instance_reducible]
                instance Form.instSubNegMonoid {G : Type (u + 1)} [g_form : Form G] :
                Equations
                • One or more equations did not get rendered due to their size.
                @[instance_reducible]
                instance Form.instAddCommMonoidWithOne {G : Type (u + 1)} [g_form : Form G] :
                Equations
                theorem Form.sub_left_mem_moves_sub {G : Type (u + 1)} [g_form : Form G] {p : Player} {x y : G} (h : x ∈ moves p y) (z : G) :
                z - x ∈ moves (-p) (z - y)
                theorem Form.sub_left_mem_moves_sub_neg {G : Type (u + 1)} [g_form : Form G] {p : Player} {x y : G} (h : x ∈ moves (-p) y) (z : G) :
                z - x ∈ moves p (z - y)
                theorem Form.sub_right_mem_moves_sub {G : Type (u + 1)} [g_form : Form G] {p : Player} {x y : G} (h : x ∈ moves p y) (z : G) :
                x - z ∈ moves p (y - z)
                theorem Form.exists_moves_add {G : Type (u + 1)} [g_form : Form G] {p : Player} {P : G → Prop} {x y : G} :
                (∃ a ∈ moves p (x + y), P a) ↔ (∃ a ∈ moves p x, P (a + y)) ∨ ∃ b ∈ moves p y, P (x + b)
                theorem Form.isOption_iff_mem_union {G : Type (u + 1)} [g_form : Form G] {x y : G} :
                theorem Form.isOption_iff_mem_moves {G : Type (u + 1)} [g_form : Form G] {x y : G} :
                IsOption x y ↔ ∃ (p : Player), x ∈ moves p y
                @[simp]
                theorem Form.not_isOption_zero {G : Type (u + 1)} [g_form : Form G] (g : G) :
                @[simp]
                theorem Form.isOption_zero_neg_iff {G : Type (u + 1)} [g_form : Form G] {g : G} :
                theorem Form.isOption_not_mem {G : Type (u + 1)} [g_form : Form G] {p : Player} {g g' : G} (h_isOption : IsOption g' g) (h_mem : g' ∉ moves p g) :
                g' ∈ moves (-p) g
                theorem Form.isOption_not_mem_neg {G : Type (u + 1)} [g_form : Form G] {p : Player} {g g' : G} (h_isOption : IsOption g' g) (h_mem : g' ∉ moves (-p) g) :
                g' ∈ moves p g
                theorem Form.leftMoves_natCast_succ' {G : Type (u + 1)} [g_form : Form G] (n : ℕ) :
                @[simp]
                theorem Form.leftMoves_natCast_succ {G : Type (u + 1)} [g_form : Form G] (n : ℕ) :
                moves Player.left (↑n + 1) = {↑n}
                @[simp]
                theorem Form.rightMoves_natCast {G : Type (u + 1)} [g_form : Form G] (n : ℕ) :
                @[simp]
                theorem Form.leftMoves_ofNat {G : Type (u + 1)} [g_form : Form G] (n : ℕ) [n.AtLeastTwo] :
                @[simp]
                theorem Form.rightMoves_ofNat {G : Type (u + 1)} [g_form : Form G] (n : ℕ) [n.AtLeastTwo] :
                @[instance_reducible]
                instance Form.instIntCast {G : Type (u + 1)} [g_form : Form G] :
                Equations
                @[simp]
                theorem Form.intCast_nat {G : Type (u + 1)} [g_form : Form G] (n : ℕ) :
                ↑↑n = ↑n
                @[simp]
                theorem Form.intCast_ofNat {G : Type (u + 1)} [g_form : Form G] (n : ℕ) :
                ↑(OfNat.ofNat n) = ↑n
                @[simp]
                theorem Form.intCast_negSucc {G : Type (u + 1)} [g_form : Form G] (n : ℕ) :
                ↑(Int.negSucc n) = -(↑n + 1)
                theorem Form.intCast_zero {G : Type (u + 1)} [g_form : Form G] :
                ↑0 = 0
                theorem Form.intCast_one {G : Type (u + 1)} [g_form : Form G] :
                ↑1 = 1
                theorem Form.natCast_zero {G : Type (u + 1)} [g_form : Form G] :
                ↑0 = 0
                theorem Form.natCast_one {G : Type (u + 1)} [g_form : Form G] :
                ↑1 = 1
                @[simp]
                theorem Form.intCast_neg {G : Type (u + 1)} [g_form : Form G] (n : ℤ) :
                ↑(-n) = -↑n
                @[simp]
                theorem Form.leftMoves_eq_natCast_zero_lt {G : Type (u + 1)} [g_form : Form G] {a : ℕ} (h1 : 0 < a) :
                moves Player.left ↑a = {↑(a - 1)}
                theorem Form.leftMoves_natCast_zero_lt {G : Type (u + 1)} [g_form : Form G] {a : ℕ} (h1 : 0 < a) :
                ↑(a - 1) ∈ moves Player.left ↑a
                @[simp]
                theorem Form.leftMoves_intCast_succ {G : Type (u + 1)} [g_form : Form G] {n : ℤ} (h1 : 0 ≤ n) :
                moves Player.left (↑n + 1) = {↑n}
                @[simp]
                theorem Form.leftMoves_intCast {G : Type (u + 1)} [g_form : Form G] {a : ℤ} (h1 : 0 < a) :
                moves Player.left ↑a = {↑(a - 1)}
                theorem Form.leftMoves_intCast_zero_lt {G : Type (u + 1)} [g_form : Form G] {a : ℤ} (h1 : 0 < a) :
                ↑(a - 1) ∈ moves Player.left ↑a
                theorem Form.leftMoves_intCast_zero_le_succ {G : Type (u + 1)} [g_form : Form G] {a : ℤ} (h1 : 0 ≤ a) :
                ↑a ∈ moves Player.left ↑(a + 1)
                theorem Form.leftMoves_intCast_le_zero_of_empty {G : Type (u + 1)} [g_form : Form G] {k : ℤ} (h1 : 0 ≤ k) (h2 : moves Player.left ↑k = ∅) :
                k = 0
                theorem Form.leftMoves_intCast_le_one_eq {G : Type (u + 1)} [g_form : Form G] {a : ℤ} (h1 : 1 ≤ a) :
                moves Player.left ↑a = {↑(a - 1)}
                @[simp]
                theorem Form.leftMoves_intCast_le_one_ne_empty {G : Type (u + 1)} [g_form : Form G] {a : ℤ} (h1 : 1 ≤ a) :
                @[simp]
                theorem Form.rightMoves_intCast {G : Type (u + 1)} [g_form : Form G] {a : ℤ} (h1 : 0 ≤ a) :
                theorem Form.mem_moves_add_one_iff_mem_moves {G : Type (u + 1)} [g_form : Form G] {g : G} {p : Player} {n : ℕ} :
                g + 1 ∈ moves p (↑n + 1) ↔ g ∈ moves p ↑n
                @[simp]
                theorem Form.one_isEnd_right {G : Type (u + 1)} [g_form : Form G] :
                @[simp]
                theorem Form.not_isEnd_left_one {G : Type (u + 1)} [g_form : Form G] :
                @[simp]
                theorem Form.natCast_isEnd_right {G : Type (u + 1)} [g_form : Form G] (n : ℕ) :
                @[simp]
                theorem Form.ofSets_isEndLike_iff {G : Type (u + 1)} [g_form : Form G] {p : Player} {s t : Set G} [Small.{u, u + 1} ↑s] [Small.{u, u + 1} ↑t] :
                IsEndLike p !{s | t} ↔ IsEnd p !{s | t}
                theorem Form.ofSets_add_ofSets {G : Type (u + 1)} [g_form : Form G] (s₁ t₁ s₂ t₂ : Set G) [Small.{u, u + 1} ↑s₁] [Small.{u, u + 1} ↑t₁] [Small.{u, u + 1} ↑s₂] [Small.{u, u + 1} ↑t₂] :
                !{s₁ | t₁} + !{s₂ | t₂} = !{(fun (x : G) => x + !{s₂ | t₂}) '' s₁ ∪ (fun (x : G) => !{s₁ | t₁} + x) '' s₂ | (fun (x : G) => x + !{s₂ | t₂}) '' t₁ ∪ (fun (x : G) => !{s₁ | t₁} + x) '' t₂}
                theorem Form.ofSets_add_ofSets' {G : Type (u + 1)} [g_form : Form G] (st₁ st₂ : Player → Set G) [Small.{u, u + 1} ↑(st₁ Player.left)] [Small.{u, u + 1} ↑(st₂ Player.left)] [Small.{u, u + 1} ↑(st₁ Player.right)] [Small.{u, u + 1} ↑(st₂ Player.right)] :
                !{st₁} + !{st₂} = !{fun (p : Player) => (fun (x : G) => x + !{st₂}) '' st₁ p ∪ (fun (x : G) => !{st₁} + x) '' st₂ p}
                theorem Form.natCast_add_one_ofSets {G : Type (u + 1)} [g_form : Form G] {n : ℕ} :
                ↑(n + 1) = !{{↑n} | ∅}
                @[simp]
                theorem Form.natCast_isEndLike_iff {G : Type (u + 1)} [g_form : Form G] {p : Player} {n : ℕ} :
                IsEndLike p ↑n ↔ IsEnd p ↑n
                @[simp]
                theorem Form.one_isEndLike_right {G : Type (u + 1)} [g_form : Form G] :
                @[simp]
                theorem Form.not_isEndLike_left_one {G : Type (u + 1)} [g_form : Form G] :
                theorem Form.natCast_ext {G : Type (u + 1)} [g_form : Form G] {k m : ℕ} (h_moves : ∀ (p : Player) (gp : G), gp ∈ moves p ↑k ↔ gp ∈ moves p ↑m) :
                ↑k = ↑m
                @[simp]
                theorem Form.isEnd_left_natCast_iff {G : Type (u + 1)} [g_form : Form G] {n : ℕ} :
                @[simp]
                theorem Form.isEnd_left_intCast_iff {G : Type (u + 1)} [g_form : Form G] {n : ℤ} :
                @[simp]
                theorem Form.isEnd_right_intCast_iff {G : Type (u + 1)} [g_form : Form G] {n : ℤ} :
                @[simp]
                theorem Form.isEnd_right_natCast {G : Type (u + 1)} [g_form : Form G] {n : ℕ} :
                theorem Form.isEnd_of_not_mem {G : Type (u + 1)} [g_form : Form G] {p : Player} {g : G} (h1 : ∀ (gr : G), gr ∉ moves p g) :
                IsEnd p g
                instance Form.instCharZero {G : Type (u + 1)} [g_form : Form G] :
                theorem Form.eq_sub_one_of_mem_leftMoves_intCast {G : Type (u + 1)} [g_form : Form G] {n : ℤ} {x : G} (hx : x ∈ moves Player.left ↑n) :
                x = ↑(n - 1)
                theorem Form.eq_add_one_of_mem_rightMoves_intCast {G : Type (u + 1)} [g_form : Form G] {n : ℤ} {x : G} (hx : x ∈ moves Player.right ↑n) :
                x = ↑(n + 1)
                theorem Form.eq_intCast_of_mem_leftMoves_intCast {G : Type (u + 1)} [g_form : Form G] {n : ℤ} {x : G} (hx : x ∈ moves Player.left ↑n) :
                ∃ m < n, ↑m = x

                Every Left option of an integer is equal to a smaller integer.

                theorem Form.eq_intCast_of_mem_rightMoves_intCast {G : Type (u + 1)} [g_form : Form G] {n : ℤ} {x : G} (hx : x ∈ moves Player.right ↑n) :
                ∃ (m : ℤ), n < m ∧ ↑m = x
                theorem Form.succ_nat_end_right {G : Type (u + 1)} [g_form : Form G] {p : Player} {n : ℕ} :
                theorem Form.nat_forall_moves {G : Type (u + 1)} [g_form : Form G] {n : ℕ} {P : G → Prop} (h1 : P ↑n) (p : Player) (gp : G) :
                gp ∈ moves p ↑n.succ → P gp

                If P holds at n, then P holds at every option of n+1 (since n is the only such option).

                @[simp]
                theorem Form.add_eq_zero_iff {G : Type (u + 1)} [g_form : Form G] {x y : G} :
                x + y = 0 ↔ x = 0 ∧ y = 0
                @[instance_reducible]
                instance Form.instSubtractionCommMonoid {G : Type (u + 1)} [g_form : Form G] :
                Equations
                • One or more equations did not get rendered due to their size.
                @[simp]
                theorem Form.IsEnd.sub_iff {G : Type (u + 1)} [g_form : Form G] {g h : G} {p : Player} :
                IsEnd p (g - h) ↔ IsEnd p g ∧ IsEnd (-p) h
                theorem Form.mem_leftMoves_natSub_add_isEnd {G : Type (u + 1)} [g_form : Form G] {a b : ℕ} {y g' : G} (hye : IsEnd Player.left y) :
                g' ∈ moves Player.left (↑a - ↑b + y) ↔ ∃ (a' : ℕ), a = a' + 1 ∧ g' = ↑a' - ↑b + y
                theorem Form.mem_rightMoves_natSub_add {G : Type (u + 1)} [g_form : Form G] {a b : ℕ} {y g' : G} :
                g' ∈ moves Player.right (↑a - ↑b + y) ↔ (∃ (b' : ℕ), b = b' + 1 ∧ g' = ↑a - ↑b' + y) ∨ ∃ yr ∈ moves Player.right y, g' = ↑a - ↑b + yr