Documentation

CombinatorialGames.Game.Small

Small games all around #

A small game is one that's smaller than all positive surreals, but larger than all negative surreals. The only small numeric games are zero, but surprisingly there are other non-numeric small games, such as the nimbers.

We prove that every dicotic game, and hence every impartial game is small. The former of these results is known as the lawnmower theorem.

TODO #

Prove that every small game lies between two dicotic games.

class IGame.Small (x : IGame) :

Small games lie between all the positive and negative surreals.

  • le_numeric_of_pos {y : IGame} [y.Numeric] : 0 < y → x ≤ y

    A small game is smaller than any positive numeric game.

  • numeric_le_of_neg {y : IGame} [y.Numeric] : y < 0 → y ≤ x

    A small game is larger than any negative numeric game.

Instances
    @[simp]
    theorem IGame.Small.lt_numeric_of_pos (x : IGame) {y : IGame} [x.Small] [y.Numeric] (h : 0 < y) :
    x < y
    theorem IGame.Small.numeric_lt_of_neg (x : IGame) {y : IGame} [x.Small] [y.Numeric] (h : y < 0) :
    y < x
    theorem IGame.Small.of_equiv {x y : IGame} (h : x ≈ y) [x.Small] :
    theorem IGame.Small.congr {x y : IGame} (h : x ≈ y) :
    instance IGame.Small.neg (x : IGame) [x.Small] :
    (-x).Small
    @[simp]
    instance IGame.Small.add (x y : IGame) [x.Small] [y.Small] :
    (x + y).Small
    instance IGame.Small.sub (x y : IGame) [x.Small] [y.Small] :
    (x - y).Small
    theorem IGame.Small.of_between (x y : IGame) {z : IGame} [x.Small] [y.Small] (h : z ∈ Set.Icc x y) :

    A game between two small games is small.

    @[simp]
    theorem IGame.leftStop_of_small (x : IGame) [x.Small] [x.Short] :
    @[simp]
    theorem IGame.Small.of_stops_eq_zero {x : IGame} [x.Short] (hl : x.leftStop = 0) (hr : x.rightStop = 0) :
    theorem IGame.Small.of_infinitesimal {x : IGame} [x.Short] (hl : ∀ y < 0, ↑y ≤ x) (hr : ∀ (y : Dyadic), 0 < y → x ≤ ↑y) :

    A short infinitesimal game is in fact small.

    theorem IGame.Small.lt_numeric_of_pos_of_forall_of_nonempty {x y : IGame} (hy : 0 < y) [y.Numeric] (h : ∀ (p : Player), ∀ y ∈ moves p x, y.Small) (hn : (moves right x).Nonempty) :
    x < y
    theorem IGame.Small.numeric_lt_of_neg_of_forall_of_nonempty {x y : IGame} (hy : y < 0) [y.Numeric] (h : ∀ (p : Player), ∀ y ∈ moves p x, y.Small) (hn : (moves left x).Nonempty) :
    y < x
    theorem IGame.Small.of_forall_of_nonempty {x : IGame} (h : ∀ (p : Player), ∀ y ∈ moves p x, y.Small) (hn : ∀ (p : Player), (moves p x).Nonempty) :
    @[irreducible]

    The lawnmower theorem: every dicotic game is small.

    @[simp]
    instance IGame.Small.ofSets_zero_left (x : IGame) [x.Small] :
    !{{0} | {x}}.Small
    @[simp]
    instance IGame.Small.ofSets_zero_right (x : IGame) [x.Small] :
    !{{x} | {0}}.Small
    @[simp]
    instance IGame.Small.tiny (x : IGame) [x.Small] :
    @[simp]
    instance IGame.Small.miny (x : IGame) [x.Small] :
    theorem IGame.Small.tiny_of_nonneg {x : IGame} (hx : 0 ≤ x) :
    theorem IGame.Small.miny_of_nonneg {x : IGame} (hx : 0 ≤ x) :