duaLab

Games

Contents

A game records positions and legal moves. Game morphisms preserve the full set of options at each position.

1. Definition

Write $\mathcal{P}_{\mathrm{fin}}(X)$ for the set of finite subsets of a set $X$, the finite part of its power set.

Definition 1.1 (Objects)

A game is a coalgebra $\theta:X\to\mathcal{P}_{\mathrm{fin}}(X)$ on a set $X$ of positions. Its moves $x\to y$ are given by $y\in\theta(x)$, and there is no infinite chain of moves.

Definition 1.2 (Morphisms)

Between games $(X,\theta_X)$ and $(Y,\theta_Y)$, a game morphism is a function $h:X\to Y$ satisfying, for every $x\in X$,

$$ \theta_Y(h(x))=\{h(u)\mid u\in\theta_X(x)\}. $$

Composition and identities are those of functions.

2. Examples

Example 2.1 (Empty game)

There are no positions.

Example 2.2 (One-position game)

There is a single position with no legal moves.

Example 2.3 (One-heap Nim)

The positions are $\mathbb{N}=\{0,1,2,\ldots\}$. Put $\theta(0)=\varnothing$ and $\theta(n)=\{0,\ldots,n-1\}$ for $n>0$. See Example 3.11 in the original paper.

3. Recursive characterization

Proposition 3.1★

A coalgebra $\theta:X\to\mathcal{P}_{\mathrm{fin}}(X)$ is a game if and only if it is recursive. Equivalently, for every set $A$ and algebra $\alpha:\mathcal{P}_{\mathrm{fin}}(A)\to A$, there is a unique function $f:X\to A$ with

$$ f(x)=\alpha(\{f(u)\mid u\in\theta(x)\}). $$

Proof

See Proposition 3.10 in the original paper.

4. Properties

Proposition 4.1 (Finite generation)★

Every subgame generated by finitely many positions is finite.

Proof

See Lemma B.6.

Proposition 4.2 (Local finite presentability)★

Games is locally finitely presentable, and its finitely presentable objects are precisely the finite games. Every game is the filtered colimit of its finite subgames.

Proof

See Lemmas B.7–B.8 and Theorem B.9.

Proposition 4.3 (Coalgebra slice)★

Games is equivalent to the slice of the category of all $\mathcal{P}_{\mathrm{fin}}$-coalgebras over the terminal game of hereditarily finite sets.

Proof

A coalgebra mapping to that game has no infinite play: each move strictly decreases the finite rank of its image. Conversely, every game has a unique such map by Proposition 3.31.

Proposition 4.4 (Regularity and extensivity)☆

Games is regular and infinitary extensive. Its regular epimorphisms are precisely the surjective game morphisms.

Proof

The finite powerset functor is finitary and preserves weak pullbacks, so Worrell, Proposition 5.5.2 applies to its coalgebras. Pass to the coalgebra slice; regular epimorphisms are the underlying surjections.

Definition 4.5 (Finite-game nerve)

For a game $X$, its finite-game nerve is the presheaf on FinGames given by

$$ N(X)(A)=\mathbf{Games}(A,X)\qquad(A\text{ a finite game}). $$

The finite-game presentation identifies $N$ with the canonical embedding into Game topos. In particular, its values are sheaves for the topology on FinGames.

Proposition 4.6 (Full faithfulness and regularity)☆

$N$ is fully faithful and regular.

Proof

Apply Lack, Proposition 3.2 to the canonical embedding, using the finite-game presentation.

Proposition 4.7 (Subobjects)☆

For every game $X$, subgames $S\subseteq X$ correspond bijectively to subobjects of $N(X)$, via $S\mapsto N(S)$.

Proof

The canonical embedding has subobject-closed image by Lack, Lemma 3.1; subobjects of a game are its subgames by Proposition B.18.

Proposition 4.8 (Coproducts)☆

$N$ preserves all small coproducts.

Proof

The canonical embedding preserves coproducts of an infinitary extensive regular category by Vitale, p.237, Lemma (3).

6. References