Game functor

The type of games IGame is an inductive type, with a single constructor ofSets taking in two small sets of games (one for each player) and outputting a new game. This suggests the definition:

inductive IGame : Type (u + 1)
  | ofSets (st : Player → Set IGame) [Small.{u} (st left)] [Small.{u} (st right)] : IGame

However, the kernel does not accept this, as Set IGame = IGame → Prop contains a non-positive occurence of IGame (see counterexamples.org for an explanation of what this is and why it's disallowed). We can get around this technical limitation using the machinery of QPFs (quotients of polynomial functors). We define a functor GameFunctor by

def GameFunctor (α : Type (u + 1)) : Type (u + 1) :=
  {st : Player → Set α // Small.{u} (st left) ∧ Small.{u} (st right)}

We can prove that this is a QPF, which then allows us to build its initial algebra through QPF.Fix, which is exactly the inductive type IGame. As a bonus, we're able to describe the coinductive type of loopy games LGame as the final coalgebra QPF.Cofix of the exact same functor.

Game Functor

def GameFunctor (α : Type (u + 1)) : Type (u + 1)

The functor from a type into the subtype of small pairs of sets in that type.

This is the quotient of a polynomial functor. The type IGame of well-founded games is defined as the initial algebra of that QPF, while the type LGame of loopy games is defined as its final coalgebra.

In other words, IGame and LGame have the following descriptions (which don't work verbatim due to various Lean limitations):

inductive IGame : Type (u + 1)
  | ofSets (st : Player → Set IGame) [Small.{u} (st left)] [Small.{u} (st right)] : IGame

coinductive LGame : Type (u + 1)
  | ofSets (st : Player → Set IGame) [Small.{u} (st left)] [Small.{u} (st right)] : LGame

Equations

• GameFunctor α = { s : Player → Set α // ∀ (p : Player), Small.{?u.9, ?u.9 + 1} ↑(s p) }

theorem GameFunctor.ext {α : Type (u + 1)} {x y : GameFunctor α} : ↑x = ↑y → x = y

theorem GameFunctor.ext_iff {α : Type (u + 1)} {x y : GameFunctor α} : x = y ↔ ↑x = ↑y

instance GameFunctor.instSmallElemValForallPlayerSetForall {α : Type (u + 1)} (x : GameFunctor α) (p : Player) : Small.{u, u + 1} ↑(↑x p)

instance GameFunctor.instFunctor : Functor GameFunctor

Equations

• GameFunctor.instFunctor = { map := fun {α β : Type (?u.19 + 1)} (f : α → β) (s : GameFunctor α) => ⟨fun (x : Player) => f '' ↑s x, ⋯⟩ }

theorem GameFunctor.map_def {α β : Type (u_1 + 1)} (f : α → β) (s : GameFunctor α) : f <$> s = ⟨fun (x : Player) => f '' ↑s x, ⋯⟩

noncomputable instance GameFunctor.instQPF : QPF GameFunctor

Equations

• One or more equations did not get rendered due to their size.