Games as recursive coalgebras
A categorical view on the Nim-sum
Abstract.
In 1901, Bouton proved that a winning strategy for the game of Nim is given by the bitwise XOR, called the nim-sum. But why does such a weird binary operation work? Led by this question, this paper introduces a categorical reinterpretation of combinatorial games and the nim-sum. The main categorical gadget used here is recursive coalgebras, which allow us to redefine games as “graphs on which we can conduct recursive calculations” in a concise and precise way.
For game-theorists, we provide a systematic framework to decompose an impartial game into simpler games and synthesize the quantities on them, which generalizes the nim-sum rule for the Conway addition. To read the first half of this paper, the categorical preliminaries are limited to the definitions of categories and functors.
For category theorists, this paper offers a nicely behaved category of games , which is a locally finitely presentable symmetric monoidal closed category comonadic over admitting a subobject classifier!
As this paper has several ways to be developed, we list seven open questions in the final section.
Key words and phrases:
Impartial games, nim-sum, Conway addition, recursive coalgebra, hylomorphism, monoidal category, monoid, locally presentable category, subobject classifier.2020 Mathematics Subject Classification
91A46, 18C50, 03B70Throughout this paper, denotes the set of all non-negative integers .
1. Introduction
1.1. Why does the nim-sum appear?
In 1901, Bouton discovered the remarkable (and now very famous) winning strategy of the game nim in [Bou01]. In -heap nim, there are heaps of stones, with stones in each heap. Two players take turns removing stones, but on each turn, they must remove stones from one heap (and “removing stones” is not allowed.) The player who can no longer make a move loses11 1 Usually, the rule is stated as “the player who takes the last stone wins,” but it does not make sense in the particular situation where from the start.. For example, Figure 1 is a typical play from the state , where wins.
Bouton’s winning strategy is based on a nicely designed group structure on called nim-sum. (We will define the nim-sum again in a more formal way in Definition 2.16.)
Definition 1.1.
The nim-sum of two natural numbers is the bit-wise excluded disjunction.
For example, the nim-sum of and is (Figure 2).
Bouton’s theorem [Bou01] claims that the winning strategy of nim is to make move so that the resulting state has as its nim-sum . One can check that the player conduct the winning strategy in Figure 1. Later, Nim-sum is proven to be important not only for Nim, but also for general combinatorial game theory. (See textbooks on combinatorial game theory, including [Sie13].)
Once you know the strategy, it is not very difficult to prove that it really is a winning strategy. However, when one shows it, people often react in a similar way: “I understand that it works, but why does it work with this weird operation called nim-sum?” The initial motivation for this paper was to answer this question concerning a conceptual origin of the nim-sum, and in fact, we provide a categorical characterization of it (Proposition 4.14). Although we admit that our characterization is not yet fully satisfying to call a “conceptual understanding” (cf. Section 5.1), we expect that our framework serves as a theoretical foundation for further research22 2 A follow-up paper, which is a joint work with Ryo Suzuki, will be uploaded later..
1.2. Recursions in game theory and coalgebra theory
In order to obtain a categorical understanding of the nim-sum, we first need to seek a natural category of impartial games. While there are already several categories of games known in category theory community, represented by Joyal’s one [Joy77], our approach is a categorical theory of recursions (see also Section 1.3.1).
Combinatorial game theory is inherently recursive (or inductive). Most of the important notions in game theory, including Grundy numbers, Conway addition, birthday, outcome, and even the notion of a game itself(!), are usually defined in a recursive (or inductive) way (see [Sie13]). In the appendix of his book On numbers and games [Con00], John H. Conway says that
[…] all that is needed to justify the induction is the principle: “If is some proposition that holds for whenever it holds for all and , then holds universally.” [Con00]
in the context of the foundations of mathematics.
In category theory, this kind of recursion scheme is addressed by recursive coalgebras, which we will recall in Section 3.2. The notion of recursive coalgebra first appears in [Osi74] in the context of categorical (or topos-theoretic) set theory, and then was generalized and developed in [Tay99]. In this paper, we call recursive -coalgebras games (Theorem 3.14), and develop a categorical theory of games (cf. Table 1).
1.3. Our contribution
We introduce the category of games in Section 3 as the category of recursive -coalgebras and reinterpret impartial game theory from that point of view (Table 1). For example, we interpret the notion of game values, such as Grundy numbers, remoteness, outcomes, and so on, in terms of hylomorphisms. To the best of the author’s knowledge, this is the first paper that interprets game theory explicitly using recursive coalgebras (see also related papers in Section 1.3.1).
Then, in Section 4, we introduce the notion of Bouton monoid (Definition 4.6), which generalizes the nim-sum (Proposition 4.14). Our definition of the Bouton monoid is based on its universality; the universal monoid that decomposes a game into smaller games and synthesizes the game values from the smaller ones to the original. Our main theorem (Theorem 4.8) proves that, for any decomposition rule ( monoidal structure) and any target game value (with some mild conditions), there exists a Bouton monoid.
As we believe that this is a fruitful way to pursue, in the last section (Section 5), we list some open questions along with some new propositions.
For category theorists, in Appendix B, we observe that the category has many pleasant properties; is a locally finitely presentable symmetric monoidal closed category comonadic over , admitting an (Epi,Mono)-orthogonal factorization system and a subobject classifier!
1.3.1. Related works
There are already studies of related categories. For example, [HL09] utilizes a terminal coalgebra to study hypergames. They consider (hyper)games as elements of the (class size) terminal coalgebra.
A recent study [Baš+24], which is indepent of our study, is from a more game-theoretic community and closer to our approach. While they do not use the coalgebra theory explicitly, their approach is very recursive-coalgebra-theoretic, and their categories are quite similar to our category. In fact, what they call the category of rulegraphs is equivalent to the category of recursive coalgebras for the covariant powerset functor , which is the prototypical example of the theory of recursive coalgebras. Furthermore, the notion of hylomorphism implicitly appears in [Baš+24, Section 4], which we will explain in terms of recursive coalgerbras in Section 3.5.
While our category of games is a full subcategory of theirs , their categorical properties are different. For example, the content of Section 4 needs the terminal object, which does not exists in but exists in . Our category is locally finitely presentable, and hence equivalent to an category of models of an essentially algebraic theory. This might contribute to their idea of the analogy between the category of games and the category of algebras, emphasized both in [Baš+24] and [BES25].
The category of -coalgebra has been studied also in the context of modal logic. In particular, a recent work [DG24] studies the category of locally finite Kripke frames, which subsumes our category as its full subcategory. Some of the content of Appendix B have already appeared in [DG24]. See Remark B.1 for more details.
Acknowledgment The author would like to thank his supervisor, Ryu Hasegawa, for helpful discussions and suggestions, in particular for suggesting the use of hylomorphisms in this research. His appreciation extends to Tomoaki Abuku, Koki Suetsugu, Paul Taylor, Takeshi Tsukada, Kazuyuki Asada, Syoei Suzuki, Ryo Suzuki, Kyosuke Higashida, Ivan Di Liberti, and Keisuke Hoshino for their valuable discussions, as well as Math Space topos and Tokyo Kanda Laboratory (NII) for offering him a place for discussion. The content of this paper was first announced at Japan Combinatorial Game Theory Mini-Workshops with Urban Larsson in May 2023. The author would like to thank the organizers.
The author was supported by JSPS KAKENHI Grant Number JP24KJ0837 and FoPM, WINGS Program, the University of Tokyo. The research was supported by ROIS NII Open Collaborative Research 2025-251M-22791.
2. Games as graphs
In this section, for those who are not familiar with combinatorial game theory, we recall the game-theoretic notions and phenomena that will be reinterpreted and generalized in the following two sections. For more details, see the standard textbooks on combinatorial game theory, including [Sie13].
2.1. Games and Outcomes
Since the notion of a game is very fundamental, it has been studied from many perspectives, and many different mathematical formulations have been proposed. In this paper, we begin our discussion with a graph-theoretic33 3 Actually, this is not quite graph-theoretic in the sense of Remark 3.16 formulation of impartial combinatorial games. Other kinds of games will be mentioned in Remark 3.37, Section 5.2, and Section 5.4.3. The idea of the formulation is quite simple; a vertex is a state of the game, and an edge is a possible move.
Definition 2.1 ((impartial) games).
A game is a pair of a (possibly infinite) set and a relation that satisfies two finiteness conditions:
- (1)
(finite options) For any , the number of options is finite.
- (2)
(finite time) There is no infinite path.
The ultimate goal of combinatorial game theory is to win a given game. To win a game is almost the same thing as knowing outcome, “-states” (Next-player-winning states) or “-states” (Previous-player-winning states), defined as follows.
Definition 2.2 (Outcome).
For a game and its state , the outcome of is defined by
or equivalently, it is recursively defined by
The latter recursive definition is not circuler, thanks to the “finite time” condition.
Remark 2.3 (How can we win with outcome?).
For those who are not familiar with combinatorial game theory, let us clarify the connection between an actual ways to win a game and the outcome function . Suppose it is your turn and the current position is an -state. Then the winning strategy is simply to always move to a -state. By the definition of -states, your opponent cannot reply with another -state. The opponent must either move to an -state, or lose immediately. In the latter case, by the definition of -states, you can move to a -state again. Due to the finite time condition, this procedure must terminate, and therefore you are guaranteed to win.
Remark 2.4 (Why do we assume the “finite options” condition?).
While we do not assume the finiteness of the underlying set, we include the “finite options” condition in Definition 2.1. This kind of “local finiteness” condition is a difference with [Baš+24] and a similarity with [DG24]. We assume it not only because many games of interest satisfy the condition, but also we need it in the following sections. Let us explain some (of many) reasons why we need it. One game theoretic reason is that it is necessary to define the Grundy number while dealing with games with infinite states. (More precisely, we need it to keep Grundy number to be finite ordinal.) A categorical reason is that the considered functor is finitary ([ALM07, Example 2.5, Example 3.18]) and hence our category of games admits a lot of pleasant properties (Appendix B). In particular, thanks to the finite option condition, we have the terminal game (Proposition 3.31), which plays the central role in our characterization of nim-sum.
Example 2.5 (Winning strategy of the subtraction nim).
Let us give a famous example of the outcome function. A subtraction nim (for ) is , where
We can (recursively) prove that the outcome function is given by
So the winning strategy is to move to the multiples of .
Theoretically, the most important game might be the following game, which we will call the binary exponent nim, or later, the terminal game (Remark 3.33).
Example 2.6 (Binary exponent nim, or the terminal game).
The underlying set of the binary exponent nim is , and the relation is defined by
For example, when , since
there are possible moves, namely . The state is -state, and the winning way it to move to or (Figure 8).
Example 2.7 (“Effeuiller la marguerite”).
Let us consider another game whose underlying set is . This time, we define by
In each phase, players have at most one option. Obviously, the outcome of a state of this boring game is determined only by the parity of ; a state is a -state if and only if is even. We will write for this game since this game is conventionally called “effeuiller la marguerite.” Althogh this game is practically quite boring, it sometimes plays a theoretical role (Example 4.16, Example C.3).
We conclude this subsection by expressing Bouton’s theorem in our formulation (Definition 2.1) as follows.
Example 2.8 (Nim).
In our formulation, the -heap nim is , where is defined by
Theorem 2.9 (Bouton’s theorem [Bou01]).
A state of the -heap nim is -state if and only if .
2.2. Divide difficulties with the Conway addition and Grundy number
In the last subsection, we have seen that once you know the outcome of a given game, you know the winning strategy. But how can we effectively calculate the outcome? (For example, how can we know that the outcome of a nim state is if and only if ?)
One promising strategy is to divide the difficulty into smaller parts! What we will do in this subsection (and the whole Section 4) is to decompose a game into smaller parts and synthesize the properties of smaller games:
- •
We want to know the outcome of a game .
- •
We devide the game into a Conway sum (Definition 2.10) of smaller games .
- •
We calculate the Grundy numbers (Definition 2.14) of the games .
- •
We calculate the Grundy numbers of from those of (Theorem 2.17).
- •
We calculate the outcome of from the Grundy number of (Proposition 2.15).
Let us clarify again that all the content in this subsection is well-known in combinatorial game theory. For more details, see standard textbooks including [Sie13].
First, we recall the notion of the Conway addition of games, which is visualized in Figure 9.
Definition 2.10 (Conway addition of games).
For two games , their Conway sum (or just sum) is the game , where if and only if or .
Remark 2.11 (Terminology and notation: Why is it called “sum”?).
The Conway sum is conventionally called “sum” and denoted by , while some readers might think “product” is a better name. In fact, the corresponding monoidal structure in graph theory is called the box “product” (see, for example, [KK24], which is also related to Section 5.3). But there is a decent reason to call it “sum” in game theory, related to the surreal number [Con00].
A typical usage of the Conway addition is to decompose a complicated game into smaller games. The prototypical example is the following decomposition of nim.
Example 2.12 (Decomposition of Nim).
The -heaps nim is the Conway sum of -copies of (-heap) nim games.
We want to utilize the Conway addition to calculate the outcome of a state . However, even if you know the outcomes and , it is generally impossible to calculate the outcome of the sum state . Thus we need to enrich the outcome into the Grundy number. As a preparation, we recall the notion of mex, which stands for minimum excluded value.
Definition 2.13 (mex).
For a finite set of natural numbers , its mex, denoted by , is the minimum natural number that does not belong to the subset . In other words, mex of is the minimum element of the complement of :
Notice that the complement is always non-empty since the set is assumed to be finite (cf. Remark 2.4).
Definition 2.14 (Grundy number).
For a game and a state , its Grundy number is recursively defined by
| (1) |
This recursive definition does work due to the two finiteness conditions in the definition of games (Definition 2.1). See Figure 10 for an example of a recursive calculation of the Grundy numbers.
The importance of the Grundy number is due to the following proposition.
Proposition 2.15 (the Grundy number is more informative than the outcome).
For any game and any state , its outcome is if and only if its Grundy number is :
Proof.
One can easily prove this by induction, although we will see more conceptual proof later (Proposition 3.26). ∎
The reason why we enrich the ouctome to Grundy number is that the Grundy number is compatible with the Conway addition (Theorem 2.17)! Let us recall nim-sum again (Definition 1.1).
Definition 2.16 (Nim-sum).
The nim-sum is the abelian group structure on , induced by the bijection given by the binary expansion. In other words, the nim-sum is the digit-wise exclusive disjunction (xor) of the binary expansion.
For example, .
Theorem 2.17 (Nim-sum rule= generalized Bouton’s theorem [Sie13, II. Theorem4.7]).
For any pair of games and any pair of states , , the Grundy number of is given by the nim-sum as follows:
Combining Proposition 2.15 and Theorem 2.17, we can calculate -states of a Conway sum and thus its winning strategy. In fact, for a given game that can be decomposed into a Conway sum of two games , we have
Example 2.18 (Analysis of nim).
The classical Bouton theorem (Theorem 2.9) is the typical example of the above observation. As the -heap nim is the Conway sum of -copies of the -heap nim (Example 2.12), in order to win , it suffices to know . By the easy induction, we can prove that (cf. Appendix C), and thus we obtain
Therefore, Proposition 2.15 implies that a state is a -state if and only if , which is exactly what the Bouton theorem states (Theorem 2.9).
3. Games as recursive coalgebras
In this section and the next section, we will reinterpret the content in Section 2 in terms of recursive coalgebras. Here is the spoiler:
| Abstract Coalgebra Theory | Game Theoretic Notions | example | |
|---|---|---|---|
| Recursive coalgebra | section 3.3 | Game | |
| Coalgebra homomorphism | section 3.4 | Game morphism | |
| Algebra | section 3.5 | recursion step of game value | mex |
| Algebra homomorphism | section 3.5 | Transformation of game value | Proposition 2.15 |
| Coalgebra-algebra morphism | section 3.5 | Game value | Grundy number |
| Terminal recursive coalgebra | section 3.6 | Binary exponent nim | |
| Monoidal structure | section 4.1 | Game decomposition | Conway sum |
| Bouton monoid | section 4.2 | Nim-sum |
Before delving into the reinterpretation part, we first observe a motivating phenomenon in Section 3.1, and recall the theory of recursive coalgebras in Section 3.2.
3.1. Why recursive coalgebras?
Before explaining the categorical abstract nonsense in Section 3.2, let us observe one phenomenon motivating the latter contents. The reader can skip this subsection since it does not include any theorems. However, we recommend to read it because this observation is the starting idea of this project44 4 This observation can be found also in [Baš+24, section 4], which does not use coalgebra theory..
Our original motivation is to understand the nim-sum (Definition 2.16), and the reason why the nim-sum works is the Nim-sum rule (Theorem 2.17) regarding the Grundy number (Definition 2.14). So our first task would be to understand the Grundy number categorically.
In the definition of Grundy number, we used a particular type of recursion
Let denote the set of all finite subset of a given set (Notation 3.9). Then, the mex function is a function from to :
Similarly, we can rewrite games as a function between and , but in the opposite direction! For any directed graph , the corresponding neighborhood function is defined by
| (2) |
If a graph satisfies the finite option condition in Definition 2.1, in particular, if is a game, the codomain can be reduced to and we obtain the function
Thus, we can rephrase the definition of Grundy number (Definition 2.14 and Equation 1) as the unique function that makes the following “twisted” diagram
| (3) |  |
commutative, where denotes the direct image function! The “finite time” condition ensures the unique existence of such a function .
One may find it weird to consider such a twisted diagram. However this reflects a kind of “twistedness” of the computation of the Grundy number; the recursive computation of Grundy numbers, as in Figure 10, is carried out by tracing the game backwards. The somewhat unusual kind of “twisted” commutativity in Diagram 3 corresponds to the nature of this recursive computation that goes against the flow of the game! Such “twisted recursive computations” have a long history in category theory (or categorical computer science) under the name of recursive coalgebras (or hylomorphisms), which we will recall in the next subsection.
3.2. Preliminaries on coalgebras and recursive coalgebras
This subsection aims to recall the basic notions in coalgebra theory, in particular, the definition and properties of recursive coalgebras. The reades are assumed to be familiar with the definitions of categories and functors, (and limits for Section 3.6). For example, the first three sections of [Mac98] suffice. For general theory and examples of coalgebras, see [Jac17]. For recursive coalgebras, see the book [Tay99], papers including [AMM20], or papers cited therein.
In order to separate the general theory from our particular context of game theory, we intentionally postpone the motivating examples untill the next subsection. So if the reader feels that it is too abstract, please refer to the next section for our game-theoretic examples.
3.2.1. Algebras and coalgebras of an endofunctor
The definition of coalgebras (and algebras) of an endofunctor is surprisingly simple:
Definition 3.1 (Coalgebras and algebras).
For an endofunctor on a category , a -coalgebra is a pair of an object and a morphism . Dually, a -algebra is a pair of an object and a morphism .
Definition 3.2 (Coalgebra homomorphism and algebra homomorphism).
For an endofunctor on a category , a homomorphism of -coalgebras from to is a morphism in such that the diagram
 |
commutes. Homomorohisms between -algebras are defined in the dual way:
 |
Notation 3.3.
For an endofunctor on a category , the category of -coalgebras and -coalgebra homomorphisms is denoted by . The category of -algebras and -algebra homomorphisms is denoted by .
3.2.2. Coalgebra-algebra morphisms and Recursive coalgebras
Definition 3.4.
For an endofunctor on a category , a coalgebra-algebra morphism from a -coalgebra to a -algebra is a morphism in the category such that the diagram
 |
commutes.
Definition 3.5 (Recursive coalgebra).
A -coalgebra is said to be recursive if, for any -alegebra , there exists a unique coalgebra-algebra morphism from to . The full subcategory of that consists of all recursive -coalgebras is denoted by .
For a recursive coalgebra and a -algebra , the unique coalgebra-algebra morphism is called the hylomorphism and denoted by .
Let us emphasize the following “stability” of hylomorphisms by compositions, which is theoretically almost trivial, but it provides a seemingly non-trivial consequences including Proposition 3.18, Corollary 3.25, and Proposition 3.26, which generalizes Proposition 2.15.
Lemma 3.6 (Stability of hylomorphisms by composition).
Let be an endofunctor on a category , be a recursive -coalgebra, be a -algebra, and be the hylomorphism between them.
- •
For any recurisive -coalgebra and any -coalgebra homomorphism , the hylomorphism is given by .
- •
For any -algebra and any -algebra homomorphism , the hylomorphism is given by .
Proof.
The commutative diagmram
 |
completes the proof. ∎
As we are interested in the terminal object of , let us recall the related result from [Lam68] and [CUV06].
Proposition 3.7 (Initial algebra is the terminal recursive coalgebra).
Proof.
Both are easily checked by diagram chases. The first assertion is known as Lambek’s lemma. ∎
Remark 3.8 (Relationship with well-founded coalgebras).
Actually, the recursive coalgebras we will consider (Section 3.3) are also characterized as well-founed coalgebras, which are known to be inherently related to recursice coalgebras. For their relationships, see [Tay99] and also a recent study [AMM20].
3.3. Games as recursive -coalgebras
In the rest of Section 3, we will specialize the general theory of recursive coalgebra (Section 3.2) to the case where the endofunctor is the the finite powerset functor.
Notation 3.9 (finite powerset functor).
In this paper,
- •
denotes the covariant powerset functor that sends a set to its powerset and a function to its direct image function, and
- •
denotes the finite powerset functor, which is the subfunctor of such that .
In terms of coalgebras, any graph is associated with the corresponding -coalgebra
by Equation 2. The finite option condition in Definition 2.1 is precisely saying that the codomain can be reduced to . The next proposition states that the finite time condition is precicely the recursiveness (Definition 3.5) and characterize games as the graphs that admits the “twisted recursion” (Diagram 3).
Proposition 3.10 (Games as recursive coalgebras).
For any graph with the finite option condition (Definition 2.1), the corresponding -coalgebra
is a recursive coalgebra if and only if is a game. In particular, for any set , Equation 2 provides a one-to-one correspondence between the game structures on and the recursive -coalgebra structures on .
Proof.
Let be a graph with the finite option condition. If the graph is a game, i.e., satisfies the finite time condition, we can recursively construct the unique coalgebra-algebra morphism to any -algebra, and hence we can prove that it is a recursive coalgebra.
Conversely, take an arbitrary recursive coalgebra . We prove that the corresponding graph satisfies the finite time condition. Consider a -algebra defined by
On the one hand, the function defined by
is an coalgebra-algebra morphism from to . On the other hand, the constant function to , which is denoted by , is also a coalgebra-algebra morphism from to . Therefore, the assumption that is recursive implies that , i.e., satisfies the finite time condition. ∎
Example 3.11 (Nim as a recursive coalgebra).
Let denote the -coalgebra corresponding to the (-heap) nim game (Example 2.8). This function is given by
which looks like the von Neumann set-theoretic definition of natural numbers. This analogy becomes more precise in Example 3.35.
3.4. Game morphisms as -coalgebra homomorphismsm
As games are recursive coalgebras, it is reasonable to define game morphisms as coalgebra homomorphisms. Notice that being a coalgebra homomorphism is much stronger than just being a graph morphism! For games and and a function , being a graph morphism is equivalent to saying that , which is strictly weaker than being a coalgebra homomorphism . In order to ensure the opposite inclusion , we need to assume a kind of “path-lifting property” as follows.
Definition 3.12 (Game morphism).
A game morphism from a game to another game is a function satsifying the following two conditions:
- (1) Graph morphism:
-
For any , implies .
- (2) Path-lifting:
-
For any and , if , then there exists such that and . (see Figure 11)
Notation 3.13.
The category of games and game morphisms is denoted by , and the canonical forgetful functor is denoted by .
Summarizing the content of the previous and the current subsections, we arrive at the following so-called “theorem,” which is in effect little more than a systematic restatement of the definitions introduced so far.
Theorem 3.14 (Games as recursive coalgebras).
The category of games is equivalent55 5 In fact, they are isomorphic. to the category of recursive -coalgebras.
Proof.
This follows from Proposition 3.10 and the argument above Definition 3.12. ∎
Some readers might find this “path-lifting” condition unnatural and hard to accept. On the one hand, some game theorists might think that it is a “category-theory-biased” condition with little connection to game theoretic phenomena. On the other hand, some category theorists might worry that the path-lifting property could break pleasant properties of the category of graphs. I believe these concerns will be resolved in the rest of the paper, but let us close this subsection with a brief explanation of why the “path-lifting property” is reasonable.
From a game theoretic perspective, the reason why we need the path-lifting property is simply because graph homomorphisms do not preserve game-theoretic data, such as the outcome and the Grundy number. For example, Figure 11 illustrates two graph morphisms: the left-hand one satisfies the path-lifting property and preserves the outcome, while the right-hand one does not. In fact, we will prove that all game morphisms preserve all “recursively defined” game data, such as the outcome and the Grundy number (Proposition 3.18 and Corollary 3.25).
From the categorical point of view, the category of games behaves surprisingly nice. Investigating the categorical properties of the category of games is not the main topic of this paper, but here I will list some facts.
Theorem 3.15 (Categorical properties of the category of games).
The category of games has the following properties:
- •
The category of games is locally finitely presentable. In particular, it has all small limits and colimits.
- •
The forgetful functor is comonadic. In particular, it preserves, reflects, and strictly creates all small colimits.
- •
The category of games has a subobject classifier.
Proof.
The proofs are postponed until Appendix B. ∎
Remark 3.16 (Game is not just a graph with properties.).
In Definition 2.1, we defined the notion of games as if they were just graphs with some properties. However, that way of speaking is not accurate in the spirit of the categorical distinction between stuff, structure, and properties, since the canonical forgetful functor
is not fully faithful. (see [BS09, 2.4. Stuff, structure, and properties] for more explanation on the categorical distinction.) This fact is also mentioned in [Baš+24, Section 5]. In [Adá05], Adámek also points out that to regard -coalgebras as graphs is “not a reasonable point of view” as follows:
[Adá05, Example 2.7.] Sometimes one also identifies with a finitely branching directed graph […] However, this is often not a reasonable point of view because the coalgebra homomorphisms are much stronger than graph homomorphisms […]
Therefore, defining a game as a recursive coalgebra does not mean reducing it to graph theory. Rather, it extracts the structure — the “neighborhood function” — from the underlying graph, and declares that this is the game-theoretic structure.
3.5. Game values as -algebras
In this subsection, we explain how game values, such as outcome and the Grundy number, are understood in our categorical framework. First, we introduce the most naïve notion of the game value: the quantity preserved by all game morphisms.
Definition 3.17.
A game value is a cocone under the forgetful functor . In other words, a game value is a set equipped with a (proper class size) family of functions from all games
that is preserved by any game morphism in the sense that .
 |
Thus, we obtain the following proposition as a special case of the abstract nonsense.
Proposition 3.18.
For any -algebra , the family of hylomorphisms
is a game value.
Proof.
This is just a special case of the first half of Lemma 3.6. ∎
Let us see some examples of -algebras and the induced game values. See Table 2 for the correspondence list.
| Game value | -algebra |
|---|---|
| Outcome | |
| Grundy number | |
| Ended states | |
| Birthday | |
| Misere outcome | |
| Remoteness | in Example 3.24 |
First, let us observe that the outcome (Definition 2.2) and the Grundy number (Definition 2.14) are game values induced by -algebras.
Example 3.19 (Outcome).
Example 3.20 (Grundy number).
The Grundy number (Definition 2.14) is induced by the -algebra (Definition 2.13).
Other important game values in combinatorial game theory are also induced by -algebras.
Example 3.21 (Ended states).
Let us start with an easy example. For each state of a game , we define by
This game value is induced by the -algebra
So we obtain
Example 3.22 (Birthday).
For a game and a state , its birthday66 6 The notion of birthday is usually defined for a set-theoretically constructed game, as an element of . Our version of the birthday of coincides with the birthday of ., denoted by , is defined to be the length of the longest possible play from the state . This game value is induced by the -algebra 77 7 The notation is not conventional. We adopt it because is a kind of dual to . See Appendix C for more details., where
So we have
Example 3.23 (Misere outcome).
In combinatorial game theory, a misere game is a game where the player who takes the last move loses. In our framework, a misere game is understood by the same notion of a game, but a different notion of the outcome: the outcome should be modified so that the ending state is an -state. Defining a -algebra by
the corresponding game evaluation is the misere outcome .
Example 3.24 (Remoteness [Smi66]).
If you do not just care about whether you win or lose, but also about how quickly you can win or how long you can postpone losing, then what you should look at is not the outcome but a more informative game value called the remoteness. The remoteness takes values in , where
- •
means that, if you move to , then you can win in at most moves, and
- •
means that, if you move to , you can avoid losing for at least moves.
This is a recuresively defined game value induced by the -algebra structure
Corollary 3.25.
Any game morphism preserves the outcome, the Grundy number, ended states, the birthday, the misere outcome, and the remoteness.
Proof.
These are just examples of Proposition 3.18, and hence examples of the stability of hylomorphisms (Lemma 3.6). ∎
Using the latter part of Lemma 3.6, we obtain the following statement:
Proposition 3.26.
For any -algebra homomorphism from to , the game value can be calculated via , i.e., we have .
 |
Proof.
This is just the latter half of Lemma 3.6. ∎
For example, the fact that is calculated by (Proposition 2.15) immediately follows from Proposition 3.26 and the fact that defined by
is a -algebra homomorphism . We can do similar arguments for the following -algebra homomorphisms as well:
- •
is calculated by .
- •
is calculated by .
- •
is calculated by .
Remark 3.27 (Comparison with [Baš+24]).
3.6. The terminal game consists of hereditarily finite sets
This subsection aims to describe the terminal game, which plays the central role in the next section (Section 4). First, we will describe it categorically (Diagram 4), and then we will write it down in a set-theoretic way (Proposition 3.31).
The calculation of the terminal recursive -coalgebra ( the terminal game, in our case) is a priori nontrivial. However, thanks to Proposition 3.7, it is reduced to the classical theorem of transfinite construction of an initial -algebra [Poh73, Adá74], which is known as Adamek’s fixed point theorem. (A concise explanation of the theorem, which suffices for our purpose, is found in [Jac16, Proposition 4.6.1 (1)].) The construction states that the initial algebra of , which also provides the terminal object in (Proposition 3.7), is given by the following colimit in
| (4) |  |
Here, we utilize the finite option condition in Definition 2.1 to ensure the assumption of Adamek’s fixed point theorem; the functor is finitary and hence preserves this colimit (cf. Remark 2.4).
Let us write down this colimit. (A canonical choice of) this colimit is known as the set of hereditarily finite sets in set theory. For its set-theoretic context and the terminology, see textbooks including [Kun13, section I.10].
Definition 3.28 (Hereditarily finite sets).
A hereditarily finite set is recursively defined as a finite set of hereditarily finite sets88 8 Rigorously speaking, a hereditarily finite set is a set that is ensured to be hereditarily finite by this recursive definition.. The set of all hereditarily finite sets is denoted by .
As this recursive definition might look confusing at first glance, let us give several examples.
Example 3.29.
The following sets are hereditarily finite sets:
- •
The empty set is trivially hereditarily finite since it has no element.
- •
Then, the set is also hereditarily finite.
- •
By induction, every (von Neumann’s formulation of) natural number is hereditarily finite. In other words, we have
- •
The set is a hereditarily finite set that is not a natural number.
- •
Informally speaking, hereditarily finite sets are sets described by a finite number of parentheses, like .
- •
While all hereditarily finite sets are finite, the converse does not hold. For example, while the set is a singleton, but it is not hereditarily finite.
Remark 3.30 (von Neumann hierarchy).
is often denoted by in order to emphasize that it is the -th of the von Neumann hierarchy.
By definition, is set-theoretically identical to . Therefore, admits
| the canonical -algebra structure | |||
| the canonical -coalgebra structure |
Proposition 3.31 (Terminal object of ).
The set is the initial -algebra with the -algebra structure . Therefore, is also the terminal object of with the -coalgebra structure .
Proof.
The former part follows from Adamek’s fixed point theorem (see Diagram 4 and the discussion above). The latter follows from Proposition 3.7. ∎
By a mild abuse of notation, we will write for the set of hereditarily finite sets, the initial -algebra, and the terminal recursive -coalgebra.
It is worth writing down the relation of the terminal game .
Definition 3.32 (Terminal game).
The terminal game is the game whose underlying set is the set of all hereditarily finite sets and whose relation is given by
Remark 3.33 (Ackerman’s interpretation and the binary exponent nim).
As we promised, the terminal game is isomorphic to the binary exponent nim in Example 2.6! Consider the following -algebra structure on
which is just the binary expression and hence bijective. The unique -algebra homomorphism is called Ackerman’s interpretation [Ack37] and known to be bijective. Therefore, this -algebra is isomorphic to the initial -algebra and hence initial as well. Consequently, the inverse function , which coincides with the binary exponent nim, is also a terminal object in .
Notation 3.34.
For each game , the unique game morphism to the terminal game is denoted by .
Example 3.35.
For the -heap nim , the game morphism is nothing other than the von Neumann formulation of natural numbers. (cf. Example 3.11)
Lemma 3.36 (Characterization of game values).
For a (class-size) family of functions , the following conditions are equivalent.
- (1)
The family is a game value (Definition 3.17), i.e., any game morphism preserves .
- (2)
The equality holds for any game .
- (3)
There exists a -algebra and a function such that for any game .
Proof.
The implication follows since is a game morphism. The implication follows since we can take the initial -algebra as , and as using the terminal game (cf. Proposition 3.31). The last implication follows from Proposition 3.18. ∎
Remark 3.37 ( as colimit, and a game with a starting state.).
For category theorists, Lemma 3.36 is an immediate corollary of an almost trivial fact that is the colimit of the forgetful functor , and the morphisms is the colimit cocone of this large colimit. Since the category has the terminal object , the colimit of this diagram is just the image of the terminal object . As game values are defined as cocones of (Definition 3.17), one can say that is the “universal game value” (but in a bit boring way).
This phenomenon is loosely related to the relationships between different definitions of games. In some context, an impartial game is defined as an element of . From our point of view, each element defines a “game” in that sense. In slightly different words, if we consider games equipped with a “starting state” , we can define the category of pointed games , whose connected components are in one-to-one correspondence with hereditarily finite sets:
Remark 3.38.
As the condition (3) in Lemma 3.36 infers, some game values are not induced by -algebras. In fact, while the number of -algebra structures on the -element set is , there are exactly distinct game values on it due to Lemma 3.36.
4. Application: Nim-sum type theorem schema and the Bouton monoids
As an example of usages of our framework, this section provides a theorem schema that generalizes the nim-sum rule (Theorem 2.17). We firstly define the notion of a Bouton monoid (Definition 4.6), and then prove that it always exists (Theorem 4.8).
4.1. Decomposing games with monoidal structures
The goal of this subsection is to find a systematic way to decompose a complex game into simpler games. An established categorical tool to decompose objects is a monoidal structure on a category. For those who are not familiar with this notion, a standard reference is [Mac98].
In this subsection, we will observe several monoidal structures on the category .
Remark 4.1.
In this section, we also consider non-unital monoidal category, which does not require the unit object. Everything in this section works by replacing monoidal by non-unital monoidal, and monoid by semigroup. If the reader is not familiar with non-unital monoidal structure, one can restrict arguments to the unital cases, while considering remoteness will require non-unital one (Example 4.16).
Hisorically, the Conway addition is regarded as the canonical choice of monoidal structure on categories of games (for example, [Joy77]). It also provides a monoidal structure on our category.
Proposition 4.2.
The Conway addition is a symmetric monoidal closed structure on with the monoidal unit .
Proof.
Being symmetric monoidal is easily proven. The closedness, which we will not use in this section, is proven in Corollary B.11. ∎
Let us see some other examples.
Example 4.3 (Selective sum [Smi66]).
For a finite number of games with , their selective sum is the game in which each player selects at least one games out of the games and makes one move for each selected game. More foramlly spealing, the selective sum of two games is defined as follows:
- •
Its underlying set is .
- •
is defined by
The selective sum defines a (unital, symmetric, and closed) monoidal structure on with the monoidal unit .
Example 4.4 (Conjunctive sum [Smi66]).
For a finite and positive number of games with , their conjunctive sum is the game in which each player makes a move for all of the games. More foramlly spealing, the conjunctive sum of two games is defined as follows:
- •
Its underlying set is .
- •
is defined by
The conjuctive sum defines a non-unital99 9 The conjunctive sum defines a monoidal structure on with a monoidal unit (Figure 5), which fails to be a game. (but symmetric and closed) monoidal structure on .
4.2. Synthesizing game values with Bouton monoids
4.2.1. Bouton monoid
In the story of the Bouton theorem (Section 2), the abelian group of the nim-sum (Definition 2.16) and the notion of Grundy number plays a central role. More concretely, there are two characterizing properties of them:
- (1) Informative (Proposition 2.15):
-
For any game and any element , the Grundy number is more informative than the outcome in the sense that
- (2) Decomposable (Theorem 2.17):
-
For any games and any states , the Grundy number of the sum state is decomposable in the sense that
We will define the notion of a Bouton monoid as the minimum monoid that satisfies the two conditions above. The existence will be proven later (Theorem 4.8).
In the follwoing definition, we will use the notion of lax monoidal functors. For those who are not familiar with that notion, one can just consider monoidal structure on that makes strictly monoidal, i.e., . In fact, all the three monoidal structures in Section 4.1 make strict monoidal.
Notation 4.5 (Notations around lax monoidal functors).
If one consider a monoidal structure on the category that makes lax monoidal1010 10 Rigorously speaking, as the comparison map is a part of the lax monoidal functor, saying that “ is lax monoidal” is somewhat misleading. Similarly, to be rigorous, we need to specify the associativity and the unitality maps of the monoidal structure. However, we intentionally hide these data by a conventional abuse of notation, partially because of Remark 4.1. (with respect to the cartesian monoidal structure on ), we will write
for the chosen comparison map. Furthermore, for a pair of states , we will write for the state . Notice that it is compatible with the notations in the previous sections, for example, in Theorem 2.17.
Now we are ready to state the definition of the Bouton monoid. To aid in understanding the definition, Table 3 shows the correspondence between the general case and the specific case of the nim-sum.
Definition 4.6.
Let be a monoidal structure on such that the forgetful functor is lax monoidal, and let be a game value. The Bouton monoid of and is
- •
a game value equipped with
- •
a function and
- •
a monoid structure
that satisfies the following three conditions.
- (1) Informative:
-
For any game , we have
- (2) Decomposable:
-
For any games and any states , we have
- (3) Minimum:
-
It is minimum among such data. More concretely, for any data of the same type satisfying (the appropriate substitutes of) the above two conditions, there exsits a surjective monoid homomorphism from a submonoid such that the following diagram
commutes for any game .
| General case | Nim-sum case |
|---|---|
| Monoidal structure | Conway addition |
| (Target) game value | |
| Nim-sum | |
| Proposition 2.15 | |
| Theorem 2.17 |
Remark 4.7 (Is this minimality condition weird?).
Some readers may be unfamiliar with this kind of minimality condition. But actually it is very common especially in the automata theory. For example, the minimality of automata and syntactic monoids (Example A.3) are stated in this form. See textbooks including [Pin22], and see also [CP20] for an elegant categorical framework. This minimality condition says that the Bouton monoid is a subquotient of any others, which informally means that has neither redundant elements ( no proper submonoids) nor redundunt fineness ( no proper quotient monoids).
The goal of this subsection is to prove the existence of the Bouton monoid.
Theorem 4.8 (Existence of Bouton monoid).
For any monoidal structure on such that the forgetful functor is lax monoidal, and any game value , the Bouton monoid exists.
4.2.2. Step 1: Miniature monoid
We start with constructing an approximation of the Bouton monoid only by the information of the monoidal structure forgetting the terget game value . We will call the approximation by a temporary name: the miniture monoid of the monoidal structure .
The following trivial proposition is usually very boring due to the triviality of the terminal object. But it is worth considering in a category of coalgebras, in which a terminal object tends to be non-trivial.
Lemma 4.9.
For any monoidal category with a terminal object , the object has a unique monoid structure with respect to the monoidal structure.
Proof.
In a monoidal category with a terminal object , the multiplication map (and the unit map if you consider a unital structure) is uniquely determined since is terminal. All required commutativities are trivial since is the terminal object. ∎
In our case of the category of games , the unique game morphism provides the unique -monoid structure on the terminal game . Then, we can convert the -monoid to a usual monoid by the following well-known fact.
Fact 4.10.
Any lax monoidal functor sends a monoid object in to a monoid object in .
By the assumption that is lax monoidal, we obtain the induced monoid whose multiplacation function is given by
where denotes the comparison map of the lax monoidal functor . We will call this monoid structure on the set the miniature monoid of the monoidal structure , and write for the multiplication function.
Example 4.11 (Miniture monoids for some monoidal structures).
For the Conway addition , the miniature monoid structure on is given by
In usual context like [Sie13], this is just called the Conway addition. Similarly, the miniature monoid structure of (Example 4.3) and (Example 4.4) are given by
Lemma 4.12 (Miniature monoid reflects the ambient monoidal structure).
For any pair of games and , we have the following equation in the miniature monoid:
Proof.
Since is the terminal game, we have the following commutative diagram in :
| (5) |  |
By sending this diagram by and utilizing the naturality of , we have the following commutative diagram in :
 |
This completes the proof. ∎
4.2.3. Step 2: Minimum monoid factorization
The miniture monoid depends only on the monoidal structure , and is independent of the target game value . So we want to minimize keeping the ability to calculate the target game value . We introduce a very simple gadget for minimizing a monoid. See Appendix A for related contexts, examples, and the proof of the existence.
Definition 4.13 (Minimum monoid factorization).
For a monoid and a function to a set , the minimum monoid factorization of is a monoid equipped with a factorization of the function into a monoid homomorphism followed by a function
 |
that satisfies the following minimality condition.
- Minimum:
-
For any monoid equipped with a factorization into a monoid homomorphism followed by a function , there exsits a surjective monoid homomorphism from a submonoid such that the following diagram commutes.
One can check that the minimum monoid factorization always uniquely exists (up to canonical isomorphisms. See Proposition A.1 for a detailed proof and a construction. If one considers a non-unital monoidal structure (Remark 4.1), one can use the semigroup version in Remark A.4.
Let us return to the context of the Bouton monoid. Since has the miniture monoid structure (Section 4.2.2), we can consider the minimum monoid factorization of the function . Let be the minimum monoid factorization of the function with respect to the miniature monoid structure . Let denote the induced monoid structure on . For any game , due to Lemma 3.36, we obtain the following decomposition of the function .
 |
We define by .
 |
The family of functions is a game value, also due to Lemma 3.36 since it factors through .
We will prove that the triple of the game value , the function , and the monoid structure , all defined just above, provides the Bouton monoid for and . Regarding the first condition “(1) Informative”, the required equation obviously holds by definition. Regarding the second condition “(2) Decomposable”, we have
where we use Lemma 4.12 at the second equation.
Therefore, in order to prove the existence theorem (Theorem 4.8), it suffices to check that these data satisfies the third condition “(3) Minimum.” Assuming that the same type of data satisfies the first two conditions in Definition 4.6, we prove that there exsits a surjective monoid homomorphism from a submonoid such that the following diagram
 |
commutes for any game .
The first observation is that the function is a monoid homomorphism since the following diagram commutes. The commutativity of the top part is the definition of , the commutativity of the left-hand trapezoid follows from the “(2) Decomposable” assumption on , and the commutativity of the right-hand triangle follows since is a game value.
 |
Therefore, the universality of as the minimum factorization monoid implies that there exists a surjective monoid homomorphism from a submonoid such that the following diagram commutes.
 |
Therefore, Lemma 3.36 implies that
 |
commutes for any game . This completes the proof of Theorem 4.8.
4.2.4. Examples of Bouton monoids
We conclude this section by giving several examples of the Bouton monoids.
Proposition 4.14 (A categorical characterization of Nim-sum).
The monoid of nim-sum is isomorphic to the Bouton monoid of the Conway addition and the outcome .
Example 4.15 ().
The Bouton monoid of the selective sum (Example 4.3) and the outcome is given by as essentially pointed out in [Smi66]. The binary operation is given by with respect to the order .
Example 4.16 ().
The Bouton monoid of the conjunctive sum (Example 4.4) and the outcome is known to be remoteness ([Smi66]).
Here, as the considered monoidal structure is non-unital, the resulting Bouton “monoid” is also non-unital, i.e., it is just a semigroup (Remark 4.1). In fact, the binary operation is given by with respect to the order , which does not admit a neutral element. The minimality of the Bouton monoid can be checked by considering (Example 2.7, Example C.3).
An example of a game-theoretically motivated Boouton monoid whose target game value is not is mentioned in Section 5.4.2 (without being able to give an explicit description).
5. Concluding remarks and open questions
As there are still a lot of things to be calculated, we list some of the remaining questions with related observations.
5.1. The Missing Piece: differential structures of games
While our paper defined the Bouton monoid and described an abstruct construction (Section 4.2), there remains the crucial part — the concrete construction of the Bouton monoid. For example, the proof of Proposition 4.14 relies on Theorem 2.17. In that sense, it remains unsatisfactory as a true “demystification” of the nim-sum.
What we should demystify is the proof of Theorem 2.17. The only non-trivial part of the proof is the following equation regarding the nim-sum and the mex operator:
| (6) |
where we adopt the notion for and . Furthermore, this equation recursively determines the value of the nim-sum since is deteremined by choosing and .
The equation (Equation 6) is reminiscent of the integral version of the Leibniz rule, called the Rota-Baxter equation
by regarding the sets as functions, as products, and as integration. This “Rota-Baxter equation” of the nim-sum is a reflection of a more trivial “Leibniz rule” of the Conway addition:
which resembles the genuine Leibniz rule . Note that we see here a kind of the twistedness in Diagram 3 as the “differential part” goes in the opposite direction of the “integral part” .
Expecting the remaining equation (Equation 6) is actually a reflection of some differential structure on , we ask the first question.
Question 5.1.
How do these “differential structures” appear in our formulation, especially for the Bouton monoids with respect to the Conway addition?
Let us describe a partial solution to this question:
Proposition 5.2 (Rota-Baxter equation for the Bouton monoids w.r.t. the Conway addition).
Let be a game value. If the Bouton monoid of with respect to the Conway addition is induced by a -algebra structure , then the monoid structure satisfies the following Rota-Baxter equation:
for any .
Proof.
In this proof, the image of a subset by a function is denoted by . Since the function is surjective by the consturction, for any , we can take such that and . By the assmption that the game value is induced by a -algebra structure , we have , in particular, we have and . As is a monoid homomorphism by the construction, we have
The left-hand side is equal to . The right-hand side is calculated as
This completes the proof. ∎
5.2. Partisan games
What we called games in this paper is usually called impartial games. We intentionally choose to concentrate on impartial games since our central motivation is to demystify the nim-sum. However, in many different contexts, partisam games, games in which a Left-player and a Right-player have different options, are of interest.
Instead of considering , we can alternatively consider to obtain the parallel theory of “partisan games as reursive coalgebras” and to mimick all the abstract nonsenses we used in this paper. (A similar idea of using coalgebras of to study partisan games has already appeared in [HL09].)
Question 5.3.
To which extent the theory of partisan games are comprehended by replacing by ?
For example, we can capture the definition of (short and partisan) Conway games, which is recursively defined as a pair of finite sets of Conway games, as follows:
Proposition 5.4.
The terminal recursive -coalgebra is given by the set of all (short and partisan) Conway games.
5.3. Classification problem of monoidal structures
In order to fathom the applicativity of Theorem 4.8, we would like to classify monoidal structures on . The first question to be asked is the most restrictive one:
Question 5.5.
Classify all symmetric mononoidal closed structures on such that is strictly monoidal.
Notice that the closedness assumption is redundant due to Corollary B.11. A similar research has been recently done for graphs [KK24]. See also [FLK80].
If there are infinitely many examples, we obtain infinitely many applications of Theorem 4.8, and if there are only finitely many examples, we obtain a finite list of all “nicely behaved notions of game-sums,” which may be of independent interest.
As Theorem 4.8 works also for a non-unital monoidal structure, the loosest classification problem regarding Theorem 4.8 is the following one.
Question 5.6.
Classify all non-unital mononoidal structures on such that is lax monoidal.
5.4. Other questions
In the rest of this section, we will list some problems, which might be of interest for some readers.
5.4.1. The closed structure
One can check that the Conway addition structure is symmetric monoidal closed (Corollary B.11) by an anstract argument.
Question 5.7 (The closed structure).
What is the internal hom with respect to the Conway addition?
In the classical context (including [Joy77]), the closedness plays the key role of switching the two players. It makes their category of games compact closed, which categorifies the classical ordered abelian group of Conway games! The closed structure might be better understood when we consider the partisan games (see Section 5.2).
5.4.2. Other types of Bouton monoid: towards circular nim
One of the motivating phenomena of this research is an open problem in combinatorial game theory: the circular nim [DH13]. In circular nim for , piles are arranged on a circle. At each move, a player selects consecutive piles and removes a total of at least one stone from them. The winning strategy for remains an open question [DH13, Section 3].
But how is related to the Bouton monoid? By an easy argument, one can observe that contains as its subgame.
Therefore, as a subproblem of , we need to understand the winning strategy of , which also remains an open question, to the best of the author’s knowledge. In order to decompose the nested structure of the game, one naïve idea is to understand the nested Bouton monoid
Question 5.8.
What is the Bouton monoid ? Is it just the miniture monoid ?
If it is a proper quotient of , it might be a useful tool to tackle ; otherwise, it at least captures one mathematical aspect of the difficulty of . Let us say a game value is essentially indecomposable by a monoidal structure if is bijective. Then, we can ask: is the Grundy number essentially indecomposable by the selective sum? This kind of question might serve as a passive approach to a difficult game in order to mathematically state one aspect of its difficulty.
5.4.3. Other endofunctors
In this paper, we have concentrated on the endofunctor by restraining our categorical desire to generalize it. As we used only simple abstract nonsense, our argument should be able to be categorically generalized.
Question 5.9.
To what extent is our framework categorically generalized? In particular, can it be done for any locally presentable category and any accessible endofunctor ?
This question is of not only categorical interest but also game-theoretic interest. As explained in Section 5.2, is another (possibly the most important) example. We are also interested in other variants like multiplayer games, probabilistic games, linear games, and transfinite games.
Appendix A Existence of the minimum monoid factorizations
In this appendix, we will explain the context and the construction of the minimum monoid factorization (Definition 4.13).
Proposition A.1 (Unique existence and the construction).
For any monoid , any set , and any function , its minimum monoid factorization uniquely exists up to a canonical isomorphism. Furthermore, the monoid homomorphism is surjective, and the corresponding monoid congruence is given by
Proof.
First, we need to prove that the equivalence relation is a monoid congruence. If and , we have
for any , and thus . This proves that is a monoid congruence, and thus the monoid structure on and a surjective monoid homomorphism are well-defined. Furthermore, the function is also well-defined because we have by taking the neutral element as .
So far, we have obtained a factorization . We prove the minimality. Let us take a monoid equipped with a factorization into a monoid homomorphism followed by a function . Then we prove that there exsits a surjective monoid homomorphism from the submonoid such that the following diagram commutes.
 |
As both and are surjective monoid homomorphisms, if a function that makes the left triangle commutative exsits, then it automatically follows that the function is also a surjective monoid homomorphism, and that the right-hand side skew rectangle is also commutative. So it suffices to prove the implication for any . If , then for any , we have , hence . This proves the implication and completes the proof. ∎
The structure of the minimum quotient is by no means anything nontrivial nor advanced – the idea of “minimizing an algebraic structure without losing too much information” is quite mundane as exemplified by the following examples.
Example A.2 (Real numbers in complex numbers).
If you care whether the sum of two complex numbers is real, then it suffices to just keep track of the imaginary parts. This obvious fact can be described as follows. Consider a function defined by
Then, the minimum monoid factorization of (with respect to the additive structure of ) is given by taking the imaginary part .
Example A.3 (Syntactic monoid of a languege).
For a finite set , a language is just a subset of the free monoid . The syntactic monoid of the language is defined as the minimum monoid factorization of the corresponding characteristic function . See some textbooks on the formal language theory, for example [Pin22], for more details on the syntactic monoids.
Remark A.4 (Minimum -algebra factorization).
Actually, any equational theory admits the property like Proposition A.1. In fact, for any -algebra , the complete lattice of -algebra congruences is a complete sublattice of the complete lattice of equivalence relations on the underlying set
which is known in the universal algebra theory ([BS81, II Theorem 5.3]). Due to the adjoint functor theorem, the embedding admits both left and right adjoint, and the right adjoint part provides the desired minimum -algebra factorization. In particular, we have the minimum subgroup factorization, which we need in the context of Remark 4.1.
Remark A.5.
The construction of the minimum monoid factorization is ubiquitous in combinatorial game theory. For example, even the “equality” of games is conventionally defined in this way! See [Sie13].
Appendix B Categorical properties of
In this appendix, we study the categorical properties of and prove Theorem 3.15:
- Theorem B.9:
-
The category of games is locally finitely presentable. In particular, it has all small limits and colimits.
- Proposition B.23:
-
The forgetful functor is comonadic. In particular, it preserves, reflects, and strictly creates all small colimits.
- Proposition B.26:
-
The category of games has a subobject classifier.
We will also prove that
- Corollary B.19:
-
The category of games has the epi-mono orthogonal factorization system.
- Remark B.27:
-
The category of games is not cartesian closed. In particular, it is not a topos.
Remark B.1 (Comparison with locally finite Kripke frames).
In [DG24], the categorical properties of the category of Kripke frames are studied, and then the category of locally finite Kripke frames is studied in the context of the duality in modal logic. As our category of games is a full subcategory of , some arguments in this appendix already appeared in [DG24]. For example, game morphisms correspond to [DG24, Definition 3.3], subgames (Definition B.3) to generated subframe [DG24, Definition 3.7], the descripton of colimits to [DG24, Proposition 3.9], the description of the equalizer to [DG24, Lemma 3.11], the local presentability to [DG24, Theorem 4.3], and the comonadicity to [DG24, Theorem 5.4].
B.1. is locally finitely presentable
We will prove that the category is locally finitely presentable. For those who are not familiar with presentability, the standard textbook is [AR94]. Our proof of the local presentability is very similar to that of [DG24]. As we will check the definition naïvely, we need to know the colimits in first.
Lemma B.2.
The forgetful functor strictly creates all small colimits. In particular, is cocomplete and preserves and reflects them. Furthermore, is conservative.
Proof.
The forgetful functor is decomposed into the two forgetful functors
The first one is fully faithful, and admits a right adjoint of taking the well-founded part ([AMM20, Proposition 4.19]). Therefore, is coreflective subcategory of and the embedding functor is conservative and creates all small colimits. The other one is conservative and creates all small colimits by the general theory of coalgebras of an endofunctor. ∎
Definition B.3 (Subgame).
A subgame of a game is a subset such that if and then .
As we will see later, subgames are almost the same as monomorphisms (Proposition B.18).
Lemma B.4 (Image is a subgame).
For a game morphism , its image is a subgame of .
Proof.
This is due to the path-lifting condition of Definition 3.12. ∎
For any injective game morphism , its image is isomorphic to as games since is conservative (Lemma B.2). Therefore, by abuse of terminology, we will call an injective game morphism a subgame.
Definition B.5.
For a game and a subset , the minimum subgame of that contains is called the subgame generated by .
See Lemma B.21 for its construction.
Lemma B.6.
Any subgame generated by a finite subset is finite.
Proof.
This follows from the two finiteness conditions in the definition of games (Definition 2.1). (cf. Remark 2.4). ∎
Lemma B.7.
Every game is the filtered colimit of (the canonical diagram of) its finite subgames.
Proof.
For any finite subset of a game , the minimum subgame containing is finite. Therefore the canonical diagram is in fact filtered, and Lemma B.2 completes the proof. ∎
Lemma B.8 (Finitely presentable Finite).
A game is finitely presentable if and only if its underlying set is finite.
Proof.
Let us take an arbitrary game . If a game is finitely presentable, Lemma B.7 implies that coincides with its finite subgame, and hence itself is finite.
Conversely, assuming that the underlying set is finite, we will prove that the hom functor
preserves filtered colimits.
Let be a filtered category, be a functor, and be the colimit cocone. Take an arbitrary morphism . Our goal is to prove that there exists such that has a lift along
 |
(The essential uniqueness of the factorization follows from the case of and Lemma B.2.)
Since a finite set is finitely presentable in , and preserves small colimits (in particuler, filtered colimits), there exists a function such that the following diagram commutes
 |
Let be the subgame of , generated by the image of . Since is finite, is also finite (Lemma Lemma B.6). So far, we have onbtained the diagram
 |
where is denoted by a dashed arrow since it is a mere function. Since is a filtered colimit (preserved by ) and is finite, there exists in such that is injective on the subgame of (Lemma B.4). In other words, the morphism in the following diagram is injective.
 |
Because the morphism is injective, the game can be regarded as a subgame of . Therefore, the composite , which is the lift of along , is a game morphism
 |
This proves that has a lift along in the category . ∎
Theorem B.9.
The category of games is locally fintiely presentble.
Proof.
Although we have spent a whole subsection to prove the existence of the terminal object in Section 3.6, we can prove much more stronger statement now.
Corollary B.10.
The category of games is complete.
Proof.
This follows since every locally presentable category is complete. ∎
Corollary B.11.
All the (non-unital or unital) monoidal structure that lifts the cartesian monoidal structure of
 |
is monoidal closed.
Proof.
Due to the adjoint functor theorem for locally presentable categories, it suffices to prove that, for any game , the functor is cocontinuous. This follows from the commutative daigram
 |
and the fact that the forgetful functor reflects colimits (Lemma B.2). ∎
This corollary implies that all of the Conway addition (Definition 2.10), the selective sum (Example 4.3), and the conjunctive sum (Example 4.4) are symmetric monoidal closed structure on . See also Section 5.4.1.
Corollary B.12.
The forgetful functor admits a right adjoint.
Proof.
This also follows from the adjoint functor theorem for locally presentable categories and Lemma B.2. ∎
This adjunction is the subject of the next subsection.
B.2. The forgetful cofree game adjunction
This subsection aims to describe the right adjoint of the forgetful functor , which exsits due to Corollary B.12. We temporarily write for the right adjoint functor and call it the cofree games functor. We already know that should be isomorphic to the terminal game . So we write for the cofree game . Let denote the counit at a set .
We will observe that we can calculate as the initial -algebra and hence by Adamek’s fixed point theorem (cf. Diagram 4)! In fact, we can show that the -coalgebra
is the terminal recursive -coalgebra, and hence given by the initial -algebra (Proposition 3.7). Notice that a -coalgebra is recursive if and only if the -coalgebra is recursive1111 11 One can directly prove it. . Using this fact, for any recursive -coalgebra , the transpose of , which is denoted by , is the unique -coalgebra homomorphism:
 |
This proves that is the terminal recursice -coalgebra, and hence given by Adamek’s fixed point theorem:
| (7) |  |
By the above observations, we obtain the following set-theoretic realization of .
Definition B.13 (Labeled hereditarily finite sets).
For a set (of labels) , a -labeled hereditarily finite set is recursively defined as a pair of a finite set of -labeled hereditarily finite sets and a label . In other words, the set of all -labeled hereditarily finite sets is defined to be
where and .
Just like a hereditarily finite set is a set with a finite number of parentheses, a -labeled hereditarily finite set is a “-labeled set with finite number of -labeled parentheses.” For example, if , a typical element of looks like
| (8) |
Proposition B.14 (Forgetful-Cofree adjunction).
The right adjoint
 |
is given by , where the structure map sends each element to . The counit sends each element to its label .
We will utilize this description of cofree games in the construction of the subobject classifier (Section B.5).
B.3. Some limits in
We have observed that the category has all small limits (Corollary B.10). The only example of small limits we have seen so far is the terminal object (Proposition 3.31). In this subsection, we will calculate some other finite limits.
B.3.1. Inverse image
The first example is the inverse images of subgames.
Lemma B.15.
For any game morphism and a subgame , its inverse image is also a subgame of , and the diagram
 |
is pullback in .
Proof.
One can check it directly. ∎
B.3.2. Monomorphisms
The second example of limits is monomorphisms, which is a morphism whose pullback along itself is given by two identity maps. The observations of monomorphisms in this subsubsection will be utilized to study the subobject classifier (Section B.5).
Just to avoid the following argument becoming wordy, we introduce an accessibility relation in an obvious way:
Definition B.16 (Accessibility relation).
For a game , we say that an element is accessible from if there exists a non-negative integer and a sequence of elements that satisfy
- •
,
- •
for , and
- •
.
This accessibility relation is denoted by .
We write for .
Remark B.17 (Subgames are downward closed subset).
This accessibility relation is just the reflective and transitive closure of , and defines a preorder on the underlying set . Furthermore, due to the “finite time” condition in Definition 2.1, it is a partial order. The notion of subgames (Definition B.3) coincides with the notion of downward closed subsets of the poset.
Proposition B.18 (Subgames Subobjects).
For any game morphism , the following conditions are equivalent:
- (1)
is monic in .
- (2)
is injective.
- (3)
is (canonically isomorphic to) a subgame inclusion.
Proof.
For the equivalence between and , see the comment below Lemma B.4. The implication immediately follows since the forgetful fucntor is faithful.
We prove . Suppose is monic. We prove that by induction on the well-founded order structure . Assuming that holds for any , we prove . We can assume since otherwise the target inequality trivially holds. Assuming , the image of includes and hence all of (Lemma B.4), so the induction hypothesis implies
| (9) |
Let us define as
Since is a subgame of , Lemma B.15 implies that is also a subgame of . Furthermore, is a finite game due to Equation 9.
Adding a new element to , we extend the finite game into a new game . In addition to the relations in , we add a relation for each such that .
One can prove is actually a game, in particular satisfies the finite option condition, due to the finiteness of . Then, for any , the function defined by
is a game morphism. It is because, for any ,
where the first inverse implication holds due to the following argument: Assuming , there exists such that since satisfies the path-lifting property (Definition 3.12). Due to Equation 9, we have , and hence .
For any (possibly non-distinct) , we have a diagram
 |
with the same composite. Since we assumed that is monic, we obtain and . This completes the proof. ∎
As is a faithful left adjoint, a game morphism is an epimorphism if and only if is surjective. As a corollary, the decomposition of a game morphism through the image game provides the epi-mono factorization system of .
Corollary B.19 (Epi-mono orthogonal factorization).
Any game morphism is uniquely factored into a composition of an epimorphism followed by a monomorphism. This data defines an orthogonal factorization system on .
Remark B.20.
In fact, this factorization system coincides with the (Epi, Regular mono) factorization system on the coregular category .
B.3.3. Equalizer
The third example is equalizers.
Lemma B.21 (Generation and Cogeneration of subgames).
For a game and a subset ,
- •
there exists the minimum subgame of that contains .
- •
there exists the maximum subgame of that is contained by .
Proof.
This is an immediate corollary of the general adjoint functor theorem applied to the complete lattice inclusion from the lattice of subgames into the lattice of subsets.
Explicitly, the former subgame is constructed as
and the latter is
∎
The next lemma is essentially the same as [DG24, Lemma3.11].
Lemma B.22 (Equalizer in ).
For any parallel pair of game morphisms , its equalizer is given by
Proof.
For any game morphism such that , the image is a subgame contained by the set-theoretic equalizer . Since is the maximum subgame contained by in the sense of Lemma B.21, we have , and factors through the subgame inclusion . The uniqueness part of the universality trivially holds since is injective. ∎
B.3.4. Digression: General limits and Stirling numbers
As is not continuous, it is not easy to calculate genral limits in . However, there is a (non-efficient) way to calculate limits using the cofree games functor (Section B.2): Take an arbitrary small diagram . Due to Corollary B.10, we know that exists. So we have
where denotes the cofree game functor, which is the right adjoint to (Proposition B.14). Therefore, we conclude that is a subgame of , whose underlying set is given by the -labeled hereditarily finite set . As this observation works for any faithful left adjoint functor , it loses a lot of information and it is not always easy to figure out which subgame is the limit.
Let us demonstrate how general limits are difficult to calculate. For a positive integer , let denote the -state game that looks like Figure 15.
Then, the product game looks like Figure 16.
.
What is happning there? One interpretation is given by regarding as an categorification of the Stirling number of the second kind!
One can easily prove that is the number of surjections from an -element set to an -element set, which is known to be equal to , where is the Stirling number of the second kind.
Therefore, the product game should have information about since the following equality holds.
In fact, the product game (or, more precisely, the isomorphism to its concrete description Figure 16) is a categorification of the multiplicative identity of the Stirling number:
Notice that these coefficients appear in Figure 16.
Even the inocent-looking example is interwinded with the combinatorics of the Stirling numbers. By this example, we would like to emphasize the difficulty of the calculation of general limits in .
B.4. is comonadic over
The following proof is essentially the same as the comonadicity of locally finite Kriple frames [DG24, Theorem 5.4].
Proposition B.23.
The forgetful functor is comonadic.
Proof.
We use the reflexive tripleability theorem (see [Rie17, Propotition 5.5.8]). As we have already proven that is a consevative left adjoint functor (Lemma B.2 and Corollary B.12) and is complete (Corollary B.10), it suffices to prove that preserves equalizers of coreflexive pairs.
Take an arbitrary coreflexive pair with a common retract such that . Then, due to Lemma B.22, the equalizer is given by . We should prove that this coincides with the set-theoretic equalizer .
Therefore, it suffices to prove that, for any , implies . Assuming and , we can take such that by applying the path-lifting property to . By applying the common retract to the equation , we obtain , which implies . This completes the proof. ∎
B.5. has a subobject classifier
In this subsection, we will give an explicit description of the subobject classifier of the category of games.
Our idea of the construction is simple: utilize the cofree-forgetful adjunction (Proposition B.14). As subobjects are just subsets satisfying some properties (Proposition B.18), we have the following canonical injection
| (10) |
Therefore, by the Yoneda lemma, if a subobject classifier exists, then it should be a subobject of the game of truth-values-labeled hereditarily finite sets .
Let us recall how the correspondence in (10) works. Let be a game and be a subset. Then, the corresponding game morphism sends an element to
where “” denotes the element of corresponding to the truth value of the proposition “.” Conversely, for a given game morphism , the corresponding subset is recovered by taking . An example of such (in the case where is a subgame of ) is visualized in Figure 17, where and are colored like (8).
Definition B.24.
A -labeled hereditarily finite set is truth-closed if
- (1)
if itself is labeled by , then every element of is also labeled by , and
- (2)
every element of is truth-closed.
Due to condition (2), truth-closed -labeled hereditarily finite sets form a subgame of . By coloring like (8), the typical examples of a truth-closed -labeled set include , , , and . Non-examples include and . Intuitively, a -labeled hereditarily finite set is truth-closed if and only if no black parenthesis appears within any red parenthesis.
Notation B.25.
The subgame of consisting of all truth-closed -labeled hereditarily finite sets is denoted by .
The game is visualized in Figure 18.
Proposition B.26 (Subobject classifier).
The game is the subobject classifier of the category of games .
Proof.
We prove that, for any subset of any game , is a subgame if and only if the characteristic map factors through the subgame .
Assuming that is a subgame, we prove that is truth-closed for any by induction. At the step of , the condition (2) in Definition B.24 is verified by the induction hypothesis. Regarding condition (1), if is labeled by , i.e., , then every is also labeled by for any , since is a subgame.
Conversely, assume that factors through . Then, for any , is truth-closed and labeled by . Therefore, for every , is also labeled by , which implies that is a subgame. ∎
Remark B.27 ( is not a topos).
The reader may wonder if is a Grothendieck topos, since it satisfies a lot of nice properties like topos, including the existence of a subobject classifier, epi-mono factorization system, the frame structure of the subobject lattice, local finite presentability, and so on. Unfortunately, is not even cartesian closed. In fact, the product functor does not preserve colimits (cf. Figure 15). For example, the colimit of the canonical -action on is . However, the colimit of induced -action on has elements.
This shows that the functor is not cocontinuous; in particular, is neither cartesian closed nor a topos.
Appendix C Birthday Nim Grundy number
The Bouton theorem (Theorem 2.9) looks particularly simple due to the fact that the Grundy number map turns out to be the identity map (cf. Example 2.18). The aim of this appendix is to explain this coincidence by a “categorical origin” of the mex function .
We start with a simple observation.
Proposition C.1.
For an endofunctor on a category , a -algebra , and a recursive -coalgebra on the same object , the following two condtions are equivalent.
- (1)
is the section of , i.e., .
- (2)
The hylomorphism coincides with the identity map .
Proof.
Both conditions are equivalent to the commutativity of
 |
∎
Therefore, unsurprisingly, the coincidence comes from the fact that the structure map of nim is a section of , i.e.,
What might be a bit surprising is that is actually the canonical choice of a retraction of in a categorical sence! When a canonical “reverse” of a map is needed, we category theorists think like “ok, then consider its adjoint!”
 |
And the adjoint turns out to be mex! Here, we consider the usual order on each set, namely, the usual order on and the inclusion relation on .
Proposition C.2 (A characterization of mex).
The right adjoint of is .
 |
Proof.
Take any and . Then, we have
∎
Since is fully faithful, its right adjoint should be a retract of thanks to the general theory of adjoint functors (and the skeletality of the posets). So we can apply Proposition C.1.
Similar phenomena are ubiquitous in this paper. For example, also admits a right adjoint, which turns out to be !
 |
Therefore, Proposition C.1 implies that is also the identity map. This is the meaning of the title of this appendix: Birthday Nim Grundy number, which actually means
Another example is the remoteness.
Example C.3.
The game (Example 2.7) is a section of the remoteness (Example 3.24) up to a canonical bijection.
References
- [Ack37] Wilhelm Ackermann “Die widerspruchsfreiheit der allgemeinen mengenlehre” In Mathematische Annalen 114.1 Springer, 1937, pp. 305–315
- [Adá74] Jiří Adámek “Free algebras and automata realizations in the language of categories” In Commentationes Mathematicae Universitatis Carolinae 15.4 Charles University in Prague, Faculty of MathematicsPhysics, 1974, pp. 589–602
- [Adá05] Jiří Adámek “Introduction to coalgebra” In Theory and Applications of Categories 14.8, 2005, pp. 157–199
- [ALM07] Jiří Adámek, Dominik Lücke and Stefan Milius “Recursive coalgebras of finitary functors” In RAIRO-Theoretical Informatics and Applications 41.4 EDP Sciences, 2007, pp. 447–462
- [AMM20] Jiří Adámek, Stefan Milius and Lawrence Moss “On Well-Founded and Recursive Coalgebras.” In FoSSaCS, 2020, pp. 17–36
- [AR94] Jiří Adámek and Jiří Rosickỳ “Locally Presentable and Accessible Categories” Cambridge University Press, 1994
- [BS09] John. Baez and Michael Shulman “Lectures on n-categories and cohomology” In Towards higher categories Springer, 2009, pp. 1–68
- [BES25] Mikhail Baltushkin, Dana. Ernst and Nándor Sieben “Isomorphism Theorems for Impartial Combinatorial Games” In arXiv preprint arXiv:2505.04919, 2025
- [Baš+24] Bojan Bašić et al. “Categories of impartial rulegraphs and gamegraphs” In International Journal of Game Theory Springer, 2024, pp. 1–27
- [Bou01] Charles. Bouton “Nim, a game with a complete mathematical theory” In Annals of mathematics 3.1/4 JSTOR, 1901, pp. 35–39
- [BS81] Stanley Burris and H.. Sankappanavar “A course in universal algebra” 78, Graduate Texts in Mathematics Springer-Verlag, New York-Berlin, 1981, pp. xvi+276
- [CUV06] Venanzio Capretta, Tarmo Uustalu and Varmo Vene “Recursive coalgebras from comonads” In Information and Computation 204.4 Elsevier, 2006, pp. 437–468
- [CP20] Thomas Colcombet and Daniela Petrişan “Automata minimization: a functorial approach” In Logical Methods in Computer Science 16 Episciences. org, 2020
- [Con00] John. Conway “On numbers and games” AK Peters/CRC Press, 2000
- [DG24] Matteo De and Silvio Ghilardi “Profiniteness, monadicity and universal models in modal logic” In Annals of Pure and Applied Logic 175.7 Elsevier, 2024, pp. 103454
- [DH13] Matthieu Dufour and Silvia Heubach “Circular Nim Games” In the electronic journal of combinatorics 20.2, 2013, pp. P22
- [FLK80] François Foltz, Christian Lair and Gregory. Kelly “Algebraic categories with few monoidal biclosed structures or none” In Journal of Pure and Applied Algebra 17.2 North-Holland, 1980, pp. 171–177
- [HL09] Furio Honsell and Marina Lenisa “Conway games, coalgebraically” In Algebra and Coalgebra in Computer Science: Third International Conference, CALCO 2009, Udine, Italy, September 7-10, 2009. Proceedings 3, 2009, pp. 300–316 Springer
- [Jac16] Bart Jacobs “Bisimulations” In Introduction to Coalgebra: Towards Mathematics of States and Observation, Cambridge Tracts in Theoretical Computer Science Cambridge University Press, 2016, pp. 114–158
- [Jac17] Bart Jacobs “Introduction to coalgebra” Cambridge University Press, 2017
- [Joy77] André Joyal “Remarques sur la théorie des jeux à deux personnes” In Gazette des sciences mathématiques du Québec 1.4, 1977, pp. 46–52
- [KK24] Krzysztof Kapulkin and Nathan Kershaw “Closed symmetric monoidal structures on the category of graphs” In Theory and Applications of Categories 41.23, 2024, pp. 760–784
- [Kun13] Kenneth Kunen “Set Theory” 34, Studies in logic College Publications, 2013
- [Lam68] Joachim Lambek “A fixpoint theorem for complete categories” In Mathematische Zeitschrift 103.2 Springer, 1968, pp. 151–161
- [Mac98] Saunders Mac “Categories for the working mathematician”, Graduate Texts in Mathematics Springer-Verlag, New York, 1998, pp. xii+314
- [Osi74] Gerhard Osius “Categorical set theory: a characterization of the category of sets” In Journal of Pure and Applied Algebra 4.1 Elsevier, 1974, pp. 79–119
- [Pin22] Jean-Éric Pin “Mathematical foundations of automata theory”, 2022
- [Poh73] Věra Pohlová “On sums in generalized algebraic categories” In Czechoslovak Mathematical Journal 23.2 Institute of Mathematics, Academy of Sciences of the Czech Republic, 1973, pp. 235–251
- [Rie17] Emily Riehl “Category theory in context” Courier Dover Publications, 2017
- [Sie13] Aaron. Siegel “Combinatorial game theory” American Mathematical Soc., 2013
- [Smi66] Cedric.B. Smith “Graphs and composite games” In Journal of Combinatorial Theory 1.1 Academic Press, 1966, pp. 51–81
- [Tay99] Paul Taylor “Practical foundations of mathematics” Cambridge University Press, 1999