On lattices from combinatorial game theory: infinite case

Abstract

Given a set of combinatorial games, the children are all those games that can be generated using as options the games of the original set. It is known that the partial order of the children of all games whose birthday is less than a fixed ordinal is a distributive lattice and also that the children of any set of games form a complete lattice. We are interested in the converse. In a previous paper, we showed that for any finite lattice there exists a finite set of games such that the partial order of the children, minus the top and bottom elements, is isomorphic to the original lattice. Here, the main part of the paper is to extend the result to infinite complete lattices. An original motivating question was to characterize those sets whose children generate distributive lattices. While we do not solve it, we show that if the process of taking children is iterated, eventually the corresponding lattice is distributive.

1 Introduction

Combinatorial games are games where two players move alternately, there are no chance moves, and there is perfect information (Albert et al. 2007; Berlekamp et al. 2001; Conway 1976; Siegel 2013). Using the normal-play convention, the loser is the first player who cannot move—that convention is the only one considered in this paper. The two players are called Left (female) and Right (male). Combinatorial games are determined recursively by their options. That is, $G =\{{G^{\mathcal {L}}}\,|\,{G^{\mathcal{R}}}\}$ is given by its set of Left and Right options, ${G^{\mathcal {L}}}$ and ${G^{\mathcal {R}}}$, respectively, where $G^L\in {G^{\mathcal {L}}}$ ($G^R\in {G^{\mathcal {R}}}$) is a typical Left (Right) option of G. The followers of G are the nodes in the game tree, including the game G, the options, the options of the options, etc. The sets ${G^{\mathcal {L}}}$ and ${G^{\mathcal {R}}}$ can be empty or infinite.

The possible outcomes of a game are ${\mathscr {L}}$, ${\mathscr {P}}$, ${\mathscr {N}}$, and ${\mathscr {R}}$: ${\mathscr {L}}$eft can force a win, regardless of moving first or second; ${\mathscr {R}}$ight can force a win, regardless of moving first or second; ${\mathscr {N}}$ext player can force a win regardless of whether this is Left or Right; ${\mathscr {P}}$revious player can force a win regardless of whether this is Left or Right. The outcome function o(G) is used to denote the outcome of G. By definition, the outcomes are partially ordered (Fig. 1).

Fig. 1

Partial order of outcomes

The outcome classes $\mathcal {L}, \mathcal {N}, \mathcal {R}, \mathcal {P}$ are the sets of all games with the indicated outcome, so that we can write $G\in \mathcal {L}$ when $o(G)={\mathscr {L}}$.

In game practice, games often decompose into components during play. In those situations, a player has to choose a component in which to play. This concept is called disjunctive sum: $G+H=\{{G^{\mathcal {L}}}+H,G+H^{\mathcal {L}}\,|\,{G^{\mathcal {R}}}+H,G+H^{\mathcal {R}}\}$. With the notions of outcome and disjunctive sum, the relations inequality and equivalence of games are defined by

$$\begin{aligned}&G \succcurlyeq H \text { if and only if } o(G+X)\geqslant o(H+X) \text { for all games } X;\\&G\sim H \text { if and only if } o(G+X)= o(H+X) \text { for all games } X. \end{aligned}$$

The first means that replacing H by G can never hurt Left, no matter what the sum is; the second means that G acts like H in any sum. In keeping with the literature, we will use $=$ for equivalence of games. The context will indicate if the symbol is being used for games or outcomes.

The negative of a game is obtained by “turning the game around”. Formally, $-G=\{-G^R_1,-G^R_2,\ldots \,|\, -G^L_1,-G^L_2,\ldots \}.$ It is well known that the class of games under the normal-play convention with the disjunctive sum $+$ and modulo equivalence $=$ is a partially ordered abelian group (Albert et al. 2007; Berlekamp et al. 2001; Conway 1976; Siegel 2013). The identity is $0=\{\emptyset \,|\,\emptyset \}$ or any equivalent game (that is, any game in $\mathcal {P}$), and the inverse of a game is its negative.

Also, regarding normal-play,

• $G=H$ iff $G-H\in \mathcal {P}$;

• $G\succ H$ iff $G-H\in \mathcal {L}$;

• $G\prec H$ iff $G-H\in \mathcal {R}$;

• $G\Vert H$ iff $G-H\in \mathcal {N}$.

There are two reductions: domination and reversibility. Given a game G, after all possible reductions, we get a unique simplest representative of the equivalence class [G], the canonical form of G (Albert et al. 2007; Berlekamp et al. 2001; Conway 1976; Siegel 2013).

Games, as mathematical objects, can be defined recursively, starting from the empty set. The game $\{\emptyset \,|\,\emptyset \}=0$ is the only game of day zero. Then, on day one, the “available material” is $\emptyset$ and 0. So, $1=\{0\,|\,\emptyset \}$, $-1=\{\emptyset \,|\,0\}$, and $*=\{0\,|\,0\}$ are born on day one. Because of that, 0, 1, $-1$, $*$ are the games born by day one, the first on day zero, and the others on day one. In Conway (1976), Conway observed that certain games are numbers. A positive integer n, for example, means that Left is n moves ahead in the game. There are also games that are not numbers.

Conway’s recursion starts from the empty set, so that the only game of day zero is $\{\emptyset \,|\,\emptyset \}=0$. Here we are interested in different initial sets (not only the empty set). In general, the recursion is formalized in the following definitions.

Definition 1

Let S be a set of games. The set $\mathbf {L}(S)$ of children of S is the set of games $G=\{{G^{\mathcal {L}}}\,|\,{G^{\mathcal {R}}}\}$ with ${G^{\mathcal {L}}}\subseteq S$ and ${G^{\mathcal {R}}}\subseteq S$.

Observation 1

“Children” in this context means the opposite to what it means in game trees. Also, it has nothing to do with the partial order of the lattice. Consider $S=\{*,1\}$. The children of S are the games “made” with $*$, 1, and $\emptyset$, that is, $\mathbf {L}(S)=\{\{\,|\,\},\{*\,|\,\},\{\,|\,*\},\{\,|1\},\{\,|*,1\},\{*\,|\,*\},\{*\,|\,1\},\{*\,|*,1\}\}\cup \{\{1\,|\,*\},\{1,*\,|\,*\},\{1,*\,|\,1,*\}\}\cup \{\{1\,|\,1\},\{1,*\,|\,1\}\}\cup \{\{1\,|\,\},\{1,*\,|\,\}\}$. After reductions, $\mathbf {L}(S)=\{0,\{1\,|\,*\},1*,2\}$. The Hasse diagram of $\mathbf {L}(S)$ is shown in Fig. 2.

Fig. 2

$\mathbf {L}(\{*,1\})$

Definition 2

Let $\mathbb {O}rd$ be the ordinal numbers. Let S be a set of games. We define

• 1. $\mathbf {L}^0(S)=\mathbf {L}(S)$;

• 2. $\mathbf {L}^\gamma (S)=\mathbf {L}(U)$ where $U=\{G\in \mathbf {L}^\delta (S):\delta <\gamma$ and $\delta ,\gamma \in \mathbb {O}rd\}$.

Observation 2

Conway’s recursion considers $S=\emptyset$ (Conway 1976).

Observation 3

In this paper, as usual in the literature, we consider $\mathbf {L}^\gamma$ modulo $=$; for example, the games $\{\,\mid \,\}$ and $\{\{0\mid 0\}\,\mid \,\{0\mid 0\}\}$ may be representatives of the same element of $\mathbf {L}^\gamma$ modulo $=$.

Observation 4

For purposes of induction, we say that G has birthday $\delta$, and write $b(G)=\delta$, if $\delta$ is the least index of the days on which G is born. A game G is said to be born by day $\delta$ if $b(G)\leqslant \delta$.

1.1 State of the art

A natural question is the following:

$$\begin{aligned} Given\,S,\,what\,can\,be\,said\,about\,the\,partial\,order\,of\,\mathbf {L}(S)? \end{aligned}$$

A seminal problem related to this question was to describe the poset of games born by day n. Or, equivalently, describe the structure of $\mathbf {L}^n(\emptyset )$. The answer was not given in Berlekamp et al. (2001) and Conway (1976). Figure 3 shows the day 1 poset and the left diagram in Fig. 4 the day 2 poset as given in Guy (1991, 1996), where ${*}=\{0\,\mid \,0\}$, $2=\{1\,|\,\}$, $1=\{0\,|\,\}$, $1{*}=\{1\,\mid \,1\}$, $\frac{1}{2}=\{0\,\mid \,1\}$, ${\uparrow }=\{0\,\mid \,{*}\}$, ${\uparrow }{*}=\{0,{*}\,\mid \,0\}$, $\pm 1=\{1\,\mid \,-1\}$.

Fig. 3

$\mathbf {L}^1(\emptyset )$

Fig. 4

Left: $\mathbf {L}^2(\emptyset )$, as given in Guy (1991); Right: $\mathbf {L}^2(\emptyset )$, corrected in Calistrate et al. (2002)

The Hasse diagram of $\mathbf {L}^2(\emptyset )$ given in Guy (1991) (shown on the left in Fig. 4) is incorrect; the game $\{1\,\mid \,0\}$ should be strictly larger than $\{1\,\mid \,0,*\}$. The actual poset is given on the right side of Fig. 4, which some readers will recognize as the free distributive lattice on 3 generators plus 4 more elements. The error was corrected in Calistrate et al. (2002), as stated in Theorem 5 below. We use the following notions from lattice theory:

• A lattice is a partially ordered set in which every two elements have a unique supremum ($a\vee b$, also called “least upper bound” or “join”) and a unique infimum ($a\wedge b$, also called “greatest lower bound” or “meet”). A lattice is distributive if $a\vee (b \wedge c)=(a\vee b)\wedge (a\vee c)$.

• A complete lattice is a poset in which all subsets have both a join and a meet.

• A modular lattice is a lattice that satisfies $x\leqslant b\Rightarrow x\vee (a\wedge b)=(x\vee a)\wedge b$.

Theorem 5

(Calistrate et al. 2002) The set of games born by day $n\in \mathbb {N}_0$ is a distributive lattice.

Also, the final theorem of Calistrate et al. (2002) states that the union of all day n games does not form a lattice.

In Albert and Nowakowski (2012), the ordered structure of $\mathbf {L}(S)$ was studied for any set S of games. Given a game G and a set of games S (G not necessarily in S), two important subsets are $\lfloor G \rfloor =\{J\in S:J\not \succcurlyeq G\}$ and $\lceil G \rceil =\{J\in S:J\not \preccurlyeq G\}$. The ideas of Calistrate et al. (2002) were extended and the following more general result was proved.

Theorem 6

(Albert and Nowakowski 2012) For any set of games S we have

• $\mathbf {L}(S)$ is a complete lattice;

• if $G\in \mathbf {L}(S)$ then $G=\{\,\lfloor G \rfloor \,|\,\lceil G \rceil \}$;

• $G\vee H=\{\lfloor G \rfloor \cup \lfloor H \rfloor \,|\,\lceil G \rceil \cap \lceil H \rceil \}$;

• $G\wedge H=\{\lfloor G \rfloor \cap \lfloor H \rfloor \,|\,\lceil G \rceil \cup \lceil H \rceil \}$.

The question “Which S give rise to distributive lattices?” was posed in Albert and Nowakowski (2012) and, based on limited evidence, the following conjecture seemed natural: If $\mathbf {L}^n(S)$ is modular then it is distributive (Nowakowski 2011).

1.2 Our contributions

The conjecture is false, as can be seen in Carvalho et al. (2014). In that paper, it was shown that for a given finite lattice L, there is a set of games S such that L is isomorphic to $\mathbf {L}(S)\setminus \{\bot ,\top \}$. The method used the meet irreducibles of the lattice.

In this paper, we present in Sect. 2 a more general method for infinite complete lattices (the method needs the Axiom of Choice Jech 2003). In that section, we prove Theorem 8, which states that all complete lattices can be generated when allowing for an extra top and an extra bottom element. The proof requires games that have infinite number of options but we show that the games in the base set S need only be of the form $-1$ and $\{2 \mid \{\text{ nimbers } \mid -2\} \}$. The nimbers are possibly transfinite (infinite nim heaps, see the end of Sect. 1).

We note that games with infinite numbers of options are not just abstract objects. For example, in the game sylver coinageSicherman (2002), on their turn, a player names a positive integer that is not a sum of multiples of previously named integers. A theorem of Sylvester’s implies that eventually the number of options becomes finite but there is no bound on how many turns that may take.

In Sect. 3, we give two examples that illustrate the techniques for infinite lattices.

In Sect. 4, we examine the difference between starting with the empty set and with an arbitrary set.

During their research, the authors of Albert and Nowakowski (2012) found sets such that $\mathbf {L}^n(S)\ne \mathbf {L}^m(\emptyset )$ for any finite n and m. This motivated the following general question:

$$\begin{aligned} For\,every\,set\,of\,games\,S,\,is\,there\,\gamma \in \mathbb {O}rd\,such\,that\,\mathbf {L}^\gamma (S)= \mathbf {L}^\gamma (\emptyset )? \end{aligned}$$

An affirmative answer would mean that Conway’s recursive construction is essential in the sense that every recursive process that begins with $S\ne \emptyset$ produces exactly the same games as the process that begins with the empty set. In Theorem 10, we prove that the answer is affirmative.

In the last section we include a brief discussion of other lattices that arise in combinatorial game theory, and pose some open questions.

1.3 Background and terminology

We finish this introductory section with some background to Set Theory (see Jech 2003) and its implications for Combinatorial Game Theory (Siegel 2013).

Definition 3

Let $\alpha \in \mathbb {O}rd$. If there is $\beta \in \mathbb {O}rd$ such that $\alpha$ = $\beta +1$, then $\alpha$ is a successor ordinal. If $\alpha$ is not a successor ordinal, then $\alpha =\sup \{\beta : \beta < \alpha \}$ is a limit ordinal. Also, 0 is a limit ordinal and $\sup \emptyset =0$.

Definition 4

$\alpha \in \mathbb {O}rd$ is additively indecomposable if it is not a sum of two smaller ordinals $\beta$ and $\xi$, i.e., $\beta ,\xi<\alpha \Rightarrow \beta +\xi <\alpha$. The class $\mathbb {H}$ (for “Hauptzahl” in German) is the proper class of the additively indecomposable ordinals.

Proposition 1

(See Pohlers 1992, p 48) The proper class $\mathbb {H}$ is unbounded.

$\mathbb {O}rd$ is not a set (by an argument similar to Russell’s paradox); it is a proper class, that is, a class that is not a set. More, every unbounded part of $\mathbb {O}rd$, in particular $\mathbb {H}$, is a proper class. If A is a proper class, and $f:A\longrightarrow B$ is an embedding, then B is also a proper class. This will be needed in Sect.  4.

A set $\{\xi \in \mathbb {O}rd:\xi <\alpha \}$ is an initial segment of $\mathbb {O}rd$. In order to prove Theorem 8, our main contribution, we need to relabel a complete lattice $(L ,\geqslant )$, maintaining the order, and using the elements of an initial segment of ordinals for labels. It is well known that a one-to-one correspondence is possible if we accept the Axiom of Choice, which is equivalent to the following theorem (Jech 2003, p 48).

Theorem 7

(Zermelo’s Well-Ordering Theorem) Every set S can be well-ordered, i.e., there is $\alpha \in \mathbb {O}rd$ and a one-to-one correspondence (enumeration) $\zeta :S\mapsto \{\xi \in \mathbb {O}rd:\xi <\alpha \}$.

Important Note: Instead of $\zeta :S\mapsto \{\xi \in \mathbb {O}rd:\xi <\alpha \}$, we will use the one-to-one correspondence $\lambda :S\mapsto \{\xi +1\in \mathbb {O}rd:\xi <\alpha \}$, where $\lambda (s)=\zeta (s)+1$.

Considering the classic game nim (Bouton 1901), the value of a finite heap of size n is called ${*}_n$ and formally ${*}_n = \{0, {*}_1, \ldots , {*}_{n-1}\, | \, 0, {*}_1, \ldots , {*}_{n-1}\}$. Central to our constructions are the transfinite nimbers. Let $\alpha \in \mathbb {O}rd$ and set $*_{\alpha } = \{\cup _{\beta<\alpha }*_{\beta } \,|\, \cup _{\beta <\alpha }*_{\beta } \}$. In this paper, when the word nimber occurs, it may be a transfinite nimber. Even though 0 is a nimber, our constructions have to avoid it. Note that any two different nimbers are not comparable and that ${*}_1$ is often shortened to ${*}$.

Notation: We write $\varDelta =\{{*}_{\alpha } \mid \alpha \text{ is } \text{ a } \text{ non-zero } \text{ ordinal } \}$ to designate the proper class of the fuzzy nimbers.

Our representation theorems use games such as $G=\{\{2|\{{*},{*}_2|-2\}\}|-1\}$, where $G^L=\{2\,|\,\{{*},{*}_2\,|\,-2\}\}$ is the Left only option of G. Using the above-mentioned reversibility, it is possible to argue that $G=\{{*},{*}_2\,|\,-1\}$, that is, $G^L$ may be replaced by ${*},{*}_2$.

2 Complete lattice representation theorem

In this section, we prove our main result.

Theorem 8

(Representation Theorem of CGT) Let $( L ,\geqslant )$ be a complete lattice. Then, for some set of games S, we have $L \cong \mathbf {L}(S)\setminus \{\bot ,\top \}$.

First, we present some results needed to prove the theorem. The basic idea is to establish the following composition:

$$\begin{aligned} \hbox {Lattice }L \rightarrow \mathop {\hbox {Family of sets}}\limits _{\hbox {(closed under unions)}} \rightarrow&\hbox {Lattice }\mathbf {L}(S)\setminus \{\bot ,\top \} \end{aligned}$$

The second part of the composition is based on results from Carvalho et al. (2014) that are true regardless of the cardinalities of the sets. We give these in Propositions 2, 3, 4, and 9.

Proposition 2

¹ Consider a family $\{J_A=\{A\,\mid \,-1\}:A \subset \varDelta \}$. Then,

• $J_A=J_B$ if and only if $A=B$;

• $J_A\succ J_B$ if and only if B is strictly contained in A;

• $J_A \Vert J_B$ if and only if $B\setminus A\ne \emptyset$ and $A\setminus B\ne \emptyset$.

Proof

Let us start with the second item. Consider $B\varsubsetneqq A$, subsets of $\varDelta$. It is easy to check that $J_A-J_B\succcurlyeq 0$ because, in the game $\{A\,\mid \,-1\}+\{1\,\mid \,B\}$, Left has a symmetric reply against every Right move. The inequality is strict because there is ${*}_\alpha$ such that ${*}_\alpha \in A$ and ${*}_\alpha \not \in B$. Hence, if Left goes first, she wins with ${*}_\alpha + \{1\,\mid \,B\}$.

On the other hand, if $J_A\succ J_B$, B must be contained in A. Also, there is a Left winning move in $J_A-J_B$ that must be some ${*}_\alpha + \{1\,\mid \,B\}$ with ${*}_\alpha \not \in B$. Hence, $B\varsubsetneqq A$.

The argument for the third item is similar because Left and Right winning moves are ${*}_\alpha + \{1\,\mid \,B\}$ and ${*}_\beta + \{A\,\mid \,-1\}$, with ${*}_\alpha \in A$ and ${*}_\alpha \not \in B$, and ${*}_\beta \not \in A$ and ${*}_\beta \in B$.

The first item complements the second and third items. $\square$

Example 1

$\{*,*_2,*_5\,\mid \,-1\}\succ \{*,*_5\,\mid \,-1\}$ — Left wins going first in $\{*,*_2,*_5\,\mid \,-1\}+\{1\,\mid \,*,*_5\}$ with $*_2+\{1\,\mid \,*,*_5\}$.

Example 2

$\{*,*_2,*_5\,\mid \,-1\}\Vert \{*,*_2,*_6\,\mid \,-1\}$ — Left wins going first in $\{*,*_2,*_5\,\mid \,-1\}+\{1\,\mid \,*,*_2,*_6\}$ with $*_5+\{1\,\mid \,*,*_2,*_6\}$; Right wins going first in $\{*,*_2,*_5\,\mid \,-1\}+\{1\,\mid \,*,*_2,*_6\}$ with $\{*,*_2,*_5\,\mid \,-1\}+*_6$.

The following definition points for the replacement of a set of options A by a single game $G_A$.

Definition 5

Let $\mathcal {F}$ be a family of subsets of $\varDelta$ closed under unions. Then, $\mathcal {F}^*$ is the set of games $\{G_A:G_A=\{2\,|\,\{A\,|\,-2\}\}$ and $A\in \mathcal {F}\}$, and $\mathcal {U}_{\mathcal {F}}=\{J_A: J_A=\{G_A\,|\,-1\} \text{ and } G_A\in \mathcal {F}^*\}.$

Example 3

Let $\mathcal {F}=\{\{*,*_2,*_3\},\{*,*_2,*_4\},\{*,*_3,*_4\},\{*,*_2,*_3,*_4\}\}$ ($\mathcal {F}$ is closed under unions). Then,

$\mathcal {F}^*=\{\{2\,|\,\{*,*_2,*_3\,|\,-2\}\},\{2\,|\,\{*,*_2,*_4\,|\,-2\}\},\{2\,|\,\{*,*_3,*_4\,|\,-2\}\}, \{2\,|\,\{*,*_2,*_3,*_4\,|\,-2\}\}\}$;

$\mathcal {U}_{\mathcal {F}}=\{\{\{2\mid \{*,*_2,*_3\mid -2\}\}\mid -1\},\{\{2\mid \{*,*_2,*_4\mid -2\}\}\mid -1\}, \{\{2\mid \{*,*_3,*_4\mid -2\}\}\mid -1\},\{\{2\mid \{*,*_2,*_3,*_4\mid -2\}\}\mid -1\}\}$.

After reductions (see Conway 1976; Berlekamp et al. 2001; Albert et al. 2007; Siegel 2013), we have

$\mathcal {U}_{\mathcal {F}}=\{\{*,*_2,*_3\mid -1\},\{*,*_2,*_4\mid -1\},\{*,*_3,*_4\mid -1\},\{*,*_2,*_3,*_4\mid -1\}\}$.

The proofs of the next three results can be found in Carvalho et al. (2014). The results are still valid when extended to the transfinite case (similar proofs). In each of the next three results, $\mathcal {F}$ is a family of subsets of $\varDelta$ closed under unions.

Proposition 3

Let $S=\mathcal {F}^*\cup \{-1\}$. Then, $\mathbf {L}(S)=\{-2,0\}\cup \left( \{-1{*}\}\cup \mathcal {U}_{\mathcal {F}}\right)$.

Proposition 4

Consider the set $S=\mathcal {F}^*\cup \{-1\}$. Then, $\{-1{*}\}\cup \mathcal {U}_{\mathcal {F}}$ is a sublattice of $\mathbf {L}(S)$.

Following, a rough sketch of the Hasse diagram of $\mathbf {L}(S)$ (Fig. 5).

Fig. 5

Hasse diagram of $\mathbf {L}(S)$

Example 4

Let $\mathcal {F}=\{\{*,*_2, *_3\},\{*,*_2, *_4\},\{*, *_3, *_4\},\{*,*_2,*_3,*_4\}\}$ and

$S=\mathcal {F}^*\cup \{-1\}$. Then, the Hasse diagram of $\mathbf {L}(S)$ is the following (Fig. 6):

Fig. 6

Hasse diagram of $\mathbf {L}(S)$ (Example 4)

Theorem 9

Consider the set of games $S=\mathcal {F}^*\cup \{-1\}$ and the family of sets $\mathcal {F}\cup \{\emptyset \}$. Consider the lattices $\left( \{-1{*}\}\cup \mathcal {U}_{\mathcal {F}},\leqslant \right)$, and $(\mathcal {F}\cup \{\emptyset \},\subseteq )$. Define the map

$$\begin{aligned} \psi :\{-1{*}\}\cup \mathcal {U}_{\mathcal {F}}\rightarrow \mathcal {F}\cup \{\emptyset \} \end{aligned}$$

where $\psi (-1{*})=\emptyset$; and $\psi (\{G_{A_1\cup A_2\cup \ldots \cup A_k}\,|\,-1\})= A_1\cup \ldots \cup A_k.$ Then $\psi$ is a order-preserving isomorphism.

Example 5

Let $\mathcal {F}=\{\{*,*_2, *_3\},\{*,*_2, *_4\},\{*, *_3, *_4\},\{*,*_2,*_3,*_4\}\}$.

A game like $\{\{2\,|\,\{*,*_2,*_3\,|\,-2\}\}\,|\,-1\}$ reduces to $\{*,*_2,*_3\,|\,-1\}$ and, as mentioned before, $\mathbf {L}^n$ is considered modulo $=$.

In Carvalho et al. (2014), the first part of the composition used a result involving the meet-irreducibles elements of $( L ,\geqslant )$. Regarding the infinite case, there may be no meet-irreducibles elements at all (see next section) and, so, we cannot use the same result. Fortunately, the concept of interior system comes to the rescue.

Definition 6

A family $\mathcal {I}$ of subsets of L is said to be an interior system if $\mathcal {I}$ is closed under unions, which means that, for all $\mathcal {H}\subseteq \mathcal {I}$, we have $\bigcup \mathcal {H}\in \mathcal {I}$. Note that $\bigcup \emptyset =\emptyset \in \mathcal {I}$.

Proposition 5

If $\mathcal {I}$ is an interior system then $(\mathcal {I},\subseteq )$ is a complete lattice.

Proof

Let $\mathcal {A}$ be a set of elements of $\mathcal {I}$. The following items are immediate.

• 1. $\bigvee \mathcal {A}=\bigcup \mathcal {A}$

• 2. $\bigwedge \mathcal {A}=\bigcup (B\in \mathcal {I}:B\subseteq \bigcap \mathcal {A})$

$\square$

Proposition 6

Let $(L,\geqslant )$ be a complete lattice. Then,

$$\begin{aligned} \mathcal {I}=\{\{x\in L:x\ngeqslant a\}:a\in L\} \end{aligned}$$

is an interior system.

Proof

To prove that $\bigcup _{a\in A\subseteq L }\{x\in L :x\ngeqslant a\}$ is in $\mathcal {I}$, it is enough to prove that $\bigcup _{a\in A\subseteq L }\{x\in L :x\ngeqslant a\}=\{x\in L :x\ngeqslant \bigvee A\}\in \mathcal {I}$. This follows because: (i) $x\ngeqslant \bigvee A$ if and only if for some $b\in A$, $x\ngeqslant b$; and (ii) the existence of $\bigvee A\in L$ is guaranteed because L is a complete lattice. $\square$

Proposition 7

Let $(L,\geqslant )$ be a complete lattice and

$$\begin{aligned} \mathcal {I}=\{\{x\in L :x\ngeqslant a\}:a\in L \}. \end{aligned}$$

Then, $(L,\geqslant )$ is isomorphic to the lattice structure $(\mathcal {I},\subseteq )$.

Proof

By Proposition 6, $\mathcal {I}=\{\{x\in L :x\ngeqslant a\}:a\in L \}$ is an interior system and, by Proposition 5, with $\subseteq$, it is a complete lattice.

Define the map $\varphi$: $a\in L \mapsto \{x\in L :x\not \geqslant a\}\in \mathcal {I}$. The map $\varphi$ is an order-preserving isomorphism because of the following facts.

• 1. Suppose $a\leqslant b$. If $x\not \geqslant a$ then it follows that $x\ngeqslant b$. On the other hand, if $b\leqslant x$ then $a\leqslant x$. Therefore,

  $$\begin{aligned} \varphi (a)=\{x\in L :x\ngeqslant a\}\subseteq \{x\in L :x\ngeqslant b\}=\varphi (b), \end{aligned}$$

  that is, $a\leqslant b\Rightarrow \varphi (a)\subseteq \varphi (b)$.

• 2. Suppose $\varphi (a)\subseteq \varphi (b)$, i.e., $\{x\in L :x\ngeqslant a\}\subseteq \{x\in L :x\ngeqslant b\}$ implies $a\leqslant b$.

  If $a\not \leqslant b$ then $a\not \in \{x\in L :x\ngeqslant a\}$ and $a\in \{x\in L :x\ngeqslant b\}$, a contradiction. Thus $a\leqslant b$.

$\square$

Example 6

We are ready to prove the main theorem.

Proof

(Representation Theorem.) First, we use the Axiom of Choice to relabel $(L,\geqslant )$. There is $\alpha \in \mathbb {O}rd$ and a one-to-one correspondence $\lambda :L\mapsto \{\xi +1\in \mathbb {O}rd:\xi <\alpha \}$. We consider $(\lambda (L),\geqslant )$ instead of $(L,\geqslant )$, defining the order of $(\lambda (L),\geqslant )$ so that $\lambda (l_1)\geqslant \lambda (l_2)$ in $(\lambda (L),\geqslant )$ iff $l_1\geqslant l_2$ in $(L,\geqslant )$.

Second, using Proposition 7, we have the isomorphism defined by

$$\begin{aligned} \varphi (a)=\{x\in \lambda (L) :x\ngeqslant a\}\,\,(a\in \lambda (L)). \end{aligned}$$

We have now the isomorphic lattice $(\varphi \lambda (L),\subseteq )$.

Third, let $\chi$ be the trivial isomorphism defined by

$$\begin{aligned} \chi (\{x\in \lambda (L) :x\ngeqslant a\})=\{*_x:x\in \lambda (L)\,\text {and}\,x\ngeqslant a\}. \end{aligned}$$

Note that $*_x$ are nimbers and $(\chi \varphi \lambda (L),\subseteq )$ is an interior system of sets of nimbers.

Fourth, by Theorem 9,

$$\begin{aligned} \psi ^{-1}:(\chi \varphi \lambda (L),\subseteq )\mapsto \left( \{-1{*}\}\cup \mathcal {U}_{\chi \varphi \lambda (L)\backslash \{\emptyset \}},\geqslant \right) \end{aligned}$$

is an isomorphism.

Let $\mathcal {F}=\chi \varphi \lambda (L)\backslash \{\emptyset \}$, and $S=\mathcal {F}^*\cup \{-1\}$. Then, $\psi ^{-1}\chi \varphi \lambda$ is an isomorphism mapping L to $\mathbf {L}(S)\setminus \{\bot ,\top \}$.$\square$

3 Two examples (infinite lattices)

In this section, we exemplify the application of Theorem 8 to infinite complete lattices.

Example 7

Consider the nonnegative integers with a partial order based on standard divisibility; $y\geqslant x$ when y divides x. We have $x\vee y=gcd(x,y)$ and $x\wedge y=lcm(x,y)$.

Applying Proposition 7, we have $\varphi (a)=\{x\in \mathbb {N}_0:x\not \mid a\}$. For every $a\in \mathbb {N}$, let $G_a=\{2\,|\,\{\bigcup _{x\not \mid a}\{*_{x+1}\}\,|\,-2\}\}$. Considering $S=(\bigcup _{a\in \mathbb {N}}\{G_a\})\cup \{-1\}$, we obtain $\mathbf {L}(S)$ where $\{\bigcup _{x\not \mid a}\{*_{x+1}\}\,|\,-1\}$ is at the “place” of $a\in \mathbb {N}$, $-1*$ is at the place of 0, an extra top (0), and an extra bottom ($-2$) (Fig. 7).

Fig. 7

Nonnegative integers — $y\geqslant x$ when y divides x

Example 8

The lattice $\overline{\mathbb {Q}}=\mathbb {Q}\cup \{-\infty ,+\infty \}$ with the standard total order is an infinite lattice, but not complete. For instance, $\{r\in \mathbb {Q}:r^2<2\}$ has no join or meet. The family $\mathcal {I}=\{\{x\in \overline{\mathbb {Q}}:x< a\}:a\in \overline{\mathbb {Q}}\}$ is not an interior system, and the representation presented in the last section fails. On the other hand, the lattice $\overline{\mathbb {R}}=\mathbb {R}\cup \{-\infty ,+\infty \}$ is complete and $\mathcal {I}=\{\{x\in \overline{\mathbb {R}}:x< a\}:a\in \overline{\mathbb {R}}\}$ is an interior system. Note that $+\infty$ is identified with $\mathbb {R}\cup \{-\infty \}$ and $-\infty$ is identified with $\emptyset$.

Applying Zermelo’s Well-Ordering Theorem, the reals are identified with $\varOmega =\{\xi \in \mathbb {O}rd:\xi <\omega _1\}$, where $\omega _1$ is the first uncountable ordinal. Each $r\in \mathbb {R}$ is identified with an ordinal $\rho _r\in \varOmega$. For every $r\in \mathbb {R}$, consider the game $G_r=\{2\,|\,\{\bigcup _{\xi <\rho _r}\{*_{\xi +1}\}\,|\,-2\}\}$. Let

$$\begin{aligned} S=(\bigcup _{r\in \mathbb {R}}\{G_r\})\cup \{\{2\,|\,\{\bigcup _{\xi <\omega _1}\{*_{\xi +1}\}\,|\,-2\}\}\}\cup \{-1\}. \end{aligned}$$

The following $\mathbf {L}(S)$ is obtained (Fig. 8).

Fig. 8

Real numbers—representation with games

4 Convergence to Conway’s construction

Starting the recursion from $S\ne \emptyset$ raises the question of whether $\mathbf {L}^\gamma (S)= \mathbf {L}^\gamma (\emptyset )$ for some $\gamma \in \mathbb {O}rd$. Consider $S=\{0\}$; if $n\in \mathbb {N}_0$ then $\mathbf {L}^n(S)\ne \mathbf {L}^n(\emptyset )$. That happens because, considering $k\in \mathbb {N}$, $k\in \mathbf {L}^{k-1}(S)$ and $k\not \in \mathbf {L}^{k-1}(\emptyset )$. However, the next result establishes a general convergence to Conway’s construction.

Theorem 10

(Convergence Theorem) Let S be a set of games. Then, for some $\gamma \in \mathbb {O}rd$, $\mathbf {L}^\gamma (S)= \mathbf {L}^\gamma (\emptyset )$.

Proof

Let S be a set of games, and

$$\begin{aligned} B=\{\beta \in \mathbb {O}rd : \exists G\in S\,\text {such that } b(G) = \beta \}, \end{aligned}$$

i.e., the set of birthdays of the elements of S. There is a natural embedding of B into S. The images may be obtained applying the Axiom of Choice to the family $\{G\in S: b(G)=\xi \}_{\xi \in B}$. Therefore, B must be a set because S is a set. Also, B is bounded (an unbounded class of ordinals is not a set).

Consider $\alpha \in \mathbb {O}rd$ such that $b(G)\leqslant \alpha$ for all $G\in S$. Let $\gamma$ be an indecomposable ordinal such that $\gamma >\alpha$. We observe that $\gamma$ exists because $\mathbb {H}$ is unbounded.

Let us prove that $\mathbf {L}^\gamma (S)= \mathbf {L}^\gamma (\emptyset )$.

($\supseteq$) Consider $J\in \mathbf {L}^\gamma (\emptyset )$. By definition, $J\in \mathbf {L}(U)$ where U is the set of games with birthday smaller than $\gamma$. Because $0\in \mathbf {L}^0(S)$, if the recursion starts with S, all games in U are born before the day $\gamma$ . So, $J\in \mathbf {L}^\gamma (S)$.

($\subseteq$) Consider $J\in \mathbf {L}^\gamma (S)$. By definition, $J\in \mathbf {L}(U)$ where U is the set of games born on day $\beta <\gamma$, considering the recursion that starts with S. Because $b(G)\leqslant \alpha$ for all $G\in S$, all games in S are in $\mathbf {L}^\alpha (\emptyset )$. Therefore, $J\in \mathbf {L}(U')$ where $U'$ is the set of games born on day $\alpha +\beta$ starting with $\emptyset$. Due to the fact that $\gamma$ is additively indecomposable, $\alpha +\beta <\gamma$ and, so, $U'$ is contained in the set of games born before the day $\gamma$, if we consider the recursion that starts with $\emptyset$. Thus, $J\in \mathbf {L}^\gamma (\emptyset )$. $\square$

Example 9

If $S=\{1, *_7, \{20\,|\,-30\}\}$ then $\mathbf {L}^\omega (S)= \mathbf {L}^\omega (\emptyset )$. More, if S is a set of short games then $\mathbf {L}^{\omega }(S)= \mathbf {L}^{\omega }(\emptyset )$.

Example 10

If $S=\{1, *_7, *_{\omega +1}\}$ then $\mathbf {L}^{\omega ^2}(S)= \mathbf {L}^{\omega ^2}(\emptyset )$.

5 Other questions

The original question still remains open:

Question 1

Characterize the sets of games S such that $\mathbf {L}^0(S)$ is a distributive lattice.

Other authors have shown that lattices come from different generation schemes.

Cincotti (2012) has shown that distributive lattices are generated when considering coalitions of multi-player combinatorial games.

Siegel (2013) considers dicot games, where either both players have a move or the game is over. These are recursively defined by (i) $S=0$, and (ii) in $\mathbf {L}^n(S) = \mathbf {L}(\mathbf {L}^{n-1})=\left\{ \{{G^{\mathcal {L}}}\,|\,{G^{\mathcal {R}}}\}: {G^{\mathcal {L}}},{G^{\mathcal {R}}}\subseteq \mathbf {L}^{n-1}\right\}$, requiring ${G^{\mathcal {L}}}\ne \emptyset \ne {G^{\mathcal {R}}}$. On (Siegel 2013, p 166), Siegel asks as an open problem/exercise to show that $\mathbf {L}^n(S)$ is not a lattice but, with the addition of a maximum and a minimum element, it is a distributive lattice.

Hereditary transitive games have the property that each option is also hereditary transitive and for each game G, $({G^{\mathcal {L}}})^{\mathcal {L}}\subseteq {G^{\mathcal {L}}}$ and $({G^{\mathcal {R}}})^{\mathcal {R}}\subseteq {G^{\mathcal {R}}}$. The works of Siegel (2011), and McKay (2016), together, show that the games born on day n do not form a distributive, but a planar lattice.

Very little is known about the partial order of misère games, that is, games in which the first player who cannot move wins. The games born by day n do not form a lattice. However, two subsets of misère games have been shown to have nice algebraic properties (McKay et al. 2016; Milley and Renault 2013; Renault 2018). Note that there has not been a paper published on misère games with infinite options.

Question 2

Describe the partial order of the dicot misère games born by day $\alpha$.

Dead ending games have the property that if Left has no moves in G then there is no sequence of Right moves that will result in Left having a move. Similarly for Right.

Question 3

Describe the partial order of the dead ending misère games born by day $\alpha$.