\documentclass{amsart} \usepackage[left=2cm, right=2cm]{geometry} \usepackage[utf8]{inputenc} \usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox} \usepackage{blindtext} \usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref} \usepackage{tikz,tikz-cd} \usepackage{array} \usepackage{pifont} \usepackage{cleveref} \usepackage[style=alphabetic,sorting=nyt, maxnames=4]{biblatex} \renewbibmacro{in:}{} % \addbibresource{biblio.bib} \addbibresource{CommonBiblio20240922.bib} \addbibresource{GamesAsWellFoundedCoalgebras.bib} \tikzset{pullback/.style={minimum size=1.2ex,path picture={ \draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);% }}} \usetikzlibrary{positioning} \usetikzlibrary{calc} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{todo}[theorem]{Todo} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{fact}[theorem]{Fact} \theoremstyle{definition} \newtheorem{example}[theorem]{Example} \newtheorem{definition}[theorem]{Definition} \newtheorem{notation}[theorem]{Notation} \newtheorem{question}[theorem]{Question} \newtheorem{idea}[theorem]{Idea} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\dq}[1]{``#1"} \newcommand{\memo}[1]{\textcolor{red}{memo: #1}} \newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}} \newcommand{\para}[1]{\paragraph{\textbf{#1}}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathcal{C}} \newcommand{\comp}{\mathbb{C}} \newcommand{\D}{\mathcal{D}} \newcommand{\E}{\mathcal{E}} \newcommand{\F}{\mathcal{F}} \newcommand{\id}{\mathrm{id}} \newcommand{\op}{\mathrm{op}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\Top}{\mathbf{Top}} \newcommand{\Cat}{\mathbf{Cat}} \newcommand{\Group}{\mathbf{Group}} \newcommand{\FinSet}{\mathbf{FinSet}} \newcommand{\PSh}{\mathbf{PSh}} \newcommand{\Sh}{\mathbf{Sh}} \newcommand{\Func}[2]{[#1,#2]} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\demph}[1]{\textbf{#1}} \newcommand{\ob}{\mathrm{ob}} \newcommand{\X}{\mathbb{X}} \newcommand{\Y}{\mathbb{Y}} \newcommand{\W}{\mathbb{W}} \newcommand{\gS}{\mathbb{S}} \newcommand{\A}{\mathbb{A}} \newcommand{\I}{\mathbb{I}} \newcommand{\0}{\mathbb{0}} \newcommand{\1}{\mathbb{1}} \newcommand{\Pow}{\mathcal{P}} \newcommand{\Pf}{\Pow_{\mathrm{fin}}} \newcommand{\Gs}{\mathbf{Games}} \newcommand{\Graphs}{\mathbf{Graphs}} \newcommand{\nsum}{\oplus} \newcommand{\Alg}[1]{\mathbf{Alg}_{#1}} \newcommand{\Coalg}[1]{\mathbf{Coalg}_{#1}} \newcommand{\RecCoalg}[1]{\mathbf{RecCoalg}_{#1}} \newcommand{\PfAlg}{\Alg{\Pf}} \newcommand{\PfCoalg}{\Coalg{\Pf}} % \newcommand{\mex}[1]{\mathrm{mex}(#1)} \newcommand{\rel}{\to} \newcommand{\red}{\mathrm{red}} \newcommand{\cp}{\ast} \newcommand{\acc}{\rightsquigarrow} \newcommand{\str}{\theta} \newcommand{\Image}{\mathrm{Im}} \newcommand{\HF}{\mathbb{HF}} \newcommand{\Nim}[1]{\mathrm{Nim}_{#1}} \newcommand{\strNim}[1]{\mathrm{strNim}_{#1}} \newcommand{\ElM}{\mathrm{ElM}} \renewcommand{\H}{\mathbb{H}} \newcommand{\epi}{twoheadrightarrow} \newcommand{\mono}{rightarrowtail} \newcommand{\RB}{\mathcal{H}} \newcommand{\B}{\mathcal{B}} % \newcommand{\rd}{\mathrm{rd}} \newcommand{\ADJ}[4] { \begin{tikzcd}[ampersand replacement = \&, column sep = small] {#1} \ar[rr, shift right=1.3ex, "{#2}"'] \&\perp\& {#3} \ar[ll, shift right=1.3ex,"{#4}"'] \end{tikzcd} } \DeclarePairedDelimiter{\gen}{\langle}{\rangle} \newcommand{\oc}{\mathsf{Outcome}} \newcommand{\Moc}{\mathsf{MOutcome}} \newcommand{\rd}{\mathsf{Red}} \newcommand{\Ind}{\mathsf{Ind}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\np}{\mathsf{np}} \newcommand{\MNP}{\mathsf{MNP}} \newcommand{\mnp}{\mathsf{mnp}} \newcommand{\End}{\mathsf{End}} \newcommand{\Empty}{\mathsf{Empty}} \newcommand{\emptyFunc}{\mathsf{empty}} \newcommand{\True}{\mathsf{True}} \newcommand{\FinTime}{\mathsf{FinTime}} \newcommand{\mex}{\mathsf{mex}} \newcommand{\xem}{\mathsf{xem}} \newcommand{\Mex}{\mathsf{Mex}} \newcommand{\Xem}{\mathsf{Xem}} \newcommand{\hylo}{\mathsf{hylo}} % \newcommand{\G}[2]{\mathcal{G}_{#1}(#2)} \newcommand{\G}{\mathsf{Grundy}} \newcommand{\BirthDay}{\mathsf{BirthDay}} \newcommand{\Remoteness}{\mathsf{Remoteness}} \newcommand{\rbmult}{{\ast_{\H}}} % \title{Games as recursive coalgebras\\ A categorical % % characterization and generalization of % view on the % Nim-sum} \title{A categorical % characterization and generalization of view on the Nim-sum, or \\ combinatorial games as recursive coalgebras} % \subtitle{AA} \author{Ryuya Hora} \subjclass[2020]{91A46, 18C50, 03B70} \keywords{Keywords} \address{Graduate School of Mathematical Sciences, University of Tokyo, Tokyo, Japan} \email{hora@ms.u-tokyo.ac.jp} \date{\today} \begin{document} \begin{abstract} In 1901, Bouton proved that a winning strategy of the nim game is given by the bit-wise 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 \textit{recursive coalgebras}, which allows us to redefine games as ``graphs on which we can conduct recursive calculation'' in a concise 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. % categorical generalization of Nim-sum called the Bouton monoid, and a categorical characterization of the Nim-sum. % The category theory used here is so elementary that combinatorial game theorists who are not familiar with advanced category theory may be soon able to use it. For category theorists, this paper offers a nicely behaved category of games $\Gs$, which is a locally finitely presentable symmetric monoidal closed category comonadic over $\Set$ admitting a subobject classifier! % and a strong monoidal comonadic forgetful functor $\Gs \to \Set$! As this paper has several ways to be developed, we list $123$\memo{rewrite} open questions in the final section. \end{abstract} \maketitle \tableofcontents \section{Introduction} % \subsection{Bouton's theorem: the winning strategy of Nim} \subsection{Why does nim-sum work?} \invmemo{Context in combinatorial game theory} In 1901, Bouton discovered the remarkable (and now very famous) winning strategy of the game \demph{nim} in \cite{bouton1901nim}. % Bouton's classical result \cite{bouton1901nim}\footnote{This is published in 1901, not 2001.} provides a winning strategy of Nim, with the notion of \demph{Nim-sum}. In $n$-heap nim, there are $n$ heaps of stones, with $a_1, \dots, a_n$ stones in each heap. Two players take turns removing stones, but on each turn, they must remove stones from one heap (and \dq{removing $0$ stones} is not allowed.) The player who can no longer make a move loses\footnote{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 $a_1 = a_2 = \cdots = a_n = 0$ from the start.}. For example, \Cref{fig:NimPlay} is a typical play from the state $(a_1,a_2,a_3)=(2,3,3)$, where $A$ wins. \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick, scale=0.7] % Layout parameters \def\rowgap{3.0} % vertical gap between states \def\r{0.8} % radius of each heap circle \def\dx{2.0} % horizontal spacing between heaps %----------------------- % Row 0: (2,3,2) %----------------------- \coordinate (R0) at (0, 0*\rowgap); \path (R0) ++(-\dx,0) coordinate (R0H1); \path (R0) ++( 0, 0) coordinate (R0H2); \path (R0) ++( \dx,0) coordinate (R0H3); \draw (R0H1) circle (\r); \draw (R0H2) circle (\r); \draw (R0H3) circle (\r); % Stones \fill ($(R0H1)+(-0.25,0)$) circle (2pt); \fill ($(R0H1)+( 0.25,0)$) circle (2pt); \fill ($(R0H2)+(-0.30, 0.20)$) circle (2pt); \fill ($(R0H2)+( 0.00,-0.25)$) circle (2pt); \fill ($(R0H2)+( 0.30, 0.20)$) circle (2pt); \fill ($(R0H3)+(-0.25,0)$) circle (2pt); \fill ($(R0H3)+( 0.25,0)$) circle (2pt); \node[right] at ($(R0H3)+(\r+0.6,0)$) {$(2,3,2)$}; %----------------------- % Row 1: (2,3,1) %----------------------- \coordinate (R1) at (0, -1*\rowgap); \path (R1) ++(-\dx,0) coordinate (R1H1); \path (R1) ++( 0, 0) coordinate (R1H2); \path (R1) ++( \dx,0) coordinate (R1H3); \draw (R1H1) circle (\r); \draw (R1H2) circle (\r); \draw (R1H3) circle (\r); \fill ($(R1H1)+(-0.25,0)$) circle (2pt); \fill ($(R1H1)+( 0.25,0)$) circle (2pt); \fill ($(R1H2)+(-0.30, 0.20)$) circle (2pt); \fill ($(R1H2)+( 0.00,-0.25)$) circle (2pt); \fill ($(R1H2)+( 0.30, 0.20)$) circle (2pt); \fill ($(R1H3)+(0,0)$) circle (2pt); \node[right] at ($(R1H3)+(\r+0.6,0)$) {$(2,3,1)$}; \draw[->] ($(R0)+(0,-1.1)$) -- ($(R1)+(0,1.1)$) node[midway,right] {$A$}; %----------------------- % Row 2: (1,3,1) %----------------------- \coordinate (R2) at (0, -2*\rowgap); \path (R2) ++(-\dx,0) coordinate (R2H1); \path (R2) ++( 0, 0) coordinate (R2H2); \path (R2) ++( \dx,0) coordinate (R2H3); \draw (R2H1) circle (\r); \draw (R2H2) circle (\r); \draw (R2H3) circle (\r); \fill ($(R2H1)+(0,0)$) circle (2pt); \fill ($(R2H2)+(-0.30, 0.20)$) circle (2pt); \fill ($(R2H2)+( 0.00,-0.25)$) circle (2pt); \fill ($(R2H2)+( 0.30, 0.20)$) circle (2pt); \fill ($(R2H3)+(0,0)$) circle (2pt); \node[right] at ($(R2H3)+(\r+0.6,0)$) {$(1,3,1)$}; \draw[->] ($(R1)+(0,-1.1)$) -- ($(R2)+(0,1.1)$) node[midway,right] {$B$}; %----------------------- % Row 3: (1,0,1) %----------------------- \coordinate (R3) at (0, -3*\rowgap); \path (R3) ++(-\dx,0) coordinate (R3H1); \path (R3) ++( 0, 0) coordinate (R3H2); \path (R3) ++( \dx,0) coordinate (R3H3); \draw (R3H1) circle (\r); \draw (R3H2) circle (\r); \draw (R3H3) circle (\r); \fill ($(R3H1)+(0,0)$) circle (2pt); \fill ($(R3H3)+(0,0)$) circle (2pt); \node[right] at ($(R3H3)+(\r+0.6,0)$) {$(1,0,1)$}; \draw[->] ($(R2)+(0,-1.1)$) -- ($(R3)+(0,1.1)$) node[midway,right] {$A$}; %----------------------- % Row 4: (1,0,0) %----------------------- \coordinate (R4) at (0, -4*\rowgap); \path (R4) ++(-\dx,0) coordinate (R4H1); \path (R4) ++( 0, 0) coordinate (R4H2); \path (R4) ++( \dx,0) coordinate (R4H3); \draw (R4H1) circle (\r); \draw (R4H2) circle (\r); \draw (R4H3) circle (\r); \fill ($(R4H1)+(0,0)$) circle (2pt); \node[right] at ($(R4H3)+(\r+0.6,0)$) {$(1,0,0)$}; \draw[->] ($(R3)+(0,-1.1)$) -- ($(R4)+(0,1.1)$) node[midway,right] {$B$}; %----------------------- % Row 5: (0,0,0) %----------------------- \coordinate (R5) at (0, -5*\rowgap); \path (R5) ++(-\dx,0) coordinate (R5H1); \path (R5) ++( 0, 0) coordinate (R5H2); \path (R5) ++( \dx,0) coordinate (R5H3); \draw (R5H1) circle (\r); \draw (R5H2) circle (\r); \draw (R5H3) circle (\r); \node[right] at ($(R5H3)+(\r+0.6,0)$) {$(0,0,0)$}; \draw[->] ($(R4)+(0,-1.1)$) -- ($(R5)+(0,1.1)$) node[midway,right] {$A$}; \end{tikzpicture} \caption{A play of $3$-heap Nim, where $A$ wins.} \label{fig:NimPlay} \end{figure} Bouton's winning strategy is based on a nicely designed group structure on $\N$ called \demph{nim-sum}. (We will define the nim-sum again in a more formal way in \Cref{def:NimSum2}.) \begin{definition}\label{def:NimSum} The \demph{nim-sum} of two natural numbers is the bit-wise excluded disjunction. \end{definition} For example, the nim-sum of $3$ and $5$ is $6$ (\Cref{fig:NimSum}). \begin{figure}[ht] \centering \begin{tikzpicture}[thick,>=Latex,scale=1] % sizes \def\w{0.6} % cell width \def\h{0.8} % cell height % column positions (3 bits) \coordinate (C2) at (0,0); \coordinate (C1) at (\w,0); \coordinate (C0) at (2*\w,0); % helper to draw a digit (no box) \newcommand{\digit}[3]{% % #1: anchor coord, #2: text, #3: yshift rows \node at ($(#1)+(0.5*\w,-#3*\h-0.5*\h)$) {$#2$}; } % row 1: 3 = 0 1 1 \node[anchor=east] at ($(C2)+(-0.5*\w,-0.5*\h)$) {$3=$}; \digit{C2}{0}{0} \digit{C1}{1}{0} \digit{C0}{1}{0} % row 2: 5 = 1 0 1 \node[anchor=east] at ($(C2)+(-0.5*\w,-1.5*\h)$) {$5=$}; \digit{C2}{1}{1} \digit{C1}{0}{1} \digit{C0}{1}{1} % % XOR symbol on the left % \node at ($ (C2)+(-1.5*\w,-1*\h)$) {$\nsum$}; % separator line (extended to cross entire width) \draw[very thick] ($(C2)+(-1.8*\w,-2*\h)$) -- ($(C0)+(\w,-2*\h)$); % result row: 6 = 1 1 0 \node[anchor=east] at ($(C2)+(-0.5*\w,-2.5*\h)$) {$6=$}; \digit{C2}{1}{2} \digit{C1}{1}{2} \digit{C0}{0}{2} \node[anchor=east] at ($(C2)+(-\w,-1*\h)$) {$\nsum$}; \end{tikzpicture} \caption{Nim-sum calculation: $3\oplus 5=6$ since $011\oplus 101=110$ in binary expression} \label{fig:NimSum} \end{figure} Bouton's theorem \cite{bouton1901nim} claims that the winning strategy of nim is to make move so that the resulting state $(a_1, \dots, a_n)$ has $0$ as its nim-sum $a_1 \nsum \dots \nsum a_n$. One can check that the player $A$ conduct the winning strategy in \Cref{fig:NimPlay}. 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 \cite{siegel2013combinatorial}.) % \subsection{Why does nim-sum work?} 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: \dq{I understand that it works, but \demph{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\memo{cref}. Although our characterization is not yet fully satisfying to call a \dq{conceptual understanding}\memo{cref}, we expect that our framework serves as a theoretical foundation for further research\footnote{A follow-up paper, which is a joint work with Ryo Suzuki, will be uploaded later.}. \subsection{Recursion in game theory and coalgebra theory} 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 \cite{siegel2013combinatorial}). In his book \textit{On numbers and games} \cite[][]{conway2000numbers}, John H. Conway discuss foundations of mathematics and say % \cite[\textit{Appendix to Part Zero} of \textit{On Numbers and Games}][]{conway2000numbers} \begin{quote} [...] all that is needed to justify the induction is the principle: % \\ \dq{If $P$ is some proposition that holds for $x$ whenever it holds for all $x^L$ and $x^R$, then $P$ holds universally.} \cite[Appendix to Part Zero,][]{conway2000numbers} \end{quote} In category theory, this kind of recursion scheme is dealt by \demph{recursive coalgebras}, which we will recall in \cref{ssec:PreliminariesOnCoalgebraicMethod}. The notion of recursive coalgebra firstly appears in \cite[Section 6,][]{osius1974categorical} in the context of categorical (or topos-theoretic) set theory, and then was generalized and developed in \cite{taylor1999practical}. % Our fomulation of games as recursive coalgebras is exactly this % On the other hand, category theory has been providing a theoretical tool to deal with many kinds of recursions. % This paper proposes to regard a game as a \demph{recursive coalgebra}, which is a categorical notion in coalgebra theory. Let us explain what it is and why it suits our aim. % This paper provides a convenient categorical framework for combinatorial game theory, and as its application, de \subsection{Our contribution} \begin{itemize} \item The notion of Bouton monoid \item Game theoretic view on the recursion theory \item Provides a unifying method to decompose game into smaller parts \item Provide a new category of games with nice properties \item Provides new project frameworks and open problems \end{itemize} \subsubsection{Related works} \para{Context in category theory} History: \url{https://ncatlab.org/nlab/show/game+theory} Category of games \begin{itemize} \item \cite{joyal1977remarques} \item \cite{blass1992game} \item \cite{laird2013constructing} \end{itemize} Recursive coalgebras \begin{itemize} \item \cite{osius1974categorical} introduced it in the context of categorical set theory. Paul Taylor defined it or general functor. \cite{taylor1999practical} \item Well-foundedness and recursiveness \cite{adamek2020well} \end{itemize} \para{Context in Logics and computer science} \para{Conway's appendix} \textbf{Acknowledgement} The first-named author would like to thank his supervisor, Ryu Hasegawa, for helpful discussions and suggestions. He was supported by JSPS KAKENHI Grant Number JP24KJ0837 and FoPM, WINGS Program, the University of Tokyo. % I would like to thank my supervisor Ryu Hasegawa for his continuous support and advice, and also for suggesting me to consider hylomorphisms in this context, which turns out to be crucial. % I would like to thank Ryo Suzuki, for suggesting me to consider Nim-sum through the Ackermann interpretation. % I would like to thank my appreciation to Tomoaki Abuku, Suetsugu, Paul Taylor, Takeshi Tsukada, Kazuyuki Asada, Keisuke Hoshino for thier discussions. % I extend my graditude for Syoei Suzuki for the discussion. I would like to express my gratitude to my supervisor, Ryu Hasegawa, for his continual support and guidance, and for suggesting that I consider hylomorphisms in this context, which proved to be essential. I am also grateful to Ryo Suzuki for recommending the use of Nim-sum through the Ackermann interpretation. My appreciation extends to Tomoaki Abuku, Koki Suetsugu, Paul Taylor, Takeshi Tsukada, Kazuyuki Asada, Syoei Suzuki, Kyosuke Higashida, Ivan Di Liberti, and Keisuke Hoshino for their valuable discussions, and Math Space topos and Kanda Lab for offering me a discussion place. % Finally, I would like to thank Syoei Suzuki, Kyosuke Higashida for engaging in discussions with me. Throughout this paper, $\N$ denotes the set of all non-negative integers $\N = \{0,1,2, \dots\}$. \para{Motivation to consider recursive coalgebras?} \begin{description} \item[Philosophical motivation] motivation is that combinatorial game theory is inherently recursive. \memo{Write about Conway's word} \item[Game-theoretic] Why nim-sum works? \item[Categorical] locally finitely presentable + epi-mono factorization + subobject classifier \end{description} \subsubsection{Related works} Categories that subsume our category: \begin{itemize} \item The category of Kripke models and p-morphisms. \item The category of game graphs. \end{itemize} \memo{compare with \cite{bavsic2024categories}} Category of games %\newpage \section{Games as graphs}\label{sec:GamesasGraphs} In this section, we recall \dq{classical} game-theoretic notions and phenomena, which will be reinterpreted and generalized later. For more details, see \cite{siegel2013combinatorial}. \subsection{Games and Outcomes} % \subsubsection{Elementary definition of games} Since the notion of a game is very fundamental, it has been studied from many perspectives, and a lot of different mathematical formulations have been given. In this paper, we begin our discussion with a graph-theoretic\footnote{Actually, this is not quite graph-theoretic in the sense of \Cref{rem:NotGraphStructureAndProperties}} formulation of impartial combinatorial games. Some other kinds of games will be mentioned as remarks\memo{cref}. % There are so many different definitions of impartial games. \memo{add bib} In this paper, we adopt a graph-theoretic one. The idea of the formulation is quite simple; a vertex is a state of the game, and an edge is a possible move. \begin{definition}[(impartial) games]\label{def:game} A \demph{game} $\X$ is a pair $\X = (X, \rel)$ of a (possibly infinite) set $X$ and a relation ${\rel}\subset X \times X$ that satisfies two finiteness conditions: \begin{enumerate} \item (finite options) For any $x \in X$, the number of options $\# \{x' \in X \mid x\rel x'\}$ is finite. \item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$ \end{enumerate} \end{definition} For example, \Cref{fig:FiniteGame} and \Cref{fig:InfiniteGame} are games, but \Cref{fig:LoopNonGame}, \Cref{fig:InfiniteNonGame}, and \Cref{fig:InfiniteOptionNonGame} are not games. \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick] % ===== Vertices ===== \node[circle, fill=black, inner sep=3pt, label=above:{}] (A) at (0,0) {}; \node[circle, fill=black, inner sep=3pt, label=above:{}] (B) at (2,0) {}; \node[circle, fill=black, inner sep=3pt, label=above:{}] (C) at (4,0) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (D) at (0.5,-1.2) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (E) at (2,-1.2) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (F) at (3.5,-1.2) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (G) at (1,-2.4) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (H) at (3,-2.4) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (T1) at (0.5,-3.6) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (T2) at (3.5,-3.6) {}; % ===== Arrows ===== \draw[->] (A) -- (D); \draw[->] (A) -- (E); \draw[->] (B) -- (E); \draw[->] (B) -- (F); \draw[->] (C) -- (F); \draw[->] (D) -- (G); \draw[->] (E) -- (G); \draw[->] (E) -- (H); \draw[->] (F) -- (H); \draw[->] (G) -- (T1); \draw[->] (G) -- (T2); \draw[->] (H) -- (T2); % ===== Curved extra arrow ===== \draw[->] (A) to[bend right] (G); \draw[->] (C) to[bend left] (T2); \end{tikzpicture} \caption{An example of a finite game} \label{fig:FiniteGame} \end{figure} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick] % Invisible node at the far left (for incoming arrow) \node[circle, fill=black, inner sep=3pt, opacity=0] (Linf) at (-6.3,0) {}; % Dots to indicate infinite continuation to the left \node at (-6.5,0) {$\cdots$}; % Visible nodes \node[circle, fill=black, inner sep=3pt] (L2) at (-4,0) {}; \node[circle, fill=black, inner sep=3pt] (L1) at (-2,0) {}; \node[circle, fill=black, inner sep=3pt] (O) at ( 0,0) {}; \node[circle, fill=black, inner sep=3pt] (R1) at ( 2,0) {}; % \node[circle, fill=black, inner sep=3pt] (R2) at ( 4,0) {}; % right endpoint % Arrows from left to right (ending at R2) \draw[->] (Linf) -- (L2); \draw[->] (L2) -- (L1); \draw[->] (L1) -- (O); \draw[->] (O) -- (R1); % \draw[->] (R1) -- (R2); \end{tikzpicture} \caption{An example of an infinite game} \label{fig:InfiniteGame} \end{figure} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick] % ===== Single vertex ===== \node[circle, fill=black, inner sep=3pt, label=above:{}] (v) at (0,0) {}; % ===== Self-loop (adjust angles / looseness as needed) ===== \draw[->] (v) to[out=45, in=135, looseness=20] (v); % Examples (toggle one if you prefer a different loop position/size): % \draw[->] (v) to[out=315, in=225, looseness=8] (v); % loop below % \draw[->] (v) to[out=0, in=60, looseness=10] (v); % loop right % \draw[->] (v) to[out=120, in=180, looseness=6] (v); % loop left \end{tikzpicture} \caption{An example of non-game with infinite path} \label{fig:LoopNonGame} \end{figure} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick] % Invisible nodes at the far left and far right \node[circle, fill=black, inner sep=3pt, opacity=0] (L3) at (-6,0) {}; \node[circle, fill=black, inner sep=3pt, opacity=0] (R3) at ( 6,0) {}; % Dots to indicate infinite continuation \node at (-6.5,0) {$\cdots$}; \node at ( 6.5,0) {$\cdots$}; % Visible nodes \node[circle, fill=black, inner sep=3pt] (L2) at (-4,0) {}; \node[circle, fill=black, inner sep=3pt] (L1) at (-2,0) {}; \node[circle, fill=black, inner sep=3pt] (O) at ( 0,0) {}; \node[circle, fill=black, inner sep=3pt] (R1) at ( 2,0) {}; \node[circle, fill=black, inner sep=3pt] (R2) at ( 4,0) {}; % Arrows from left to right \draw[->] (L3) -- (L2); \draw[->] (L2) -- (L1); \draw[->] (L1) -- (O); \draw[->] (O) -- (R1); \draw[->] (R1) -- (R2); \draw[->] (R2) -- (R3); \end{tikzpicture} \caption{Another example of non-game with infinite path} \label{fig:InfiniteNonGame} \end{figure} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick] % Top vertex \node[circle, fill=black, inner sep=3pt, label=above:{}] (U) at (0,1.5) {}; % Bottom row vertices (finite sample + dots to the right) \node[circle, fill=black, inner sep=3pt, label=below:{}] (V1) at (0,0) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (V2) at (2,0) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (V3) at (4,0) {}; \node[circle, fill=black, inner sep=3pt, label=below:{}] (V4) at (6,0) {}; \node at (7,0) {$\cdots$}; % Arrows from U to each visible bottom node \draw[->] (U) -- (V1); \draw[->] (U) -- (V2); \draw[->] (U) -- (V3); \draw[->] (U) -- (V4); % (Optional) dashed arrow towards the dots, to suggest infinitely many \draw[->, dashed] (U) -- (6.8,0.2); \end{tikzpicture} \caption{An example of non-game with infinite options} \label{fig:InfiniteOptionNonGame} \end{figure} The ultimate goal of combinatorial game theory is to win a given game. To win a game is almost the same thing as knowing \demph{outcome}, \dq{$N$-states} (Next-player-winning states) or \dq{$P$-states} (Previous-player-winning states), defined as follows. % its winning states and losing states. \begin{definition}[Outcome]\label{def:outcome} For a game $\X=(X, \rel)$ and its state $x\in X$, the outcome of $x$ is defined by \[ \oc_{\X}(x)\coloneqq \begin{cases} N& \text{(if the next player wins from the state $x$)}\\ P& \text{(if the previous player wins from the state $x$),} \end{cases} \] or equivalently, it is recursively defined by \[ \oc_{\X}(x)\coloneqq \begin{cases} N& \text{(if there exists $x\rel x'$ whose outcome is $P$.)}\\ P& \text{(otherwise)} \end{cases} \] \end{definition} The latter recursive definition is not circuler, thanks to the \dq{finite time} condition. \begin{remark}[How can we win with outcome?] % Once you know the outcome function $\oc\colon X \to \{N,P\}$, you can win the game from any $N$-state $x$. Only thing you should do it to move $x$ to a $P$-state, which exists by the definition of $P$-state. Then, by definition of $P$-state, the opponent must move from a $P$-state to an $N$-state. Due to the finite time condition, the game should terminate somewhere. For those who are not familiar with combinatorial game theory, let us clarify the connection between an actual ways to win a game $\X=(X, {\rel})$ and the outcome function $\oc\colon X \to \{N,P\}$. Suppose it is your turn and the current position is an $N$-state. Then \demph{the winning strategy is simply to always move to a $P$-state.} By the definition of $P$-states, your opponent cannot reply with another $P$-state. The opponent must either move to an $N$-state, or lose immediately. In the latter case, by the definition of $N$-states, you can move to a $P$-state again. Due to the finite time condition, this procedure must terminate, and therefore you are guaranteed to win. \end{remark} \begin{remark}[Why do we assume the \dq{finite options} condition?]\label{rem:finiteOptions} We include the finite options condition in \Cref{def:game}. 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. (More precisely, we need it to keep Grundy number to be finite ordinal.) A categorical reason is that the considered functor $\Pf\colon \Set \to \Set$ is finitary (\cite[Example 2.5, Example 3.18]{adamek2007recursive}) and hence our category of games admits a lot of pleasant properties\memo{cref}) In particular, thanks to the finite option condition, we have the terminal game, which plays the central role in our characterization of nim-sum.\memo{cref}) % In order to define Grundy number. % The existence of the terminal game. % The finitary endo fucntor. % \invmemo{Local finiteness is important} \end{remark} \begin{example}[Winning strategy of the subtraction nim]\label{exmp:SubtractionNim}Let us give a famous example of the outcome function. A {subtraction nim} (for $S=\{1,2,3\}$) is $(\N, {\rel})$, where \[ n\rel m \iff n=m+1, m+2, \text{or }m+3. \] We can (recursively) prove that the outcome function is given by \[ \oc(n)= \begin{cases} N &(n\not\equiv 0 \mod 4)\\ P &(n\equiv 0 \mod 4). \end{cases} \] So the winning strategy is to move to the multiples of $4$. \end{example} % The next example is not well-known (at least in the following form), but will turn out to be theoretically important and is worth being called \demph{the universal game}. Theoretically, the most important game might be the following game, which we will call the binary exponent nim, (or the terminal game\memo{cref}). \begin{example}[Binary exponent nim, or the terminal game]\label{exmp:BinaryExponentNimOrTerminalGame} % The underlying set of the universal game is g % \end{example} % \begin{remark}[The universal game of natural numbers] % Since the terminal object is defined by universality, it is unique up to canonical isomorphism. Another description of the terminal object is given by \demph{Ackerman's interpretation} of hereditarily finite sets. \memo{ref} The underlying set of the binary exponent nim is $\N$, and the relation $n \rel m$ is defined by \[n \rel m \iff 2^m \text{ appears in the binary expansion of }n.\] For example, when $n=10000$, since \[ n=10000=2^{13}+2^{10}+2^{9}+2^{8}+2^{4}, \] there are $5$ possible moves, namely $10000\rel4,8,9,10,13$. The state $n=10000$ is $N$-state, and the winning way it to move to $8$ or $10$ (\Cref{fig:BinaryExponentNim}). % because the next player can move to $8$, then the opponet has no choice other than moving to $3$, and the last move $3\rel 0$ terminates the game. \end{example} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick, node distance=12mm and 14mm] % === Nodes (placed roughly by "levels") === \node[circle, fill=red, inner sep=3pt, label=above:{10000}] (N10000) at (0,1) {}; \node[circle, fill=red, inner sep=3pt, label=left:{13}] (N13) at (-4,-1) {}; \node[circle, fill=blue, inner sep=3pt, label=left:{10}] (N10) at (-2,-1) {}; \node[circle, fill=red, inner sep=3pt, label=left:{9}] (N9) at ( 0,-1) {}; \node[circle, fill=blue, inner sep=3pt, label=right:{8}] (N8) at ( 2,-1) {}; \node[circle, fill=red, inner sep=3pt, label=right:{4}] (N4) at ( 4,-1) {}; \node[circle, fill=red, inner sep=3pt, label=right:{3}] (N3) at (0,-3) {}; \node[circle, fill=blue, inner sep=3pt, label=right:{2}] (N2) at (0,-5) {}; \node[circle, fill=red, inner sep=3pt, label=right:{1}] (N1) at (0,-7) {}; \node[circle, fill=blue, inner sep=3pt, label=right:{0}] (N0) at (0,-9) {}; % === Edges === \draw[->] (N10000) -- (N13); \draw[->] (N10000) -- (N10); \draw[->] (N10000) -- (N9); \draw[->] (N10000) -- (N8); \draw[->] (N10000) -- (N4); \draw[->] (N13) -- (N3); \draw[->] (N13) -- (N2); \draw[->] (N13) to[bend right] (N0); \draw[->] (N10) -- (N3); \draw[->] (N10) to[bend right] (N1); \draw[->] (N9) -- (N3); \draw[->] (N9) to[bend left] (N0); \draw[->] (N8) -- (N3); \draw[->] (N4) -- (N2); \draw[->] (N3) to[bend left] (N1); \draw[->] (N3) to[bend right] (N0); \draw[->] (N2) -- (N1); \draw[->] (N1) -- (N0); \end{tikzpicture} \caption{The binary exponent nim, below $10000$, with {\color{blue} $P$-states} and {\color{red} $N$-states}.} \label{fig:BinaryExponentNim} \end{figure} % Later, we will observe that this game is universal, in the following senses: % \begin{itemize} % \item This game is the terminal object of the category of games. % % $\Gs$. % \item This is the universal \dq{recursively defined data} of games % \item Every state of every game is canonically \dq{equivalent} to the unique state (i.e., natural number) of this game. % \end{itemize} % \begin{example}[Boring examples] % \end{example} \begin{example}[\dq{Effeuiller la marguerite}]\label{exmp:EffeuillerLaMarguerite} Let us consider another game whose underlying set is $\N$. This time, we define $n\rel m$ by \[n\rel m \iff n=m+1.\] In each phase, players have at most one option. % unless the games has already ended. Obviously, the outcome of a state $n$ of this boring game is determined only by the parity of $n$: a state $n$ is a $P$-state if and only if $n$ is even. We will write $\ElM$ for this game since this game is conventionally called \dq{effeuiller la marguerite.} Althogh this game $\ElM=(\N, -1)$ is practically quite boring, it is theoretically important\memo{Cref}. \end{example} We conclude this subsection by expressing Bouton's theorem in our formulation (\Cref{def:game}) as follows. % % We end this subsection by giving several famous examples of combinatorial games. % The nim-game can be formulated of the form of \Cref{def:game} as follows. \begin{example}[Nim]\label{exmp:nimAsGraph} % Let $\Nim{n}$ denote the nim game with $n$-heaps. In our formulation, the $n$-heap nim $\Nim{n}$ is $(\N^{n}, \rel)$, where $(a_1, \dots a_n)\rel (b_1, \dots b_n)$ is defined by \[ (a_1, \dots a_n)\rel (b_1, \dots b_n) \iff \text{there exists $1\leq i \leq n$ such that $a_i > b_i$ and for any $j \neq i$, $a_j = b_j$} % if and only if \] \end{example} \begin{theorem}[Bouton's theorem \cite{bouton1901nim}]\label{thm:Bouton} A state $(a_1,\dots , a_n)$ of the $n$-heap nim $\Nim{n}$ is $P$-state if and only if $a_1 \nsum \cdots \nsum a_n=0$. \end{theorem} % \begin{example}[Subtraction Game]\label{ExampleSubtractionGame} % \memo{Write!} % \end{example} % \begin{example}[Wythoff]\label{ExampleWythoff} % \memo{Write!} % \end{example} \subsection{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 of it. But how can we effectively calculate the outcome? (For example, how can we know that the outcome of a nim state $(a_1, \dots , a_n)$ is $P$ if and only if $a_1 \nsum \dots \nsum a_n =0$?) One promising strategy is to divide the difficulty into smaller parts! What we will do in this subsection is to decompose a game into smaller parts and synthesize the properties of smaller games: \begin{itemize} \item We want to know the outcome of a big game $\X$. \item We devide the game $\X$ into a \demph{Conway sum} (\Cref{def:ConwayAddition}) of smaller games $\X = \Y + \Z$. \item We calculate the \demph{Grundy numbers} (\Cref{def:GrundyNumber}) of the games $\Y,\Z$. \item We calculate the {Grundy numbers} of $\X$ from those of $\Y,\Z$ (\Cref{thm:GeneralizedBoutonTheoremNimSumRule}). \item We calculate the outcome of $\X$ from the Grundy number of $\X$ (\Cref{prop:GrundynumberIsMoreInformativeThanOutcome}). \end{itemize} All of the content in this subsection is well-known in combinatorial game theory. For more details, see standard textbooks including \cite{siegel2013combinatorial}. \invmemo{In the previous subsection, we have seen the nim-sum $\nsum$ provides a winning strategy of the nim game. But which part of the nim game rule made us to consider nim-sum? The answer is classically known in combinatorial game theory, as the generalized nim-sum rule for \demph{Conway addition} and \demph{Grundy number}. (See \cite{siegel2013combinatorial} for more detail.) \invmemo{Can't catch the meaning}} % Moreover, Grundy number is compatible with the \demph{addition of games}. First, we recall the notion of the \demph{Conway addition} of games, which is visualized in \Cref{fig:ConwayAddition}. \begin{definition}[Conway addition of games]\label{def:ConwayAddition} For two games $\X = (X,\rel_{\X}), \Y = (Y,\rel_{\Y})$, their \demph{Conway sum} (or just sum) $\X + \Y$ is the game $(X\times Y, \rel_{\X + \Y})$, where $(x,y) \rel_{\X + \Y} (x',y')$ if and only if $(x \rel_{\X} x' \land y=y')$ or $(x=x' \land y \rel_{\Y}y')$. \end{definition} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick] % ===== Macro: slanted grid (cols x rows), with unique name prefix ===== % Args: #1=cols (nonnegative integer), #2=rows (nonnegative integer), % #3=x-shift, #4=y-shift, #5=name prefix (letters only) \newcommand{\slantedgrid}[5]{% \def\dx{0.8} % step in x for X-direction \def\dy{-0.8} % step in y for X-direction \def\ex{-0.8} % step in x for Y-direction \def\ey{-0.8} % step in y for Y-direction % nodes \foreach \i in {0,...,#1}{% \foreach \j in {0,...,#2}{% \coordinate (#5-\i-\j) at (#3+\i*\dx+\j*\ex, #4+\i*\dy+\j*\ey); \node[circle, fill=black, inner sep=2pt] at (#5-\i-\j) {}; }% }% % right-down arrows (only if cols>=1) \ifnum#1>0 \pgfmathtruncatemacro{\imax}{#1-1}% \foreach \i in {0,...,\imax}{% \foreach \j in {0,...,#2}{% \draw[->] (#5-\i-\j) -- (#5-\the\numexpr\i+1\relax-\j); }% }% \fi % left-down arrows (only if rows>=1) \ifnum#2>0 \pgfmathtruncatemacro{\jmax}{#2-1}% \foreach \i in {0,...,#1}{% \foreach \j in {0,...,\jmax}{% \draw[->] (#5-\i-\j) -- (#5-\i-\the\numexpr\j+1\relax); }% }% \fi } % ===== Left: 3×1 as a 2×0 slanted grid ===== \slantedgrid{3}{0}{-8}{0}{X} \node at (-7,-4) {$\X$}; % Tensor symbol \node at (-4.3,-1) {$+$}; % ===== Middle: 1×4 as a 0×3 slanted grid ===== \slantedgrid{0}{4}{0}{0.5}{Y} \node at (-1.5,-4) {$\Y$}; % Equality sign \node at (2.3,-1) {$=$}; % ===== Right: 3×4 as a 2×3 slanted grid (shifted right to avoid overlap) ===== \slantedgrid{3}{4}{7}{2}{Z} \node at (6.5,-4) {$\X + \Y$}; \end{tikzpicture} \caption{An example of Conway addition.} \label{fig:ConwayAddition} \end{figure} \begin{remark}[Terminology and notation] It is conventionally called sum and denoted by $\X + \Y$, while some readers might think \dq{product} is a better name. Actually, there is a decent reason related to the surreal number (\cite{conway2000numbers}).\memo{check} The corresponding monoidal structure in graph theory is called the box product (see, for example, \cite{kapulkin2024closed}). \end{remark} % \memo{This is called \dq{box product} in graph theory. % \cite{kapulkin2023closed}} % \memo{write diagrams} A typical usage of the Conway addition is to decompose a complicated game into smaller games. Examples include the following decomposition of nim. \begin{example}[Decomposition of Nim]\label{exmp:DecompositionOfNim} The $n$-heaps nim $\Nim{n}$ is the sum of $n$-copies of ($1$-heap) nim games.\[\Nim{n} = \Nim{1} + \dots + \Nim{1}\] \end{example} We want to utilize the Conway addition $+$ to calculate the outcome of a state $(x,y)\in \X+ \Y$. However, even if you know the outcomes $\oc_\X(x)$ and $\oc_\Y(y)$, it is generally impossible to calculate the outcome $\oc_{\X+ \Y}(x,y)$. Thus we need to enrich the outcome into the Grundy number. As a preparation, we recall the notion of mex, which stands for \demph{m}inimum \demph{ex}cluded value. \begin{definition}[mex]\label{def:mex} For a finite set of natural numbers $S\subset \N$, its mex $\mex(S)\in \N$ is the minimum natural number that does not belong to the subset $S$. In other words, mex of $S$ is the minimum element of the complement of $S$: \[\mex(S) = \min S^{\mathrm{c}}.\] \end{definition} Notice that the complement $S^c$ is always non-empty since the set $S$ is assumed to be finite (cf. \Cref{rem:finiteOptions}). \begin{definition}[Grundy number]\label{def:GrundyNumber} For a game $\X = (X, \rel)$ and a state $x\in X$, its \demph{Grundy number} $\G_{\X}(x)$ is recursively defined by \begin{equation}\label{eq:GrundyNumber} \G_{\X}(x)\coloneqq \mex(\{\G_{\X}(x')\mid x \rel x'\}). \end{equation} % \[\] \end{definition} This recursive definition does work due to the two finiteness conditions in the definition of games (\Cref{def:game}). % \begin{figure}[ht] % \centering % \begin{tikzpicture}[>=Latex, thick] % % ===== Vertices ===== % \node[circle, fill=black, inner sep=3pt, label=above:{}] (A) at (0,0) {}; % \node[circle, fill=black, inner sep=3pt, label=above:{}] (B) at (2,0) {}; % \node[circle, fill=black, inner sep=3pt, label=above:{}] (C) at (4,0) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (D) at (0.5,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (E) at (2,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (F) at (3.5,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (G) at (1,-2.4) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (H) at (3,-2.4) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (T1) at (0.5,-3.6) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (T2) at (3.5,-3.6) {}; % % ===== Arrows ===== % \draw[->] (A) -- (D); % \draw[->] (A) -- (E); % \draw[->] (B) -- (E); % \draw[->] (B) -- (F); % \draw[->] (C) -- (F); % \draw[->] (D) -- (G); % \draw[->] (E) -- (G); % \draw[->] (E) -- (H); % \draw[->] (F) -- (H); % \draw[->] (G) -- (T1); % \draw[->] (G) -- (T2); % \draw[->] (H) -- (T2); % % ===== Curved extra arrow ===== % \draw[->] (A) to[bend right] (G); % \draw[->] (C) to[bend left] (T2); % \end{tikzpicture} % \begin{tikzpicture}[>=Latex, thick] % % ===== Vertices ===== % \node[circle, fill=black, inner sep=3pt, label=above:{}] (A) at (0,0) {}; % \node[circle, fill=black, inner sep=3pt, label=above:{}] (B) at (2,0) {}; % \node[circle, fill=black, inner sep=3pt, label=above:{}] (C) at (4,0) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (D) at (0.5,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (E) at (2,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{}] (F) at (3.5,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{1}] (G) at (1,-2.4) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{1}] (H) at (3,-2.4) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (T1) at (0.5,-3.6) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (T2) at (3.5,-3.6) {}; % % ===== Arrows ===== % \draw[->] (A) -- (D); % \draw[->] (A) -- (E); % \draw[->] (B) -- (E); % \draw[->] (B) -- (F); % \draw[->] (C) -- (F); % \draw[->] (D) -- (G); % \draw[->] (E) -- (G); % \draw[->] (E) -- (H); % \draw[->] (F) -- (H); % \draw[->] (G) -- (T1); % \draw[->] (G) -- (T2); % \draw[->] (H) -- (T2); % % ===== Curved extra arrow ===== % \draw[->] (A) to[bend right] (G); % \draw[->] (C) to[bend left] (T2); % \end{tikzpicture} % \begin{tikzpicture}[>=Latex, thick] % % ===== Vertices ===== % \node[circle, fill=black, inner sep=3pt, label=above:{}] (A) at (0,0) {}; % \node[circle, fill=black, inner sep=3pt, label=above:{}] (B) at (2,0) {}; % \node[circle, fill=black, inner sep=3pt, label=above:{}] (C) at (4,0) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (D) at (0.5,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (E) at (2,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (F) at (3.5,-1.2) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{1}] (G) at (1,-2.4) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{1}] (H) at (3,-2.4) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (T1) at (0.5,-3.6) {}; % \node[circle, fill=black, inner sep=3pt, label=below:{0}] (T2) at (3.5,-3.6) {}; % % ===== Arrows ===== % \draw[->] (A) -- (D); % \draw[->] (A) -- (E); % \draw[->] (B) -- (E); % \draw[->] (B) -- (F); % \draw[->] (C) -- (F); % \draw[->] (D) -- (G); % \draw[->] (E) -- (G); % \draw[->] (E) -- (H); % \draw[->] (F) -- (H); % \draw[->] (G) -- (T1); % \draw[->] (G) -- (T2); % \draw[->] (H) -- (T2); % % ===== Curved extra arrow ===== % \draw[->] (A) to[bend right] (G); % \draw[->] (C) to[bend left] (T2); % \end{tikzpicture} % \caption{Grundy number} % \label{fig:FiniteGame} % \end{figure} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick, scale=0.9] % Lighten only the arrows; keep text color as-is (black) \tikzset{edge/.style={->, draw=black!35}} % ===== Macro: one panel of the same DAG with stagewise Grundy labels ===== % Usage: \grundypanel{}{}{} % Stage 1: label terminals only (g=0) % Stage 2: + Level 1 (g=1) % Stage 3: + Level 2 & Level 3 (X: 0,2,0; W: 1,1,2) % Stage 4: + Level 4 (V: 0,3) % Stage 5: same labels as Stage 4 (final state), included to show a 5-step pipeline \newcommand{\grundypanel}[4]{% \begin{scope}[xshift=#1cm, yshift=#2cm] \def\stage{#3}% % --- Nodes (same geometry as before) --- % Bottom (terminals) — filled black if computed at this stage, else light \node[circle, inner sep=3pt, fill={\ifnum\stage>0 black\else black!20\fi}, label=left:{\ifnum\stage>0 $0$\fi}] (#4Z1) at (-2,-7.2) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>0 black\else black!20\fi}, label=left:{\ifnum\stage>0 $0$\fi}] (#4Z2) at ( 0,-7.2) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>0 black\else black!20\fi}, label=left:{\ifnum\stage>0 $0$\fi}] (#4Z3) at ( 2,-7.2) {}; % Level 1 — black if stage>1 \node[circle, inner sep=3pt, fill={\ifnum\stage>1 black\else black!20\fi}, label=left:{\ifnum\stage>1 $1$\fi}] (#4Y1) at (-2,-5.8) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>1 black\else black!20\fi}, label=left:{\ifnum\stage>1 $1$\fi}] (#4Y2) at ( 0,-5.8) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>1 black\else black!20\fi}, label=left:{\ifnum\stage>1 $1$\fi}] (#4Y3) at ( 2,-5.8) {}; % Level 2 — black if stage>2 \node[circle, inner sep=3pt, fill={\ifnum\stage>2 black\else black!20\fi}, label=left:{\ifnum\stage>2 $0$\fi}] (#4X1) at (-2,-4.4) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>2 black\else black!20\fi}, label=left:{\ifnum\stage>2 $2$\fi}] (#4X2) at ( 0,-4.4) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>2 black\else black!20\fi}, label=left:{\ifnum\stage>2 $0$\fi}] (#4X3) at ( 2,-4.4) {}; % Level 3 — W1 and W3 appear at stage>3; W2 appears already at stage>2 with g=1 \node[circle, inner sep=3pt, fill={\ifnum\stage>3 black\else black!20\fi}, label=left:{\ifnum\stage>3 $1$\fi}] (#4W1) at (-2,-3.0) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>2 black\else black!20\fi}, label=left:{\ifnum\stage>2 $2$\fi}] (#4W3) at ( 0,-3.0) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>3 black\else black!20\fi}, label=right:{\ifnum\stage>3 $1$\fi}] (#4W2) at ( 2,-3.0) {}; % Level 4 (tops) — black if stage>4 \node[circle, inner sep=3pt, fill={\ifnum\stage>4 black\else black!20\fi}, label=left:{\ifnum\stage>4 $0$\fi}] (#4V1) at (-1,-1.6) {}; \node[circle, inner sep=3pt, fill={\ifnum\stage>4 black\else black!20\fi}, label=left:{\ifnum\stage>4 $3$\fi}] (#4V2) at ( 1,-1.6) {}; % --- Edges (same for all stages), drawn in light gray --- % Level 1 -> terminals \draw[edge, {\ifnum\stage>1 black\else black!20\fi}] (#4Y1) -- (#4Z1); \draw[edge, {\ifnum\stage>1 black\else black!20\fi}] (#4Y2) -- (#4Z2); \draw[edge, {\ifnum\stage>1 black\else black!20\fi}] (#4Y2) -- (#4Z3); \draw[edge, {\ifnum\stage>1 black\else black!20\fi}] (#4Y3) -- (#4Z3); % Level 2 -> Level 1 / terminals \draw[edge, {\ifnum\stage>2 black\else black!20\fi}] (#4X1) -- (#4Y1); \draw[edge, {\ifnum\stage>2 black\else black!20\fi}] (#4X1) -- (#4Y2); \draw[edge, {\ifnum\stage>2 black\else black!20\fi}] (#4X2) -- (#4Y2); \draw[edge, {\ifnum\stage>2 black\else black!20\fi}] (#4X2) -- (#4Z1); \draw[edge, {\ifnum\stage>2 black\else black!20\fi}] (#4X3) -- (#4Y3); % Level 3 -> Level 2 / Level 1 / terminals \draw[edge, {\ifnum\stage>3 black\else black!20\fi}] (#4W1) -- (#4X1); \draw[edge, {\ifnum\stage>3 black\else black!20\fi}] (#4W1) -- (#4X2); \draw[edge, {\ifnum\stage>3 black\else black!20\fi}] (#4W2) -- (#4X2); \draw[edge, {\ifnum\stage>3 black\else black!20\fi}] (#4W2) -- (#4X3); \draw[edge, {\ifnum\stage>2 black\else black!20\fi}] (#4W3) -- (#4Y1); \draw[edge, {\ifnum\stage>2 black\else black!20\fi}] (#4W3) -- (#4Z3); % Level 4 -> Level 3 / Level 2 \draw[edge, {\ifnum\stage>4 black\else black!20\fi}] (#4V1) -- (#4W1); \draw[edge, {\ifnum\stage>4 black\else black!20\fi}] (#4V1) -- (#4W2); \draw[edge, {\ifnum\stage>4 black\else black!20\fi}] (#4V1) -- (#4W3); \draw[edge, {\ifnum\stage>4 black\else black!20\fi}] (#4V2) -- (#4W2); \draw[edge, {\ifnum\stage>4 black\else black!20\fi}] (#4V2) -- (#4X2); \draw[edge, {\ifnum\stage>4 black\else black!20\fi}] (#4V2) -- (#4X3); % Stage label \node at (0,-8.6) {\small Step~#3}; \end{scope}% } % ===== Five panels left-to-right ===== \grundypanel{0.0}{0.0}{1}{A} \grundypanel{6.0}{0.0}{2}{B} \grundypanel{12.0}{0.0}{3}{C} \grundypanel{0.0}{-9.0}{4}{D} \grundypanel{6.0}{-9.0}{5}{E} \begin{scope}[xshift=12cm, yshift=-9cm] \node[circle, inner sep=3pt, fill=blue] (GZ1) at (-2,-7.2) {}; \node[circle, inner sep=3pt, fill=blue] (GZ2) at ( 0,-7.2) {}; \node[circle, inner sep=3pt, fill=blue] (GZ3) at ( 2,-7.2) {}; % Level 1 — black if stage>1 \node[circle, inner sep=3pt, fill=red] (GY1) at (-2,-5.8) {}; \node[circle, inner sep=3pt, fill=red] (GY2) at ( 0,-5.8) {}; \node[circle, inner sep=3pt, fill=red] (GY3) at ( 2,-5.8) {}; % Level 2 — black if stage>2 \node[circle, inner sep=3pt, fill=blue] (GX1) at (-2,-4.4) {}; \node[circle, inner sep=3pt, fill=red] (GX2) at ( 0,-4.4) {}; \node[circle, inner sep=3pt, fill=blue] (GX3) at ( 2,-4.4) {}; % Level 3 — W1 and W3 appear at stage>3; W2 appears already at stage>2 with g=1 \node[circle, inner sep=3pt, fill=red] (GW1) at (-2,-3.0) {}; \node[circle, inner sep=3pt, fill=red] (GW3) at ( 0,-3.0) {}; \node[circle, inner sep=3pt, fill=red] (GW2) at ( 2,-3.0) {}; % Level 4 (tops) — black if stage>4 \node[circle, inner sep=3pt, fill=blue] (GV1) at (-1,-1.6) {}; \node[circle, inner sep=3pt, fill=red] (GV2) at ( 1,-1.6) {}; % --- Edges (same for all stages), drawn in light gray --- % Level 1 -> terminals \draw[edge, black] (GY1) -- (GZ1); \draw[edge, black] (GY2) -- (GZ2); \draw[edge, black] (GY2) -- (GZ3); \draw[edge, black] (GY3) -- (GZ3); % Level 2 -> Level 1 / terminals \draw[edge, black] (GX1) -- (GY1); \draw[edge, black] (GX1) -- (GY2); \draw[edge, black] (GX2) -- (GY2); \draw[edge, black] (GX2) -- (GZ1); \draw[edge, black] (GX3) -- (GY3); % Level 3 -> Level 2 / Level 1 / terminals \draw[edge, black] (GW1) -- (GX1); \draw[edge, black] (GW1) -- (GX2); \draw[edge, black] (GW2) -- (GX2); \draw[edge, black] (GW2) -- (GX3); \draw[edge, black] (GW3) -- (GY1); \draw[edge, black] (GW3) -- (GZ3); % Level 4 -> Level 3 / Level 2 \draw[edge, black] (GV1) -- (GW1); \draw[edge, black] (GV1) -- (GW2); \draw[edge, black] (GV1) -- (GW3); \draw[edge, black] (GV2) -- (GW2); \draw[edge, black] (GV2) -- (GX2); \draw[edge, black] (GV2) -- (GX3); % Stage label \node at (0,-8.6) {{\color{blue} $P$-states} and {\color{red} $N$-states}}; \end{scope}% \end{tikzpicture} \caption{Recursive calculation of \demph{Grundy numbers} from bottom to top, and the outcome} \label{fig:RecursioveCalculationOfGrundyNumber} \end{figure} The importance of Grundy number is due to the following proposition. \begin{proposition}[the Grundy number is more informative than the outcome]\label{prop:GrundynumberIsMoreInformativeThanOutcome} % The P-player (Previous player) wins the game $\X$ with the initial state $x\in X$ if and only if $\G_{\X}(x) = 0$. For any game $\X=(X, {\rel})$ and any state $x\in X$, its outcome is $P$ if and only if its Grundy number $\G_{\X}(x)$ is $0$: \[ \oc_{\X}(x)=P \iff \G_{\X}(x)=0. \] \end{proposition} \begin{proof} One can easily prove this by induction, although we will see more conceptual proof later. See comments just after \Cref{prop:AlgebraHomPreservesGameValue}. % \memo{add bib} \end{proof} The reason why we enrich the ouctome to Grundy number is that the Grundy number is compatible with the Conway adiition (\Cref{thm:GeneralizedBoutonTheoremNimSumRule})! % There is a well-known way to calculate the Grundy number of a state of a sum game: nim-sum. Let us recall nim-sum again (\Cref{def:NimSum}). \begin{definition}[Nim-sum]\label{def:NimSum2} \demph{Nim-sum} is the abelian group structure on $\N$, induced by the bijection $\N \to \bigoplus_{k=0}^{\infty} \Z/2\Z$ given by the binary expansion . In other words, nim-sum is the digit-wise exclusive disjunction (xor) of the binary expansion. \end{definition} For example, $7\nsum 5 = (111)_{2} \nsum (101)_{2} = (010)_{2} = 2$. The following famous proposition is not due to me. For a proof, see \memo{add bib} \begin{theorem}[Nim-sum rule= generalized Bouton's theorem \memo{citation}]\label{thm:GeneralizedBoutonTheoremNimSumRule} For any pair of games $\X = (X,\rel_{\X}), \Y = (Y,\rel_{\Y})$ and any pair of states $x\in X, y\in Y$, the Grundy number of $(x,y)$ is given by the nim-sum as follows: \[\G_{\X+\Y}(x,y)= \G_{\X}(x)\nsum\G_{\Y}(y).\] \end{theorem} \memo{Cite} Combining \Cref{prop:GrundynumberIsMoreInformativeThanOutcome} and \Cref{thm:GeneralizedBoutonTheoremNimSumRule}, we can calculate $P$-states of a Conway sum and thus its winning strategy. In fact, for a given game $\X$ that can be decomposed into a Conway sum of two games $\X = \Y + \Z$, we have \[ x=(y,z) \text{ is a $P$-state} {\iff} \G_{\Y+\Z}(y,z)=0 \iff \G_{\Y}(y) \nsum \G_{\Z}(z)=0. \] \begin{example}[Analysis of nim]\label{exmp:AnalysisOfNim} The classical bouton theorem (\Cref{thm:Bouton}) is the typical example of the above observation. In fact, the $n$-heap nim $\Nim{n}$ is the Conway sum of $n$-copies of the $1$-heap nim $\Nim{1}$ (\Cref{exmp:DecompositionOfNim}). So in order to win $\Nim{n}$, it suffices to know $\G_{\Nim{1}}\colon \N \to \N$. By the easy induction, we can prove that $\G_{\Nim{1}}= \id_{\N}$, and thus we obtain \[ \G_{\Nim{n}}(a_1, \dots , a_n)= \G_{\Nim{1}}(a_1) \nsum \dots \nsum \G_{\Nim{1}}(a_n) = a_1 \nsum \dots \nsum a_n. \] Therefore, \Cref{prop:GrundynumberIsMoreInformativeThanOutcome} implies that a state $(a_1, \dots, a_n)$ is a $P$-state if and only if $a_1 \nsum \dots \nsum a_n=0$, which is exctly what the Bouton theorem states (\Cref{thm:Bouton}). % For example, we can deduce a winning strategy of $n$-heap nim $\Nim{n}$, which is a sum of $n$-copy of $\Nim{1}$. % \memo{Write} \end{example} \section{Games as recursive coalgebras}\label{sec:GamesAsRecursiveCoalgebras} In this section, we will reinterpret the content in \Cref{sec:GamesasGraphs} in terms of recursive coalgebras. Here are the spoiler: \begin{table}[ht] \centering \begin{tabular}{|l|l|} \hline \textbf{Abstract Coalgebra Theory} & \textbf{Game Theoretic Notions} \\ \hline Coalgebra & (Finite-branching) graphs \\ \hline Algebra & A system of game values \\ \hline Coalgebra-algebra morphisms & Recursive calculation of game value \\ \hline Recursive coalgebras & Games \\ \hline \end{tabular} \caption{Comparison between Abstract Coalgebra Theory and Game Theoretic Notions} \label{tab:coalgebra_game_theory_comparison} \end{table}\memo{revise this table} \subsection{A key observation, before delving into the theory} Before explaining the categorical abstract nonsense in \Cref{ssec:PreliminariesOnCoalgebraicMethod}, let us observe one phenomenon motivating the latter contents. % so that the reader will not be bored in the next category-theoretic subsection. While this subsection does not include any theorems, this is one of the core part of this paper, in the sense that this observation is the starting point of this project.\memo{This observation is independently found by \cite{bavsic2024categories}, though they do not use coalgebra theory} Our original motivation is to understand the nim-sum (\Cref{def:NimSum2}), and the reason why the nim-sum works is the Nim-sum rule (\Cref{thm:GeneralizedBoutonTheoremNimSumRule}) regarding the Grundy number (\Cref{def:GrundyNumber}). In the definition of Grundy number (\Cref{def:GrundyNumber}), we used a particular type of recursion \[\G_{\X}(x)=\mex(\{\G_{\X}(x')\mid x \rel x'\})\] (\Cref{eq:GrundyNumber}), which we we will reinterpret in categorical terms later \memo{Cref}. Let $\Pf(X)$ denote the set of all finite subset of a given set $X$ (\Cref{not:FinitePowersetFunctorPfin}). Then, the mex function is a function from $\Pf(\N)$ to $\N$: \[\mex \colon \Pf(\N) \to \N.\] Similarly, we can rewrite games as a function between $\Pf(X)$ and $X$, but in the opposite direction! For any directed graph $(X, {\rel}\subset X\times X)$, the corresponding \demph{neiborhood function} $\str\colon X \to \Pow(X)$ is defined by \begin{equation}\label{eq:TheCorrespondence} \str(x)= \{x'\in X\mid x\rel x'\}. \end{equation} If a graph $\X=(X, {\rel})$ satisfies the finite option condition in \Cref{def:game}, in particular if $\X$ is a game, the codomain $\Pow(X)$ can be reduced to $\Pf(X)$ and we obtain the function \[ \str\colon X \to \Pf(X). \] Thus, we can rephrase the definition of Grundy number (\Cref{def:GrundyNumber} and \Cref{eq:GrundyNumber}) as the unique function $\G_{\X}\colon X \to \N$ that makes the following \dq{twisted} diagram \begin{equation}\label{eq:GrundyNumberDiagram} \begin{tikzcd}[column sep = 50pt, row sep= 30pt] \Pf(X)\ar[r,"\Pf(\G_{\X})"]&\Pf(\N)\ar[d,"\mex"']\\ X\ar[u,"\str"]\ar[r,"\G_{\X}"]&\N \end{tikzcd} \end{equation} commutative, where $\Pf(\G_{\X})$ denotes the direct image function. The \dq{finite time} condition ensures the unique existence of such a function $\G_{\X}\colon X \to A$. The recursive computation of Grundy numbers, as in \Cref{fig:RecursioveCalculationOfGrundyNumber}, is carried out by tracing the game \demph{backwards}. The somewhat unusual kind of \dq{twisted} commutativity in \Cref{eq:GrundyNumberDiagram} corresponds to this recursive computation that goes against the flow of the game! Such \dq{twisted recursive computations} have a long history in category theory (or categorical computer science) under the name of \demph{recursive coalgebras} (or hylomorphisms), which we will recall in the next subsection. \subsection{Preliminaries on coalgebras and recursive coalgebras}\label{ssec:PreliminariesOnCoalgebraicMethod} This subsection aims to recall the basic notions in coalgebra theory, in particular, the definition and properties of recursive coalgebras. For general theory and examples of coalgebras, see \cite{jacobs2017introduction}. For recursive coalgebras, see the book \cite{taylor1999practical}, papers including \cite{adamek2020well}, or papers cited therein. % It might be easier for some readers—especially those already familiar with coalgebra theory—if we separate our game-theoretic examples from the general theory of coalgebras. However, we believe that beginners would find it more motivating if the concrete examples are presented alongside the general theory. So, in this subsection, we’ll present our particular examples each time we introduce an abstract definition. 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. \subsubsection{Algebras and coalgebras of an endofunctor}\label{ssec:AlgebrasAndCoalgebrasOfEndofunctor} The definition of coalgebras (and algebras) of an endofunctor is surprisingly simple: % \subsection{Coalgebras of an endofuntors} \begin{definition}[Coalgebras and algebras]\label{DefinitionCoalgebra} For an endofunctor $T\colon \C \to \C$ on a category $\C$, a \demph{$T$-coalgebra} $\X$ is a pair $\X=(X, \str)$ of an object $X \in \ob(\C)$ and a morphism $\str \colon X \to TX$. Dually, a \demph{$T$-algebra} $\A$ is a pair $\A=(A, \alpha)$ of an object $A \in \ob(\C)$ and a morphism $\alpha \colon TA \to A$. \end{definition} \begin{definition}[Coalgebra homomorphism and algebra homomorphism] \label{DefinitionCoalgebraMorphism} For an endofunctor $T\colon \C \to \C$ on a category $\C$, a homomorphism of $T$-coalgebras from $(X, \str)$ to $(X',\str')$ is a morphism $f\colon X \to X'$ in $\C$ such that the diagram % \[ % \begin{tikzcd} % X\ar[r,"f"]\ar[d,"\str"]&X'\ar[d,"\str'"]\\ % TX\ar[r,"Tf"]&TX' % \end{tikzcd} % \] \[ \begin{tikzcd} TX\ar[r,"Tf"]&TX'\\ X\ar[r,"f"]\ar[u,"\str"]&X'.\ar[u,"\str'"] \end{tikzcd} \] commutes. Homomorohisms between $T$-algebras $(A, \alpha), (A', \alpha')$ are defined in the dual way \[ \begin{tikzcd} TA\ar[r,"Tf"]\ar[d,"\alpha"]&TA'\ar[d,"\alpha'"]\\ A\ar[r,"f"]&A'. \end{tikzcd} \] \end{definition} \begin{notation}\label{not:AlgCoalgCategortOfCoAlgebras} For an endofunctor $T\colon \C \to \C$ on a category $\C$, the category of $T$-coalgebras and $T$-coalgebra homomorphisms is denoted by $\Coalg{T}$. The category of $T$-algebras and $T$-algebra homomorphisms is denoted by $\Alg{T}$. \end{notation} \subsubsection{Coalgebra-algebra morphisms and Recursive coalgebras}\label{ssec:RecursiveCoalgebras} We will recall the notion of recursive coalgebra, due to \cite{osius1974categorical} and \cite{taylor1999practical}. \begin{definition} For an endofunctor $T\colon \C \to \C$ on a category $\C$, a \demph{coalgebra-algebra morphism} from a $T$-coalgebra $\X=(X, \str)$ to a $T$-algebra $\A=(A,\alpha)$ is a morphism $f\colon X\to A$ in the category $\C$ such that the diagram \[ \begin{tikzcd} TX\ar[r,"Tf"]&TA\ar[d,"\alpha"']\\ X\ar[u,"\str"]\ar[r,"f"]&A \end{tikzcd} \] commutes. \end{definition} \begin{definition}[Recursive coalgebra]\label{def:recursiveCoalgebras}\memo{cite} A $T$-coalgebra $\X=(X,\str)$ is said to be \demph{recursive} if, for any $T$-alegebra $\A=(A,\alpha)$, there exists a unique coalgebra-algebra morphism from $\X$ to $\A$. The full subcategory of $\Coalg{T}$ that consists of all recursive coalgebras is denoted by $\RecCoalg{T}$. For a recursive coalgebra $\X=(X, \theta)$ and a $T$-algebra $\A=(A, \alpha)$, the unique coalgebra-algebra morphism $X\to A$ is called the \demph{hylomorphism} and denoted by $\hylo_{\A, \X}\colon X \to A$. \end{definition} Let us emphasize the following stability of hylomorphisms by compositions, which is theoretically almost trivial, but it provides a seemingly non-trivial consequences\memo{cite}. \begin{lemma}[Stability of hylomorphisms by composition]\label{lem:StabilityOfHylomorphisms} Let $T$ Let $T\colon \C \to \C$ be an endofunctor on a category $\C$, $\X=(X, \str)$ be a recursive $T$-coalgebra, $\A=(A, \alpha)$ be a $T$-algebra, and $\hylo_{\A,\X}\colon X \to A$ be the hylomorphism between them. % Then, the following properties hold. \begin{itemize} \item For any recurisive $T$-coalgebra $\X'=(X',\str')$ and any $T$-coalgebra homomorphism $f\colon \X'\to \X$, the hylomorphism $\hylo_{\A,\X'}\colon X' \to A$ is given by $\hylo_{\A,\X'} = \hylo_{\A, \X}\circ f$. \[ \begin{tikzcd}[row sep=5pt] X'\ar[rr, "\hylo_{\A,\X'}"]\ar[rd, "f"']&&A\\ &X\ar[ru, "\hylo_{\A,\X}"']& \end{tikzcd} \] \item For any $T$-algebra $\A'=(A',\alpha')$ and any $T$-algebra homomorphism $g\colon \A\to \A'$, the hylomorphism $\hylo_{\A',\X}\colon X \to A'$ is given by $\hylo_{\A',\X} = g \circ \hylo_{\A, \X}$. \[ \begin{tikzcd}[row sep=5pt] X\ar[rr, "\hylo_{\A',\X}"]\ar[rd, "\hylo_{\A,\X}"']&&A'\\ &A\ar[ru, "g"']& \end{tikzcd} \] \end{itemize} \end{lemma} \begin{proof} The commutative diagmram \[ \begin{tikzcd}[column sep=30pt] TX'\ar[r, "Tf"]&TX\ar[r, "T(\hylo_{\A,\X})"]&TA\ar[r, "Tg"]\ar[d, "\alpha"]&TA'\ar[d, "\alpha'"]\\ X'\ar[r, "f"]\ar[u, "\str'"]&X\ar[u, "\str"]\ar[r, "\hylo_{\A,\X}"]&A\ar[r, "g"]&A' \end{tikzcd} \] complete the proof. \end{proof} \invmemo{ \begin{remark}[In which category is a coalgebra-algebra morphism actually a morphism?] It is just a profunctor. We can consider its collage/cograph. The above proposition is just a general phenomenon for profunctor. \end{remark} } \begin{proposition}[{\cite[][Lemma 2.2]{lambek1968fixpoint}\cite[][Proposition 2]{capretta2006recursive}}]\label{prop:TerminalRecursiveCoalgebraIsInitialAlgebra} For an endofunctor $T\colon \C \to \C$ on a category $\C$, if a $T$-algebra $\A=(A,\alpha)$ is the initial $T$-algebra, then \begin{itemize} \item the structure map $\alpha \colon TA \to A$ is an isomorphism, and \item the coalgebra $(A, \alpha^{-1}\colon A \to TA)$ is the terminal recursive coalgebra. \end{itemize} \end{proposition} \begin{proof} The first assertion is known as Lambek's lemma. The second assertion immediately follows from the related definitions. \end{proof} \invmemo{The inverse direction is \cite[][Proposition 7]{capretta2006recursive}} \begin{remark}[Relationship with well-founded coalgebras] \cite{taylor1999practical} For now, see \href{https://ncatlab.org/nlab/show/recursion+scheme}{[recursion scheme]} in nLab. For the relationship with well-founded coalgebra, see the recent study \cite{adamek2020well} by Adamek, Milius, and Moss. \end{remark} \subsection{Games as recursive coalgebras} % So far, we have recalled the general theory of recursive coalgebra. In the rest of \Cref{sec:GamesAsRecursiveCoalgebras}, we will specialize the general theory of recursive coalgebra (\Cref{ssec:PreliminariesOnCoalgebraicMethod}) to the case where the endofunctor $T\colon \C \to \C$ is the % we will consider in the present paper is the \demph{finite powerset functor} (\Cref{not:FinitePowersetFunctorPfin}). \begin{notation}[finite powerset functor]\label{not:FinitePowersetFunctorPfin}In this paper, \begin{itemize} \item $\Pow\colon \Set \to \Set$ denotes the covariant \demph{powerset functor} that sends a set to its powerset and a function to its direct image function, and \item $\Pf:\Set \to \Set$ denotes \demph{the finite powerset functor}, which is the subfunctor of $\Pow:\Set \to \Set$ such that $\Pf(X) = \{S \subset X\mid \# S < \infty\}$. \end{itemize} % The finite powerset functor $\Pf:\Set \to \Set$ is the subfunctor of the covariant powerset functor $\Pow:\Set \to \Set$ such that % $\Pf(X) = \{S \subset X\mid \# S < \infty\}$. \end{notation} % \[ % \Pf\colon \Set \to \Set, % \] % that sends a (possibly infinite) set % For any directed graph $(X, {\rel}\subset X\times X)$, the corresponding function $\str\colon X \to \Pow(X)$ defined by % \begin{equation}\label{eq:TheCorrespondence} % \str(x)= \{x'\in X\mid x\rel x'\} % \end{equation} In terms of coalgebras, any graph $\X=(X, {\rel})$ is associated with the corresponding $\Pow$-coalgebra \[\str\colon X \to \Pow(X)\] by \Cref{eq:TheCorrespondence}. The finite option condition in \Cref{def:game} is precisely saying that the codomain $\Pow(X)$ can be reduced to $\Pf(X)$. The next proposition states that the finite time condition is precicely the recursiveness (\Cref{def:recursiveCoalgebras}) and characterize games as the graphs that admits the \dq{twisted recursion} (\Cref{eq:GrundyNumberDiagram}). \begin{proposition}[Games as recursive coalgebras]\label{prop:GamesFiniteTimeIsRecursivenessAndGamesAsRecursiveCoalgebras} For any graph $\X=(X, {\rel})$ with the finite option condition (\Cref{def:game}), the corresponding $\Pf$-coalgebra \[ \str\colon X \to \Pf(X) \] is recursive coalgebra if and only if $\X$ is a game. In particular, for any set $X$, \Cref{eq:TheCorrespondence} provides a one-to-one correspondence between the game structures on $X$ and the recursive $\Pf$-coalgebra structures on $X$. \end{proposition} \begin{proof} Let $\X=(X, {\rel})$ 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, and hence we can prove that it is a recursive coalgebra. Conversely, take an arbitrary recursive coalgebra $\X= (X,\str)$. % Assuming that the corresponding graph $(X, \rel)$ does not satisfy the finite option condition, we deduce a contradiction. We prove that the corresponding graph $(X, \rel)$ satisfies the finite time condition. Consider a $\Pf$-algebra $\A=(\{\top, \bot\},\alpha)$ defined by % \[ % \alpha(S) = \top \iff S \subset \{\top\} % \] \[ \alpha(S) \coloneqq \begin{cases} % \top &( S \subset \{\top\})\\ \top &( \bot \notin S)\\ % \bot &( S \not\subset \{\top\}). \bot &( \bot \in S). \end{cases} \] On the one hand, the function $\FinTime_{\X}\colon X \to \{\top, \bot\}$ defined by \[ \FinTime_{\X}(x) \coloneqq \begin{cases} \top &(\text{any path starting from $x$ terminates in finite steps})\\ \bot & (\text{otherwise}) \end{cases} \] is an coalgebra-algebra morphism from $\X$ to $\A$. On the other hand, the constant function to $\top$, which is denoted by $\True_{\X}\colon X \to \{\top, \bot\}$, is also a coalgebra-algebra morphism from $\X$ to $\A$. Therefore, the assumption that $\X$ is recursive implies that $\FinTime_{\X}= \True_{\X}$, i.e., $\X$ satisfies the finite time condition. % Two functions $f,g\colon X\to \{\top, \bot\}$ % and consider the hylomorphism $\hylo_{\A,\X}\colon X \to N$. If $x\rel x'$, then we can prove that $\hylo_{\A,\X}(x)>\hylo_{\A,\X}(x')$. By the well-foundedness of the poset $(\N,<)$, this proves that the corresponding graph of the coalgebra $\X=(X, \str)$ satisfies the finite time condition, thus is a game. \memo{cite, general recursion schema?} \end{proof} \begin{example}[Nim is von Neumann's natural numbers!]\label{exmp:NimCoalgebra} Let $(\N, \nu:\N \to \Pf(\N))$ denote the $\Pf$-coalgebra corresponding to the ($1$-heap) nim game $\Nim{1}$ (\Cref{exmp:nimAsGraph}). This function $\nu$ is given by \[\nu:\N \to \Pf(\N): n \mapsto \{0,1, \dots, n-1\}.\] In other words, this is von Neumann's set-theoretic definition of natural numbers (cf. \memo{cite}). % \memo{ % } \end{example} \subsection{Game morphisms} As games are recursive coalgebras, it is reasonable to define \demph{game homomorphisms} as coalgebra homomorphisms. Notice that being a coalgebra homomorphism is much stronger than just being a graph morphism! For games $\X=(X, {\rel_\X})$ and $\Y=(Y, {\rel_\Y})$ and a function $f\colon X \to Y$, being a graph morphism $x_0\rel x_1 \implies f(x_0) \rel f(x_1)$ is equivalent to saying that $f(\str_{\X}(x))\subset \str_{\Y}(f(x))$, which is strictly weaker than being a coalgebra homomorphism $f(\str_{\X}(x))= \str_{\Y}(f(x))$. In order to ensure the opposite inclusion $f(\str_{\X}(x))\supset \str_{\Y}(f(x))$, we need to assume a kind of \dq{path-lifting property} as follows. \[\text{Being a game homomorphism }\iff \begin{tikzcd}[row sep = 20pt, column sep=40pt] \Pf(X)\ar[r,"\Pf(f)"]&\Pf(Y)\\ &\\ X\ar[uu, "\str_{\X}"]\ar[r,"f"]\ar[ruu, phantom, "\rotatebox{-45}{$\subset$}"]&Y\ar[uu, "\str_{\Y}"]\\ {}\ar[r,"\text{(1) Graph morph.}", phantom ]&{} \end{tikzcd} \text{ and } \begin{tikzcd}[row sep = 20pt, column sep=40pt] \Pf(X)\ar[r,"\Pf(f)"]&\Pf(Y)\\ &\\ X\ar[uu, "\str_{\X}"]\ar[r,"f"]\ar[ruu, phantom, "\rotatebox{-45}{$\supset$}"]&Y\ar[uu, "\str_{\Y}"]\\ {}\ar[r,"\text{(2) Path-lift.}", phantom ]&{} \end{tikzcd} \] \begin{definition}[Game morphism]\label{def:GameMorphism} A \demph{game morphism} from a game $\X = (X, \rel_{\X})$ to another game $\Y = (Y, \rel_{\Y})$ is % a $\Pf$-coalgebra homomorphism between them, i.e., a function $f\colon X \to Y$ satsifying the following two conditions: \begin{description} \item[(1) Graph morphism] For any $x,x'\in X$, $x\rel_{\X} x'$ implies $f(x) \rel_{\Y} f(x')$. \label{ConditionGraphpreserving} \item[(2) Path-lifting] For any $x\in X$ and $y\in Y$, if $f(x) \rel_{\Y} y$, then there exists $x' \in \X$ such that $x\rel_{\X}x'$ and $f(x')= y$. (see \Cref{fig:PathLiftingProperty})\label{conditionLocallySurjective} \end{description} % We write $\Gs$ for the category of games and game homomorphisms. \end{definition} \begin{notation}\label{not:CategoryOfGames} The category of games and game morphisms is denoted by $\Gs$, and the canonical forgetful functor $\X=(X, {\rel}) \mapsto X$ is denoted by $U \colon \Gs \to \Set$. \end{notation} Summarizing the content of the previous and the current subsections, we arrive at the following so-called \dq{theorem,} which is in effect little more than a systematic restatement of the definitions introduced so far. \begin{theorem}[Games as recursive coalgebras]\label{thm:main1:GamesAsRecursiveCoalgebras} The category of games is equivalent to the category of recursive $\Pf$-coalgebras\footnote{In fact, they are isomorphic.}. \[ \Gs\simeq \RecCoalg{\Pf} \] \end{theorem} \begin{proof} % For a game $\X = (X,\rel)$, we can define a structure map $\str:X \to \Pf(X)$ by $ x \mapsto \str (x) \coloneq \{x'\in X\mid x\rel x'\}$. The \dq{finite options} condition in the definition of games ensures the finiteness of $\str(x)$. % This correspondence defines a fully faithful functor $\Gs \to \Coalg{\Pf}$. This follows since a function $f\colon X \to X'$ is a $\Pf$-coalgebra homomorphism if and only if $f(\str(x))=\str'(f(x))$. The inclusion relation $f(\str(x))\subset \str'(f(x))$ is equivalent to the \dq{Graph morphism condition}, and the other inclusion relation $f(\str(x))\supset \str'(f(x))$ is equivalent to the \dq{Path-lifting condition}. This follows from \Cref{prop:GamesFiniteTimeIsRecursivenessAndGamesAsRecursiveCoalgebras} and the argument above \Cref{def:GameMorphism}. \end{proof} % A naive idea of \demph{game morphisms} might be functions that preserve the transition relation. In other words, a game morphism from $\X$ to $\Y$ might be guessed to be a function $X \to Y$ such that, if $x\rel_{\X} x'$ then $f(x) \rel_{\Y} f(x')$. % However, for several reasons, we will not adopt that naive definition. One intuitive reason is that they preserve only \dq{graph-theoretic data} and do not preserve \dq{game-theoretic data}. For example, such a \dq{graph-theoretic} function might send a $P$-state to an $N$-state and does not preserve the Grundy number and the birthday of games. % Modifying such a problematic point, we define the notion of game morphism utilizing the \dq{path-lifting property}: Some readers might find this \dq{path-lifting} condition unnatural and hard to accept. From the perspective of game theory, it could look like a \dq{category-theory-biased} condition with little connection to the phenomena of combinatorial game theory. 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 \dq{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, \Cref{fig:PathLiftingProperty} illustrates two graph morphisms: the left one satisfies the path-lifting property and preserves the outcome, while the right one does not. We will prove that all game morphisms preserve all \dq{recursively defined game data} (\memo{cref}). \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick, scale=1.0] % ===== First copy ===== % Left: 2-vertex graph \begin{scope}[xshift=0cm] \node[circle, fill=red, inner sep=2pt] (LtopA) at (0,1.0) {}; \node[circle, fill=blue, inner sep=2pt] (LbotA) at (0,-0.5) {}; \draw[->] (LtopA) -- (LbotA); \end{scope} % Right: 3-vertex graph \begin{scope}[xshift=4cm] \node[circle, fill=blue, inner sep=2pt] (RtopA) at (0,1.5) {}; \node[circle, fill=red, inner sep=2pt] (RmidA) at (0,0) {}; \node[circle, fill=blue, inner sep=2pt] (RbotA) at (0,-1.5) {}; \draw[->] (RtopA) -- (RmidA); \draw[->] (RmidA) -- (RbotA); \end{scope} % Dotted arrows (lighter) \draw[dashed,->,draw=black!50] (LtopA) -- (RmidA); \draw[dashed,->,draw=black!50] (LbotA) -- (RbotA); % Check mark for the left diagram \node[scale=2, black] at (2,-2.5) {\ding{51}}; % ===== Second copy (shifted to the right) ===== % Left: 2-vertex graph \begin{scope}[xshift=9cm] \node[circle, fill=red, inner sep=2pt] (LtopB) at (0,1.0) {}; \node[circle, fill=blue, inner sep=2pt] (LbotB) at (0,-0.5) {}; \draw[->] (LtopB) -- (LbotB); \end{scope} % Right: 3-vertex graph \begin{scope}[xshift=13cm] \node[circle, fill=blue, inner sep=2pt] (RtopB) at (0,1.5) {}; \node[circle, fill=red, inner sep=2pt] (RmidB) at (0,0) {}; \node[circle, fill=blue, inner sep=2pt] (RbotB) at (0,-1.5) {}; \draw[->] (RtopB) -- (RmidB); \draw[->] (RmidB) -- (RbotB); \end{scope} % Dotted arrows (lighter) \draw[dashed,->,draw=black!50] (LtopB) -- (RtopB); \draw[dashed,->,draw=black!50] (LbotB) -- (RmidB); % X mark for the right diagram \node[scale=2, black] at (11,-2.5) {\ding{55}}; \end{tikzpicture} \caption{A game morphism (left side) and a graph morphism that does not satisfy the path-lifting property (right side) with {\color{blue} $P$-states} and {\color{red} $N$-states}} \label{fig:PathLiftingProperty} \end{figure} \begin{remark}[Game is not just a graph with properties.]\label{rem:NotGraphStructureAndProperties} In \Cref{def:game}, we defined the notion of games as if they were just graphs satisfying two additional properties. However, that way of speaking is not accurate in the spirit of the categorical distinction between stuff, structure, and properties, since % Stuff, structure, and properties.]{baez2009lectures} the canonical forgetful functor \[ \Gs \to \Graphs \] is not fully faithful. (see \cite[][2.4. Stuff, structure, and properties]{baez2009lectures} for more explanation on the categorical distinction.) In \cite{adamek2005introduction}, Ad\'{a}mek also points out that to regard $\Pf$-coalgebras as graphs is \dq{not a reasonable point of view} as follows: % \memo{{\cite[][Example 2.7.]{adamek2005introduction}} \begin{quote} {\cite[][Example 2.7.]{adamek2005introduction}} Sometimes one also identifies $Q$ with a finitely branching directed graph [...] % :[...] % $\alpha(q)$ is the set of all neighbour nodes of $q$. However, this is often not a reasonable point of view because the coalgebra homomorphisms are much stronger than graph homomorphisms [...] % : [...] % given two systems $(Q,\alpha)$ and $(Q',\alpha')$, a coalgebra homomorphism is a function $h\colon Q\to Q'$ which preserves and reflects the dynamics. That is, $h$ is a graph homomorphism such that if $\overline{q}$ is a next state of $h(q)$ in $Q'$, then there exists a next state $\hat{q}$ of $q$ in $Q$ with $\overline{q}= h(\hat{q})$. \end{quote} % } \end{remark} From the categorical point of view, % how well does the category of games behave categorically? the category of games $\Gs$ 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. \begin{theorem}[Categorical properties of the category of games]\label{thm:CategoricalPropertiesOfGames} The category of games $\Gs$ has the following properties: \begin{itemize} \item The category of games $\Gs$ is locally finitely presentable. In particular, it has all small limits, small colimits, and small generators. \item The forgetful functor $U\colon \Gs \to \Set$ is comonadic. In particular, it preserves, reflects, and strictly creates all small colimits. % \item The category of games $\Gs$ has a subobject classifier. % \item The category of games $\Gs$ is not cartesian closed. \item The category of games $\Gs$ is not a topos, but it admits similar properties: it has a subobject classifier, the epi-mono factorization system, and subobject frames. % has all small limits, all small colimits, a small generating set, a subobject classifier, epi-mono factorization, ... \memo{write} \end{itemize} \end{theorem} \begin{proof} The proof is postponed until \Cref{appendix:CategoricalPropertiesOfGames}. \memo{Cref} \end{proof} \subsection{The terminal game consists of hereditarily finite sets} % \memo{ask refs} % With the category-theoretic terminology, we can conduct universal costructions of games! The first, and % Such an appearance of a set-theoretic construction is % % kind of necessary. Because both the initial algebra and the terminal game are the set-theoretic object $\H$, % % the set of all hereditarily finite sets, and % due to the fact that the nim game is the subgame of the terminal game, which we will investigate in the next subsection. This subsection aims to describe the terminal game, which plays the central role in the next section (\Cref{sec:NimSumTypeTheoremSchema}). First, we will describe it categorically (\Cref{eq:TerminalGameHereditarilyFiniteAdamek}), and then we will write it down in a set-theoretic way. The calculation of the terminal recursive coalgebra ($=$ the terminal game, in our case) is a priori nontrivial. However, thanks to \Cref{prop:TerminalRecursiveCoalgebraIsInitialAlgebra}, it is reduced to the classical theorem of transfinite construction of free algebras \cite{pohlova1973sums, adamek1974free}, which is known as Adamek's fixed point theorem. (A concise explanation, which suffices for our purpose, is found in \cite[][Proposition 4.6.1 (1)]{Jacobs_2016a}.) The construction states that the initial algebra of $\Pf\colon \Set \to \Set$, which also provides the terminal object in $\Gs\simeq \RecCoalg{\Pf}$ (\Cref{prop:TerminalRecursiveCoalgebraIsInitialAlgebra}), is given by the following colimit \begin{equation}\label{eq:TerminalGameHereditarilyFiniteAdamek} \begin{tikzcd} \emptyset \ar[r]& \Pf(\emptyset) \ar[r]& \Pf(\Pf(\emptyset)) \ar[r]&\Pf(\Pf(\Pf(\emptyset))) \ar[r]&\cdots \textrm{The Terminal Game!} % \H, \end{tikzcd} \end{equation} Here, we utilize the finite option condition in \Cref{def:game}, which implies that $\Pf\colon \Set \to \Set$ is finitary and hence preserves this colimit (cf. \Cref{rem:finiteOptions}). Let us write down this colimit. (A canonical choice of) this colimit is known as the set of \demph{hereditarily finite sets} in set theory. For its set-theoretic context and the terminology, see textbooks including \cite[][section I.10]{kunen2013set}. % \cite{kunen2013set} % Possibly the most important game is, the terminal object of $\Gs$. % First, we recall the set-theoretic notion of hereditarily finite sets. \begin{definition}[Hereditarily finite sets] A \demph{hereditarily finite set} is recursively defined as a finite set of hereditarily finite sets\footnote{Rigorously speaking, a hereditarily finite set is a set that is ensured to be hereditarily finite by this recursive definition.}. % A set $A$ is \demph{hereditarily finite} if all elements of $A$ are hereditarily finite. The set of all hereditarily finite sets is denoted by $\H$. \end{definition} As this recursive definition might look confusing at first glance, let us give several examples. \begin{example}\label{def:HereditarilyFiniteSets} The following sets are hereditarily finite sets: \begin{itemize} \item The empty set $\emptyset$ is trivially hereditarily finite since it has no element. \item Therefore, the set $\{\emptyset\}$ is also hereditarily finite. \item By induction, every (von Neumann's formulation of) natural number $n=\{0,1, \dots n-1\}$ is hereditarily finite. In other words, \[\N = \{0=\emptyset,\ 1= \{\emptyset\},\ 2= \{\emptyset,\{\emptyset\}\},\ 3=\{\emptyset, \{\emptyset\}, \{\emptyset,\{\emptyset\}\}\}, \dots\} \subset \H.\] \item The set $\{\{\emptyset\}\}$ is a hereditarily finite set that is not a natural number. \item Informally speaking, hereditarily finite sets are sets described by a finite number of parentheses, like $\{\{\},\{\{\{\}\}\},\{\{\}\}\}$. \item While all hereditarily finite sets are finite, the converse does not hold. For example, $\{\R\}$ is finite, but not hereditarily finite. \end{itemize} \end{example} \begin{remark}[von Neumann hierarchy] $\H$ is often denoted by $V_{\omega}$ in order to emphasize that it is the $\omega$-th of the von Neumann hierarchy. \end{remark} By definition, $\Pf(\H)$ is set-theoretically identical to $\H$. Therefore, $\H$ admits % the canonical \begin{align*} \textrm{the canonical $\Pf$-algebra structure }\;& \id_{\H}:\H \to \Pf(\H)\textrm{, and}\\ \textrm{the canonical $\Pf$-coalgebra structure }\;&\id_{\H}:\Pf(\H) \to \H. \end{align*} % \[\textrm{$\Pf$-algebra structure: }\id_{\H}:\H \to \Pf(\H)\textrm{, and}\] % \[\textrm{$\Pf$-coalgebra structure: }\id_{\H}:\Pf(\H) \to \H.\] % From now on, we will, by an abuse of notation, simply write $\H$ to mean either a $\Pf$-algebra structure or a $\Pf$-coalgebra structure. \begin{proposition}[Terminal object of $\Gs$]\label{prop:TerminalGameAndInitialAlgebraAreHereditarilyFiniteSets} The set $\H$ is the initial $\Pf$-algebra with the $\Pf$-algebra structure $\id_{\H}:\H \to \Pf(\H)$. Therefore, $\H$ is also the terminal object of $\Gs \simeq \RecCoalg{\Pf}$ with the $\Pf$-coalgebra structure $\id_{\H}:\Pf(\H) \to \H$. \end{proposition} \begin{proof} The former part follows from Adamek's fixed point theorem (see \Cref{eq:TerminalGameHereditarilyFiniteAdamek} and the discussion above). The latter follows from \Cref{prop:TerminalRecursiveCoalgebraIsInitialAlgebra}. \end{proof} It is worth writing down the terminal object of $\Gs$, which we will call the terminal game. \begin{definition}[Terminal game]\label{DefinitionUniversalGame} The \demph{terminal game} $\H=(\H,\rel)$ is the game whose underlying set is the set of all hereditarily finite sets $\H$ and whose relation $\rel$ is defined by \[x \rel y \iff y \in x.\] \end{definition} \begin{remark}[Ackerman's interpretation] As we promised, the terminal game is isomorphic to the binary exponent nim in \Cref{exmp:BinaryExponentNimOrTerminalGame}! % There is another way to describe the terminal game, using natural numbers $\N$ instead of hereditarily finite sets $\H$. Consider the following $\Pf$-algebra structure on $\N$ % One canonical choice of such a bijection is \[b: \Pf(\N)\to \N \colon S \mapsto \sum_{s\in S} 2^s,\] % on the set of natural numbers $\N$. which is just the binary expression and hence bijective. % Throughout this paper, $\H = \Pf(\H) $ is the crucial fact. But is it necessary to consider $\H$? Just by considering the cardinality, we should be able to consider a bijection between $\N$ and $\Pf(\N)$ as well! % since they are both countable sets. The unique $\Pf$-algebra morphism $\mathrm{Ack}\colon\H \to \N$ is called \demph{Ackerman's interpretation} \cite{ackermann1937widerspruchsfreiheit} and known to be bijective. % In fact, $\mathrm{Ack}$ gives an isomorphism between them as $\Pf$-algebras and $\Pf$-coalgebras (or, games). Consequently, this $\Pf$-algebra $(\N,b)$ is isomorphic to the initial $\Pf$-algebra $\H$, % also an initial object in $\Alg{\Pf}$, and and hence it is also the terminal object in $\Gs \simeq \RecCoalg{\Pf}$. \end{remark} \begin{definition}\label{def:ReductionMap} The \demph{reduction morphism} of a game $\X$ is the unique game morphism to the terminal game $\H$ and denoted by \[ \rd_{\X}\colon \X \to \H. \] \end{definition} % \begin{notation} % For a game $\X$, the unique game morphism to $\H$ is denoted by $\rd_{\X}\colon \X \to \H$. % \end{notation} \begin{remark}[Two definitions of combinatorial games]\label{RemarkTwoDefinitionsOfCombinatorialGames} Conventionally, a game is defined set-theoretically, and some people call an element of $\H$ a game. We do not adopt this formulation since \memo{Compare with \cite{bavsic2024categories}} \memo{existensial one} \end{remark} \invmemo{Is it related to the product-exp description of games?} \subsection{Recursively defined values are hylomorphisms} 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\"{i}ve notion of the game value. \begin{definition}\label{def:gameValue} A \demph{game value} to a set $A$ is a (proper class size) family of functions \[ \{v_{\X}\colon X\to A\}_{\X=(X, \str)\text{: game}} \] from all games to the set $A$. \end{definition} What we are interested in is when a game morphism $f\colon \X \to \Y$ \demph{preserves a game value} in the sense that $v_{\X}=v_\Y \circ f$ \[ \begin{tikzcd}[row sep = 5pt] \X\ar[rd,"v_\X"]\ar[dd, "f"']&\\ &A\\ \Y\ar[ru, "v_{\Y}"']& \end{tikzcd} \] \begin{definition}\label{def:recursivelyDefinedGameValue} A game value $\{v_{\X}\colon X\to A\}_{\X=(X, \str)\text{: game}}$ is said to be \demph{recursively defined} if there exists a $\Pf$-algebra structure $\A=(A, \alpha)$ on $A$ such that for any game $\X$, the function $v_{\X}$ is equal to the hylomorphism $\hylo_{\A, \X}\colon X \to A$. \end{definition} Thus, we obtain the following proposition as a special case of the abstract nonsense (\Cref{lem:StabilityOfHylomorphisms}). \begin{proposition}\label{prop:GameMorphismsPreservesAllRecursivelyDefinedGameValues} Any game morphism preserves all recursively defined game values. \end{proposition} \begin{proof} This is just the first half of \Cref{lem:StabilityOfHylomorphisms} \end{proof} \memo{compare with \cite{bavsic2024categories}} The outcome (\Cref{def:outcome}) and the Grundy number (\Cref{def:GrundyNumber}) are recursively defined. \begin{example}[Outcome] The outcome (\Cref{def:outcome}) $\{\oc_\X\colon X \to \{N,P\}\}_{\X=(X,{\rel})}$ is recursively defined by the $\Pf$-algebra $\NP=(\{N,P\}, \np)$, where \[ \np\colon \Pf(\{N,P\})\to \{N,P\}\colon S \mapsto \begin{cases} P &(P \notin S)\\ N &(P\in S). \end{cases} \] So we have \[ \oc=\hylo_{\NP} \] \end{example} \begin{example}[Grundy number] The Grundy number $\G =\{\G_{\X}\colon X \to \N\}$ (\Cref{def:GrundyNumber}) is recursively defined by the $\Pf$-algebra $\Mex=(\N, \mex)$ (\Cref{def:mex}). \[ \G= \hylo_{\Mex} \] \end{example} Other important game values in combinatorial game theory are also recursively defined. \begin{example}[Birthday] For a game $\X=(X, {\rel})$ and a state $x\in X$, its \demph{birthday}\footnote{The notion of birthday is usually defined for a set-theoretically constructed game, as an element of $\H$. Our version of the birthday of $x\in X$ coincides with the birthday of $\rd_{\X}(x)\in \H$.}, denoted by $\BirthDay_\X(x)$, is defined to be the length of the longest possible play from the state $x$. This game value $\{\BirthDay_{\X}\colon X \to \N\}$ is recursively defined by the $\Pf$-algebra $\Xem= (\N,\xem)$, where \[ \xem \colon \Pf(\N)\to \N\colon S \mapsto \min\{n \in \N\mid \text{for any }m\in S, m=Latex, thick, node distance=10mm and 15mm] % Central box (normal rectangle) \node[draw, minimum width=35mm, minimum height=15mm, align=center] (box) {theorem schema}; % Left inputs (rounded rectangles, closer) \node[draw, rounded corners=4pt, left=of box.west, xshift=-15mm, yshift=5mm, anchor=east, minimum width=26mm, align=center] (mono) {Monoidal structure $+$}; \node[draw, rounded corners=4pt, left=of box.west, xshift=-15mm, yshift=-5mm, anchor=east, minimum width=26mm, align=center] (pf) {$\Pf$-algebra $\A$}; % Right output (rounded rectangle, closer) \node[draw, rounded corners=4pt, right=of box.east, xshift=15mm, anchor=west, minimum width=26mm, align=center] (bouton) {Bouton monoid $\B_{{+}, \A}$}; % Connection points on the box \coordinate (boxWup) at ([yshift=5mm]box.west); \coordinate (boxWdn) at ([yshift=-5mm]box.west); % Arrows \draw[->] (mono.east) -- (boxWup); \draw[->] (pf.east) -- (boxWdn); \draw[->] (box.east) -- (bouton.west); \end{tikzpicture} \end{figure} \begin{figure}[ht] \centering \begin{tikzpicture}[>=Latex, thick, node distance=10mm and 15mm] % Central box (normal rectangle) \node[draw, minimum width=35mm, minimum height=15mm, align=center] (box) {theorem schema}; % Left inputs (rounded rectangles, closer) \node[draw, rounded corners=4pt, left=of box.west, xshift=-15mm, yshift=5mm, anchor=east, minimum width=26mm, align=center] (mono) {Conway addition ${+}$}; \node[draw, rounded corners=4pt, left=of box.west, xshift=-15mm, yshift=-5mm, anchor=east, minimum width=26mm, align=center] (pf) {Outcome $\NP$}; % Right output (rounded rectangle, closer) \node[draw, rounded corners=4pt, right=of box.east, xshift=15mm, anchor=west, minimum width=26mm, align=center] (bouton) {Nim sum $(\N, \nsum)$}; % Connection points on the box \coordinate (boxWup) at ([yshift=5mm]box.west); \coordinate (boxWdn) at ([yshift=-5mm]box.west); % Arrows \draw[->] (mono.east) -- (boxWup); \draw[->] (pf.east) -- (boxWdn); \draw[->] (box.east) -- (bouton.west); \end{tikzpicture} \end{figure} \subsection{Decomposing games with monoidal structures} % \subsection{Unital and nonunital monoidal structures on \texorpdfstring{$\Gs$}{Gs}} Our goal is to find a systematic way to decompose a complex game into simpler games. An established categorical tool to decompose objects is a \demph{monoidal structure} on a category. % $\Gs$. For those who are not familiar with this notion, a standard reference is \cite{Maclane1998CWMcategories}. This subsection aims to observe several monoidal structures on the category $\Gs$. \begin{remark}\label{rmk:nonUnital} In this section, we consider monoidal structures on a category. We will also use \demph{non-unital monoidal category}, which does not require the unit object. \memo{cite... Lurie?} Everything in this section works by replacing monoidal by non-unital monoidal, and monoid by semigroup. \end{remark} Hisorically, the Conway addition is regarded as the canonical choice of \dq{categories of games} (for example, \cite{joyal1977remarques}). It also provides a monoidal structure on our category. \begin{proposition}\label{prop:conwayAddition} The Conway addition is a symmetric monoidal closed structure on $\Gs$. \end{proposition} \begin{proof} Being symmetric monoidal is easily proven. In order to prove the closednedd, we can utilize the local presentability of $\Gs$ (\Cref{thm:CategoricalPropertiesOfGames}). In fact, due to the adjoint functor theorem for locally presentable categories (\memo{cite}\cite{adamek1994locally}), it suffices to prove that, for any game $\X=(X, {\rel})$, the functor $\X+ {-}\colon \Gs \to \Gs$ is cocontinuous. This follows from the commutative daigram \[ \begin{tikzcd} \Gs\ar[r, "\X+{-}"]\ar[d, "U"]&\Gs\ar[d, "U"]\\ \Set\ar[r, "X\times {-}"]&\Set, \end{tikzcd} \] and the fact that the comonadic functor $U\colon \Gs \to \Set$ reflects colimits. \end{proof} % \begin{remark} % In fact, the Conway addition is symmetric monoidal closed. Being symmetric monoidal is easily proven. In order to prove the closednedd, we can utilize the local presentability of $\Gs$ (\Cref{thm:CategoricalPropertiesOfGames}). In fact, due to the adjoint functor theorem for locally presentable categories (\memo{cite}\cite{adamek1994locally}), it suffices to prove that, for any game $\X=(X, {\rel})$, the functor $\X\otimes {-}\colon \Gs \to \Gs$ is cocontinuous. This follows from the commutative daigram % \[ % \begin{tikzcd} % \Gs\ar[r, "\X\otimes{-}"]\ar[d, "U"]&\Gs\ar[d, "U"]\\ % \Set\ar[r, "X\times {-}"]&\Set, % \end{tikzcd} % \] % and the fact that the comonadic functor $U\colon \Gs \to \Set$ reflects colimits. % \end{remark} \begin{example}[Selective sum \cite{smith1966graphs}]\label{exmp:SelctiveSum} For a finite number of games $\X_1, \dots, \X_n$ with $n\geq0$, their \demph{selective sum} $\X_1\lor \dots\lor \X_n$ is the game in which each player select at least one games out of the $n$ games and makes one move for each selected game. More foramlly spealing, the selective sum $\X\lor \Y$ of two games $\X=(X, \rel_\X), \Y=(Y,\rel_\Y)$ is defined as follows: \begin{itemize} \item Its underlying set is $X\times Y$. \item $ (x,y) \rel_{\X\lor\Y} (x',y')$ is defined by \[ (x,y) \rel_{\X\lor\Y} (x',y') \iff (x\to_\X x' \land y=y')\lor(x\to_\X x' \land y\to_\Y y')\lor(x=x' \land y\to_\Y y') \] \end{itemize} The selective sum defines a (unital, symmetric, and closed) monoidal structure on $\Gs$. the monoidal unit $1$. \end{example} \begin{example}[Conjunctive sum \cite{smith1966graphs}]\label{exmp:ConjunctiveSum} For a finite and positive number of games $\X_1, \dots, \X_n$ with $n>0$, their \demph{conjunctive sum} $\X_1\land \dots\land \X_n$ is the game in which each player makes a move for all of the $n$ games. More foramlly spealing, the conjunctive sum $\X\land \Y$ of two games $\X=(X, \rel_\X), \Y=(Y,\rel_\Y)$ is defined as follows: \begin{itemize} \item Its underlying set is $X\times Y$. \item $ (x,y) \rel_{\X\land\Y} (x',y')$ is defined by \[ (x,y) \rel_{\X\lor\Y} (x',y') \iff (x\to_\X x' \land y\to_\Y y') \] \end{itemize} The conjuctive sum defines a non-unital\footnote{The conjunctive sum defines a monoidal structure on $\Coalg{\Pf}$ with a monoidal unit (\Cref{fig:LoopNonGame}), which fails to be a game.} (but symmetric and closed) monoidal structure on $\Gs$. \end{example} \subsection{Synthesizing game values with Bouton monoids} \subsection{Preparation 1: Raw bouton monoid} A fun part of the coalgebra theory is to study the terminal object and the unique map into it. While terminal objects are typically too simple to be interesting in the \dq{usual} categories like $\Set, \Top, \Group, \Cat$, it becomes non-trivial in categories of coalgebras (see such examples in textbooks on coalgebras including \cite{jacobs2017introduction}). 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! \begin{proposition} For a monoidal category $(\C, I, \otimes)$ with a terminal object $1$, the object $1$ has a unique monoid structure with respect to the monoidal structure. \end{proposition} \begin{proof} All structural maps, $\eta\colon I \to 1$ and $\mu\colon 1\otimes 1 \to 1$, are uniquely determined. All required commutativities are trivial since $1$ is the terminal object. \end{proof} We will utilize the following well-known fact. \begin{proposition}[Well-known] Any (lax) monoidal functor $F\colon (\C, I_{\C}, \otimes_{\C})\to (\D,I_{\D},\otimes_{\D} )$ sends a monoid object in $\C$ to a monoid object in $\D$. \end{proposition} \begin{definition}We adopt the following terminologies: \begin{itemize} \item For a monoidal category $(\C, I_{\C}, \otimes_{\C})$ with a terminal object $1$, the \demph{terminal monoid} is the unique monoid object whose underlying object is $1$, which coincides with the terminal object of the category of monoid objects. \item For a lax monoidal functor $F\colon (\C, I_{\C}, \otimes_{\C})\to (\D,I_{\D},\otimes_{\D})$, the \demph{$F$-terminal monoid} is the monoid object in $\D$, obtained by sending the terminal monoid of $\C$ by the functor $F$. \end{itemize} \end{definition} \begin{example} The terminal monoid in $(\C, I_{\C}, \otimes_{\C})$ is $\id_{\C}$-terminal monoid. \end{example} \begin{example} For the free abelian group functor $F\colon \Set\to \mathbf{Ab}$, the $F$-terminal monoid is the ring of integers $\Z$. \end{example} % \begin{remark} % In fact, the terminal monoid is the terminal object of the category of monoid objects in $(\C, I_{\C}, \otimes_{\C})$. % \end{remark} % For many lax monoidal functors, the $F$-monoid is tirivial. For example, the forgetful functor Using these almost trivial categorical structures, we define the notion of raw Bouton monoid, which serves as the matterial to construct the Bouton monoid. \begin{definition}\label{def:rawBoutonMonoid} For a monoidal structure $(\Gs, I, \ast)$ on the category of games $\Gs$ such that the forgetful functor $U \colon (\Gs, I, \ast) \to (\Set,1,\times)$ is lax monoidal, the \demph{raw bouton monoid} $\RB_{\ast}$ is the $U$-terminal monoid with respect to the monoidal structure $\ast$. \end{definition} Notice that the raw bouton monoid is a usual monoid (i.e., a monoid in $\Set$) whose underlying set is $\H$ due to \Cref{prop:TerminalGameAndInitialAlgebraAreHereditarilyFiniteSets}. \begin{notation} For a monoidal structure $\ast\colon \Gs\times \Gs \to \Gs$ that makes $U\colon \Gs \to \Set$ lax monoidal, we adopt the following notations. \begin{itemize} \item The multiplication function of the raw bouton monoid is denoted by $\rbmult \colon\H\times \H \to \H$. % by abuse of notation. \item For two games $\X=(X,\rel_{\X})$ and $\Y=(Y,\rel_{\Y})$, the comparison map of the lax monoidal functor is denoted by $\mu_{\X,\Y}\colon X\times Y = U\X \times U\Y \to U(\X\ast \Y)$, and $\mu_{\X,\Y}(x,y)\in U(\X\ast \Y)$ is simply denoted by $(x,y) \in U(\X\ast \Y)$. \end{itemize} \end{notation} This raw bouton monoid structure $\rbmult\colon \H \times \H \to \H$ on $\H$ is a kind of miniture of the monoidal structure $*\colon \Gs \times \Gs \to \Gs$, exemplified by the case of the Conway addition: \begin{example}\label{exmp:rawBoutonMonoidConway} For the Conway addition $+$, the raw Bouton monoid structure $+_{\H} $ on $\H$ is given by \[ A+_{\H} B = \{a+_{\H} B \mid a\in A\} \cup \{A+_{\H} b\mid b\in B\}. \] In usual context like \cite{siegel2013combinatorial}, this is just called the Conway addition. \end{example} Similarly, the raw bouton monoid structure of $\lor, \land$ (\Cref{exmp:SelctiveSum} \Cref{exmp:ConjunctiveSum}) are given by \begin{align*} A \lor_{\H} B &= \{a\lor_{\H} B \mid a\in A\} \cup \{a\lor_{\H} b\mid a\in A, b\in B\} \cup \{A\lor_{\H} b\mid b\in B\}\\ A \land_{\H} B &= \{a\land_{\H} b\mid a\in A, b\in B\} \end{align*} \begin{proposition}[Raw generalized nim-sum rule] For any pair of games $\X=(X,\rel_{\X})$ and $\Y=(Y,\rel_{\Y})$, we have the following equation in the raw bouton monoid: \[ \rd_{\X\ast\Y}(x,y) = \rd_{\X}(x) \ast_{\H} \rd_{\Y}(y). \] \end{proposition} \begin{proof} Since $\H$ is the terminal game, we have the following commutative diagram in $\Gs$: \[ \begin{tikzcd} &\X\ast \Y\ar[rd,"\rd_{\X\ast \Y}"],\ar[d,"\rd_{\X}\ast \rd_{\Y}"']&\\ &\H\ast\H\ar[r,"\rd_{\H\ast \H}"']&\H. \end{tikzcd} \] By sending this diagram by $U$ and utilizing the naturality of $\mu$, we have the following commutative diagram in $\Set$: \[ \begin{tikzcd} X\times Y=U\X\times U\Y \ar[d,"U\rd_{\X}\times U\rd_{\Y}"']\ar[r,"\mu_{\X,\Y}"]&U(\X\ast \Y)\ar[rd,"U(\rd_{\X\ast \Y})"],\ar[d,"U(\rd_{\X}\ast \rd_{\Y})"']&\\ \H \times \H=U\H \times U\H\ar[r,"\mu_{\H,\H}"]\ar[rr, bend right , "\ast"']&U(\H\ast\H)\ar[r,"U(\rd_{\H\ast \H})"]&U(\H)=\H. \end{tikzcd} \] This proves the proposition. \end{proof} \subsection{Preparation 2: Minimum quotient monoid} % In principle, the raw Bouton monoid $\RB_{\ast}$ contains sufficient information to analyze games by decomposition, but practically, it is too large to compute efficiently. Therefore, in order to calculate desired information about games (such as outcome), we define an appropriate size quotient monoid of the raw Bouton monoid. In principle, the raw Bouton monoid $\RB_{\ast}$ contains sufficient information to decompose and analyze games, but practically, it is too large to calculate. Thus we will define a more practical \demph{Bouton monoid} in the next subsection by quotienting the raw bouton monoid to the minimum size necessary to calculate the desired information about the game (such as outcome of games). This subsection aims to recall a theoretical aspect of quotienting monoid. \invmemo{Same thing with rieg one.} \begin{definition}[Minimum quotient monoid] For a monoid $M$ and a function $f\colon M \to S$ to a set $S$, the \demph{minimum quotient monoid} of $f\colon M \to S$ is a surjective monoid homomorphism $q_f \colon M \twoheadrightarrow M_f$ such that \begin{enumerate} \item $f$ factors through $q_f$ (as a function). \label{ConditionSfactor} \item For an arbitrary surjective monoid homomorphism $q \colon M \to N$ such that $f$ factors thorough $q$, % satisfying condition (\Cref{ConditionSfactor}) there exists a function $r\colon N \to M_f$, (which is necessarily unique and is a surjective monoid homomorphism if it exists) such that $q_{f} = r\circ q$. \label{ConditionMinimum} \[ \begin{tikzcd} M\ar[rr,"f"]\ar[rd,"q", two heads]\ar[rdd,"q_{f}"', two heads]&&S\\ &N\ar[ru,dashed]\ar[d,"r", dashed]&\\ &M_{f}\ar[ruu,dashed]& \end{tikzcd} \] \end{enumerate} \end{definition} \begin{proposition}[Unique existence]\label{PropositionUniqueExistenceOfUniversalQuotient} For a monoid $M$, a set $S$, and a function $f\colon M \to S$, the minimum quotient monoid of $f$ exists and is unique (up to a canonical isomorphism). Furthermore, the corresponding congruence relation $\sim_{f} \subset M\times M$ is given by \[ m\sim_{f} m' \iff \text{for any }a,b\in M, f(amb)=f(am'b). \] That is, the quotient map $q_{f}\colon M\twoheadrightarrow M_{f}$ is (isomorphic to) the canonical surjection $M \twoheadrightarrow M/{\sim_{f}}$. \end{proposition} \begin{proof} % The maximum quotient monoid is the quotient o % % Since the maximum quotient monoid is the right adjoint of the embedding functor % % \[ % % \text{(the complete latice of quotient monoids of $M$)}\to M/\Set, % % \] % % the proposition follows from the general adjoint functor theorem. First, we need to prove the equivalence relation $\sim_f$ is a congruence relation. If $m\sim_f m'$ and $n\sim_f n'$, for any $a,b\in M$, we have \[ f(amnb)= f(am'nb)=f(am'n'b), \] and thus $mn\sim_f m'n'$. This proves that $\sim_f$ is a congruence relation, and $q_f\colon M \to M_f \coloneqq M/{\sim_f}$ is a surjective monoid homomorphism. In order to prove the condition \Cref{ConditionSfactor}, we need to prove $m\sim_f m' \implies f(m) = f(m')$, and this immediately follows from the definition of $\sim_f$ by taking the neutral element as $a,b$. Lastly, we prove the condition \Cref{ConditionMinimum}. We prove $q(m) = q(m') \implies m\sim_f m'$. If $q(m) = q(m')$, then for any $a,b\in M$, we have $q(amb)=q(a)q(m)q(b)= q(a)q(m')q(b)=q(am'b)$, hence $f(amb)=f(am'b)$. % , % hence $f$ factors through $q$. This proves that $q(m) = q(m') \implies m\sim_f m'$ and the condition \Cref{ConditionMinimum}. \end{proof} % \memo{Is the sizes of the minimum quotient is bounded by $|S|+ \aleph_0$? No} The structure of the minimum quotient is by no means anything nontrivial nor advanced--the idea of \dq{minimizing while preserving the algebraic structure without losing the data you care about} is quite mundane as exemplified by the following example: \begin{example} 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 $f\colon \comp \to \{\top, \bot\}$ defined by \[ f(z)= \begin{cases} \top &(z\in \R)\\ \bot &(z\notin\R ). \end{cases} \] Then, the minimum quotient monoid of $f$ (with respect to the additive structure of $\comp$) is given by taking the imaginary part $\comp \twoheadrightarrow \R i$. \end{example} \begin{remark} The existence follows only from the fact that the embedding \[ \mathrm{MonoidCongruences(M)} \hookrightarrow \mathrm{Equiv(M)} \] admits (not only a left adjoint but also) a right adjoint. In fact, due to the adjoint functor theorem, it suffices to prove that, for any family of monoid congruences, its supremum in the complete lattice of equivalence relations $\mathrm{Equiv(M)}$ is again a monoid congruence. \end{remark} \begin{remark} The construction of the minimum quotient monoid is ubiquitous in combinatorial game theory. For example, even the \dq{equality} of games is conventionally defined in this way! See \cite{siegel2013combinatorial}. It also appears in the definition of the syntactic monoid of a language. \end{remark} \subsection{Bouton monoid} \begin{definition}[Bouton monoid] For a monoidal structure $(\Gs,I, \ast)$ such that the forgetful functor $U\colon (\Gs,I,\ast) \to (\Set, 1,\times)$ is lax monoidal and a $\Pf$-algebra $\A=(A, \alpha)$, the \demph{Bouton monoid} $\B_{\ast, \A}$ is the minimum quotient monoid of a function \[ \begin{tikzcd} \RB_{\ast}= \H \ar[r,"\hylo_{\A,\H}"]& A. \end{tikzcd} \] The canonical surjective monoid homomorphism from $\RB_{\ast}$ to $\B_{\ast,\A}$ is denoted by $q_{\ast, \A}\colon \RB_{\ast}\twoheadrightarrow \B_{\ast,\A}$. By abuse of notation, the monoid structure on $\B_{\ast, \A}$ is denoted by % where $\RB_{\ast}$ is equipped with the raw Bouton monoid structure with respect to the monoidal structure $\ast$. \end{definition} \begin{definition}[Induction map] The \demph{induction map} of a $\Pf$-algebra $\A$ is the unique $\Pf$-algebra morphism from the initial $\Pf$-algebra $\H$ and denoted by \[ \Ind_{\A} \colon \H \to \A \]\memo{Rethink about the Notation} \end{definition} \begin{proposition} For a game $\X$ and a $\Pf$-algebra $\A=(A, \alpha)$, the hylomorphism $\hylo_{\A,\X}\colon \X \to \A$ is decomposed into \[ \begin{tikzcd} X \ar[r,"\rd_{\X}"] \ar[rr,"\hylo_{\A,\X}"', bend right] & \H\ar[r,"\hylo_{\A, \H}"] & A \end{tikzcd} \] \end{proposition} \begin{notation} We adopt the following notations: \begin{itemize} \item For a game $\X=(X,\rel_{\X})$, the function \[ \begin{tikzcd} X \ar[r,"\rd_{\X}"] & \RB_{\ast} \ar[r,"q_{\ast,\A}"] &\B_{\ast,\A} \end{tikzcd} \] is denoted by $\G_{\ast,\A}\colon \X \to \B_{\ast,\A}$. \end{itemize} \end{notation} \begin{theorem}\label{thm:maintheorem} For a monoidal structure $(\Gs,I, \ast)$ such that the forgetful functor $U\colon (\Gs,I,\ast) \to (\Set, 1,\times)$ is lax monoidal and a $\Pf$-algebra $\A=(A, \alpha)$, we have \[ \G_{*, \A}(x,y) = \G_{*, \A}(x) \ast \G_{*, \A}(y). \] \end{theorem} \begin{proposition}[A categorical characterization of Nim-sum] The monoid of nim-sum $(\N, 0, \nsum)$ is isomorphic to the Bouton monoid $\B_{{+}, \NP}$ of the Conway addition ${+}$ and the $\Pf$-algebra of $N,P$-states. \end{proposition} \begin{example}[Example 2: Remoteness] \end{example} % \subsection{Example 1: Nim-sum} % \subsection{Example 2: Remoteness} \subsection{Towards the differential structure of games} \section{Open questions}\label{sec:OpenQuestions} We believe that this paper is just a starting point of the theory of "Games as recursive coalgebras". There are still a lot of things to be calculated. We post some of the remaining questions in this appendix. \subsection{Urgent questions} \subsubsection{The differential structure} \subsection{Mathematically stated questions} \begin{question}[The closed structure] What is the internal hom? \end{question} \begin{question} Are the bouton functions always recursively defined? \end{question} \begin{question} Regarding the cyclic nim, is the Grundy number essentially indecomposable with respect to the $\geq 1$-monoidal structure? \end{question} \subsection{Ambiguous (but ambitious) questions!} \memo{It's quite natural to consider a multiplayer game, probability game, 2-turns/1-turn game, and other variants of games. And might be dealt with using some appropriate algebras. Furthermore, can we consider other graph data, like entropy? I know there is a notion of the temperature of a game. Is it an example of this framework?} \memo{By considering coalgebra-algebra map (from now, we call it ca map) (or, profunctor Alg -> Coalg), we may able to discard $\H$ and discuss everything so far...(?) The canonical map may be the unique ca map, and a game (or well-foundedness) may be equivalent to the condition that for any algebra, there uniquely exists a ca map to it.} \begin{question}[partisan games]\label{que:PartisanGames} Replacing $\Pf$ with other endofunctors to describe other types of game theory, like partisan, probabilistic, mis\`ere, transfinite, and loopy games. \end{question} Replacing $\Pf$ with other endofunctors to describe other types of game theory, like partisan, probabilistic, mis\`ere, transfinite, and loopy games. \begin{question} Double cat \end{question} \begin{question} lpac \end{question} \begin{question} semantics \end{question} \begin{question} Is there a nice way to calculate Bouton monoid? like Adamek construction? cf. Nim-sum is just the symmetric difference via the Ackerman interpretation. \end{question} \begin{question} Is there a topos-theoretic analogy? \end{question} \begin{question} As a relative local state classifier. \end{question} \begin{question} Difference structure \end{question} \begin{question}[Ryo Suzuki] Via the Ackerman interpretation, the nim-sum operation is interpreted as symmetric difference. In other words, $\Pf$ is object-wise bijective (but not isomorphic) to the monad induced by the monadic functor \[ U\colon \mathrm{Vect}_{\mathbb{F}_2}\to \Set, \] and the Nim-sum structure is nothing other than the vector space structure on the minimum fixed point. \end{question} \appendix \section{Categorical properties of games}\label{appendix:CategoricalPropertiesOfGames} What we will prove are the following categorical properties of $\Gs$. \begin{theorem} The category of games has the following properties: \begin{itemize} \item $\Gs$ is locally finitely presentable. \item In particular, $\Gs$ is small complete and small cocomplete. \item The forgetful functor $U\colon \Gs \to \Set$ has a right adjoint, and creates all colimits. \memo{Is it comonadic?} \item $\Gs$ has a subobject classifier \item $\Gs$ has the epi-mono factorization \item The subobject lattice of the object of $\Gs$ is a Heyting algebra. \end{itemize} However, \begin{itemize} \item $\Gs$ is not cartesian closed. \item In particular, $\Gs$ is not an (elementary) topos. \end{itemize} \end{theorem} \subsection{Subgames} In this subsection, we will define the notion of subgames and prove some basic properties. \begin{definition}[Subgame]\label{DefinitionSubgames} A subgame of a game $\X = (X, \rel)$ is a subset $S \subset X$ such that if $x\in S$ and $x\rel x'$ then $x' \in S$. \end{definition} Just to avoid the following argument becoming wordy, we introduce an accessibility relation in an obvious way: \begin{definition}[Accessibility relation]\label{DefinitionAccessibility} For a game $\X=(X, \rel)$, an element $x\in X$ is \demph{accessible} from $x'$ if there exists a non-negative integer $n \in \N$ and a sequence of elements $x_0, \dots x_n$ that satisfy \begin{itemize} \item $x_0=x'$, \item $x_i \rel x_{i+1}$ for $0\leq i < n$, and \item $x_n=x$. \end{itemize} This accessibility relation is denoted by $x' \acc x$. \end{definition} \begin{remark}[Subgames are downward closed subset] % If one regards a game as a poset (by the reflective and transitive closure of $\rel$), This accessibility relation is just the reflective and transitive closure of $\rel$, and defines a preorder on the underlying set $X$. Furthermore, due to the \dq{finite time} condition in Definition \Cref{def:game}, it is a partial order. The notion of subgames coincides with the notion of downward closed subsets of the poset. \end{remark} \begin{lemma}[Generation and Cogeneration of subgames]\label{GenerationanadCogenerationOfSubgames} For a game $\X=(X, \rel)$ and a subset $S\subset X$, \begin{itemize} \item there exists the minimum subgame of $\X$ that contains $S$. \item there exists the maximum subgame of $\X$ that is contained by $S$. \end{itemize} \end{lemma} \begin{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 \[\{x\in X\mid \exists s \in S, \ s\acc x\},\] and the latter is \[\{x\in X\mid \forall y \in X,\ (x\acc y \implies y \in S)\}\] \end{proof} \begin{definition}\label{SubgameGeneration} For a game $\X=(X, \rel)$ and a subset $S\subset X$, the minimum subgame of $\X$ that contains $S$ is called the subgame generated by $S$, and denoted by $\gen{S}$. \end{definition} \begin{lemma}\label{LemmaFinitelygeneratedSubgameisFinite} A subgame generated by a finite subset is finite. \end{lemma} \begin{lemma}[Image is a subgame]\label{LemmaImageisSubgame} For a game morphism $f\colon \X \to \Y$, its image $\Image{f}$ is a subgame of $\Y$. \end{lemma} \begin{proof} This is due to the second condition (\Cref{conditionLocallySurjective}) of Definition \Cref{def:GameMorphism}. \end{proof} \begin{proposition}[Surjection-Subgame factorization]\label{PropositionSurjSubgameFactorization} A game morphism is uniquely factored into a composition of a surjective morphism followed by a subgame inclusion. \end{proposition} We obtain the following factorization system, which will turn out to be the epi-mono factorization (see \memo{ref}) \begin{proposition}[Subgames $=$ Subobjects]\label{PropositionSubgameAndSubobjectAndMono} For a game morphism $f\colon \X \to \Y$, the following conditions are equivalent: \begin{enumerate} \item $f$ is monic in $\Gs$. \label{ConditionMonic} \item $f$ is injective. \label{ConditionInjective} \item $f$ is (canonically isomorphic to) a subgame inclusion.\label{ConditionSubobject} \end{enumerate} \end{proposition} \begin{proof} The implications $\Cref{ConditionSubobject} \implies \Cref{ConditionInjective}$ and $\Cref{ConditionInjective} \implies \Cref{ConditionMonic}$ are easy to prove. We prove the converses. First, we prove $\Cref{ConditionMonic}\implies \Cref{ConditionInjective}$. Suppose $f$ is monic. We prove that $\# f^{-1}(y) \leq 1$ by induction on the well-founded order structure $(Y,\acc)$. Assuming that, for any $y' \acc y$ and $y\neq y'$, $\# f^{-1}(y') \leq 1$ holds, we prove $\# f^{-1}(y) \leq 1$. If $\# f^{-1}(y) =0$, then the proof is completed. So we can assume $\# f^{-1}(y) \geq 1$. In that case, $\# f^{-1}(y') =1$ for any $y'\neq y$ that is accessible from $y$. Let us define $S\subset X$ as \[ S \coloneqq \{x\in X\mid f(x)\neq y \text{ and } y \acc f(x)\}. \] It is not hard to prove that $S$ is a subgame of $\X$. We define a new game $\W$, % whose underlying set is $S \coprod \{\ast_0, \ast_1\}$. The relation $\ast_i \rel_{\W} s$ for $i=0,1$ and $s\in S$ is defined by % \[ % \ast_i \rel_{\W} s \iff y\rel_{\Y} f(s) % \] % and no other relation is added. whose underlying set is $S \coprod \{\ast\}$. The relation $\ast \rel_{\W} s$ for $s\in S$ is defined by \[ \ast \rel_{\W} s \iff y\rel_{\Y} f(s) \] and no other relation is added. \memo{This is a game, since $S$ is finite.}Then, for any $x\in f^{-1}(y)$, the function $g_{x} \colon \W \to \X$ defined by \[ g_{x}(w) = \begin{cases} s &(w=s\in S)\\ x & (w= \ast) \end{cases} \] is a game morphism. It is because, for any $x'\in \X$, \begin{align*} x \rel_{\X} x' &\iff y= f(x) \rel_{\Y} f(x')\\ &\iff x'\in S \text{ and }y \rel_{\Y} f(x')\\ &\iff x'\in S \text{ and }\ast \rel_{\W} x', \end{align*} where the first equivalence is due to the induction hypothesis. For any (possibly non-distinct) $x_0, x_1 \in f^{-1}(y)$, we have a diagram \[ \begin{tikzcd} \W\ar[r,"g_{x_0}", shift left]\ar[r,"g_{x_1}"',shift right]&\X\ar[r,"f"]&\Y, \end{tikzcd} \] with the same composite. Since we assumed that $f$ is monic, we obtain $g_{x_0} = g_{x_1}$ and $x_0 = x_1$. Next, we prove $\Cref{ConditionInjective}\implies \Cref{ConditionSubobject}$. Suppose $f$ is injective. Then $f$ is factored as \[ \X \to \Image{f} \to \Y, \] where $\Image{f} \to \Y$ is a subgame inclusion (Proposition \Cref{PropositionSurjSubgameFactorization}). Since $\X \to \Image{f}$ is a bijective game morphism, it is an isomorphism (Lemma \Cref{LemmaForgetfulFaithfulConservative}). \end{proof} %\newpage \subsection{Creation of colimits}\label{SubsectionCocompleteness} Before proceeding to the following contents, we will prove a basic lemma. \begin{lemma}\label{LemmaForgetfulFaithfulConservative} The forgetful functor $U \colon \Gs \to \Set$ is faithful and conservative. \end{lemma} \begin{proof} This is an immediate corollary of the coalgebraic description of games. Direct proof is also easy. \end{proof} \begin{proposition}[Well-founded part adjunction] The category of games $\Gs$ is a coreflective subcategory of $\Coalg{\Pf}$. \end{proposition} \begin{proof} \cite{adamek2020well} \end{proof} \begin{proposition}\label{propositionCocompleteness} The forgetful functor $U \colon \Gs \to \Set$ strictly creates all small colimits. In particuler, $\Gs$ is cocomplete. \end{proposition} \begin{proof} The forgetful functor is decomposed into \[ \Gs \to \Coalg{\Pf}\to \Set. \] And both functors above strictly create all small colimits. \end{proof} \memo{Does it come from the comonadicity?} \subsection{The forgetful-cofree adjunction and its comonadicity % Labeled hereditarily finite sets give the } \begin{definition}[Labeled Hereditarily finite sets]\label{DefinitionLabeledHFS} For a set (of labels) $\Lambda$, a $\Lambda$-labeled hereditarily finite set is recursively defined as a pair $(S,\lambda)$ of a finite set $S$ of $\Lambda$-labeled hereditarily finite sets and $\lambda \in \Lambda$. In other words, the set of all $\Lambda$-labeled hereditarily finite sets $\HF(\Lambda)$ is defined to be \[ \HF(\Lambda) = \bigcup_{k=0}^{\infty} \HF_{n}(\Lambda), \] where $\HF_{0}(\Lambda)= \emptyset$ and $\HF_{n+1}(\Lambda)= \Pf(\HF_{n}(\Lambda)) \times \Lambda$. \end{definition} \begin{proposition}[Forgetful-Cofree adjunction]\label{PropositionForgetfulCofreeadjunction} $\HF$ gives a right adjoint to the forgetful functor. \[\ADJ{\Set}{\HF}{\Gs}{U}\] \end{proposition} % \begin{notation}\label{NotationLabeledHF} % The set of all $\Lambda$-labeled hereditarily finite sets is denoted by $\HF(\Lambda)$. % \end{notation} \subsection{Epimorphisms, monomorphisms, and factorization} \begin{proposition}[Epic and monic morphisms]\label{PropositionEpicandMonicMorphisms} In the category of games $\Gs$, a morphism $f \colon \X\to \Y$ is \begin{enumerate} \item epic, if and only if it is surjective. \label{StatementEpic} \item monic, if and only if it is injective.\label{StatementMonic} \item isomorphic, if and only if it is bijective.\label{StatementIsomorphic} \end{enumerate} \end{proposition} \begin{proof} (\Cref{StatementEpic}) follows from the fact that the forgetful functor $\Gs \to \Set$ is a faithful left adjoint (Proposition \Cref{PropositionForgetfulCofreeadjunction}). (\Cref{StatementIsomorphic}) \memo{Does it come from the comonadicity? Yes, reflective tripleability } \end{proof} \begin{corollary}[Subgame]\label{CorollarySubgame} A subobject of a game $\X = (X, \rel)$ is (canonically isomorphic to) a downward closed subset $S\subset X$, i.e., a subset $S \subset X$ such that if $x\in S$ and $x\rel x'$ then $x' \in S$. \end{corollary} \begin{corollary} The category of games admits the epi-mono orthogonal factorization system. \end{corollary} \subsection{The subobject classifier}\label{SubsectionSubobjectClassifier} In this subsection, we will give an explicit description of the subobject classifier of the category of games. \begin{figure}[ht] \centering \includegraphics[width=0.5\linewidth]{images/SubobjectClassifier.jpeg} \caption{An incomplete sketch of the subobject classifier} \label{FigureSubobjectClassifier} \end{figure} \begin{figure}[ht] \centering \includegraphics[width=0.5\linewidth]{images/SubobjectClassification.jpeg} \caption{An example of subobject classification} \label{FigureSubobjectClassification} \end{figure} Our idea of the construction is simple: utilize the cofree-forgetful adjunction (Prposition \Cref{PropositionForgetfulCofreeadjunction}). Because of Corollary \Cref{CorollarySubgame}, we have the following canonical injection \[ \mathrm{Sub}_{\Gs}(\X) \rightarrowtail \Set(X,\{\top,\bot\}) \cong \Gs(\X,\HF(\{\top,\bot\})). \] 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 $\HF(\{\top,\bot\})$. \begin{definition}\label{DefinitionTruthClosed} A $\{\top, \bot\}$-labeled hereditarily finite set $A\in \HF(\{\top,\bot\})$ is \demph{truth-closed} if \begin{enumerate} \item if $A$ itself is labeled by $\top$, then every element of $A$ is also labeled by $\top$, and \item every element of $A$ is truth-closed. \end{enumerate} \end{definition} \begin{notation} The game of all truth-closed $\{\top,\bot\}$-labeled hereditarily finite sets is denoted by $\Omega$. \end{notation} See Figure \Cref{FigureSubobjectClassifier} and Figure \Cref{FigureSubobjectClassification}. \begin{proposition}[Subobject classifier]\label{PropositionSubobjectClassifier} % The subgame of $\HF(\{\top,\bot\})$ that consists of a $\{\top, \bot\}$-colored set $A$ that satisfies % \begin{itemize} % \item If % \end{itemize} The game $\Omega$ is the subobject classifier of the category of games $\Gs$. \end{proposition} % \subsection{\texorpdfstring{$\Gs$ is locally finitely presentable}{The category of games is locally finitely presentable}} \subsection{Locally finitely presentable} % The category of games is \begin{lemma}\label{LemmaGamesAreLocallyFinite} Every game is a directed colimit of its finite subgames. \end{lemma} \begin{proposition}[Finitely presentable $=$ Finite]\label{PropositionFinitePresentabilityOfGames} A game is a finitely generated object if and only if its underlying set is a finite set. \end{proposition} \begin{proof} If a game is finitely generated, due to Lemma \Cref{LemmaGamesAreLocallyFinite}, it should be finite. We prove the converse. Suppose a game $\X$ is finite. We will prove that the hom functor \[ \Gs (\X, -)\colon \Gs \to \Set \] preserves filtered colimits. Let $\C$ be a filtered category, $F\colon \C \to \Gs$ be a functor, and $\{\alpha_c \colon Fc \to \Y\}_{c\in \ob{\C}}$ be the colimit cocone. Take an arbitrary morphism $f\colon \X \to \Y$. Our goal is to prove that there exists $c\in \ob{\C}$ such that $f$ has a lift $g$ along $\alpha_c$ \[ \begin{tikzcd} &Fc\ar[d,"\alpha_c"]\\ \X\ar[r,"f"']\ar[ru, dashed,"\exists g"]&\Y. \end{tikzcd} \] (The essential uniqueness of the factorization follows from the case of $\Set$ and Proposition \Cref{propositionCocompleteness}.) Since a finite set is finitely presentable in $\Set$, and $U$ preserves small colimits (in particuler, filtered colimits), there exists a function $h \colon U\X \to UFc$ such that the following diagram commutes \[ \begin{tikzcd} &UFc\ar[d,"U\alpha_c"]\\ U\X\ar[r,"Uf"']\ar[ru, dashed,"h"]&U\Y. \end{tikzcd} \] Let $\iota\colon \gS\to Fc$ be the subgame of $Fc$, generated by the image of $h$. Since $\X$ is finite, $\gS$ is also finite (Lemma \Cref{LemmaFinitelygeneratedSubgameisFinite}). \[ \begin{tikzcd} &\gS\ar[r,\mono,"\iota"]&Fc\ar[d,"\alpha_c"]\\ \X\ar[rr,"f"']\ar[ru, dashed,"h"]&&\Y, \end{tikzcd} \] where $h$ is a mere function, denoted by a dashed arrow. Since $\Y$ is a filtered colimit (preserved by $U$) and $\gS$ is finite, there exists $k\colon c \to c'$ in $\C$ such that $\alpha_{c'}$ is injective on the subgame $Fk(\gS)=\Image{(Fk \circ \iota)}$ of $Fc'$ (Lemma \Cref{LemmaImageisSubgame}). In other words, the morphism $\alpha_{c'}\circ m$ in the following diagram is injective. (Again, $h$ is a mere function.) % for the epi-mono (=Surj-subgame) factorization (Proposition \Cref{PropositionSurjSubgameFactorization}) of $Fk \circ \iota$ % \[ % \begin{tikzcd} % \gS\ar[r,\mono,"\iota"]\ar[d,\epi]&Fc\ar[d,"Fk"']\\ % Fk(\gS)\ar[r,\mono]&Fc' % \end{tikzcd} % \] \[ \begin{tikzcd} &\gS\ar[r,\mono,"\iota"]\ar[d,\epi,"e"']&Fc\ar[dd,bend left, "\alpha_c"]\ar[d,"Fk"']\\ &Fk(\gS)\ar[r,\mono,"m"]\ar[rd,"\alpha_{c'}\circ m"', \mono]&Fc'\ar[d,"\alpha_{c'}"']\\ \X\ar[rr,"f"']\ar[ruu, dashed,"h", bend left]&&\Y, \end{tikzcd} \] Because the morphism $\alpha_{c'}\circ m$ is injective, it is a subgame embedding (Proposition \Cref{PropositionSubgameAndSubobjectAndMono}). Therefore, the lift of $f$ along $\alpha_{c'}\circ m$ is a game morphism. \[ \begin{tikzcd} &\gS\ar[r,\mono,"\iota"]\ar[d,\epi,"e"']&Fc\ar[dd,bend left, "\alpha_c"]\ar[d,"Fk"']\\ &Fk(\gS)\ar[r,\mono,"m"]\ar[rd,"\alpha_{c'}\circ m"', \mono]&Fc'\ar[d,"\alpha_{c'}"']\\ \X\ar[rr,"f"']\ar[ru,"h\circ e"]\ar[ruu, dashed,"h", bend left]&&\Y, \end{tikzcd} \] This proves that $f$ has a lift along $\alpha_{c'}$ in the category $\Gs$. \end{proof} \begin{theorem}\label{TheoremLocallyFinitePresentabilityOfTheGameCategory} The category of games $\Gs$ is locally fintiely presentble. \end{theorem} \begin{corollary}\label{CorollaryCompletenessOfGames} The category of games $\Gs$ is complete. \end{corollary} \subsection{Limits of games}\label{SubsectionLimitsOfGames} In this subsection, we will give an explicit description of (small) limits of games. Since every small limit is described by equalizers and products, we will explain only for them. \subsubsection{Equalizer}\label{SubsubsectionEqualizer} \subsubsection{Binary products}\label{SubSubsectionProducts} In this subsection, we will explicitly construct the binary product of games. Its existence is already proven (Corollary \Cref{CorollaryCompletenessOfGames}). Our plan is similar to the construction of the subobject classifier (subsection \Cref{SubsectionSubobjectClassifier}). That is, utilizing the labeled hereditarily finite sets. \begin{definition}\label{DefinitionProduct} Let $\X=(X,\rel_{\X})$ and $\Y= (Y, \rel_{\Y})$ two games. A $X\times Y$-labeled hereditarily finite set $(S, (x,y)) \in \HF({X\times Y})$, where $S$ is a finite set of $X\times Y$-labeled hereditarily finite sets $S=\{(S_i, (x_i,y_i))\}_{i=1}^{n}$, is \demph{enumerative}, if \begin{enumerate} \item every element $(S_i, (x_i,y_i))$ is enumerative, \item $\theta_{\X} (x) = \{x_i\}_{i=1}^{n}$, and \item $\theta_{\Y} (y) = \{y_i\}_{i=1}^{n}$, % \item $\{x_i\mid 1 \leq i \leq n\}=\{x'\in X\mid x\rel x'\}$ and $\{y_i\mid 1 \leq i \leq n\}=\{y'\in Y\mid y\rel y'\}$ \end{enumerate} where $\theta_{\X}$ and $\theta_{\Y}$ denote the associated coalgebra structure functions. The subgame of $\HF{(X\times Y)}$, spanned by all enumerative elements, is denoted by $\X \times \Y$. \end{definition} \begin{proposition}\label{ProppositionProduct} For two games $\X=(X,\rel_{\X})$ and $\Y= (Y, \rel_{\Y})$, the game % of enumerative $X\times Y$-labeled hereditarily finite sets $\X\times \Y$ gives the categorical product of $\X$ and $\Y$. \end{proposition} \memo{Write one example.} \memo{On Infinite Products} \begin{remark}[Relationship with the stirling number] % starling number]\label{RemarkStarlingNumber} \memo{i forgot what I meant. Is this related to the recursive definition of Stirling number?} \end{remark} \section{Mex is the right adjoint of Nim} The bouton theorem (\Cref{thm:Bouton}) looks particularly simple due to the fact that the Grundy number map $\G_{\Nim{1}}\colon \N \to \N$ turs out to be the identity map $\id_{\N}$. The aim of this appendix is to explain this coincidence $\G_{\Nim{1}}=\id_{\N}$ by a \dq{categorical origin} of the mex function $\mex\colon \Pf(\N)\to \N$. We start with a simple observation. \begin{proposition}\label{prop:SectionIdentity} For an endofunctor $T\colon \C \to \C$ on a category $\C$, a $T$-algebra $\A=(A,\alpha)$, and a recursive $T$-coalgebra $\X=(A, \str)$ on the same object $A\in \ob(\C)$, the following two condtions are equivalent. \begin{enumerate} \item $\str$ is the section of $\alpha$, i.e., $\alpha\circ \str = \id_A$. \item The hylomorphism $\hylo_{\A,\X}\colon A \to A$ coincides with the identity map $\id_A$. \end{enumerate} % % For a $\Pf$-algebra structure $\alpha \colon \Pf(A)\to A$ and a game structure $\theta\colon A \to \Pf(A)$ on the same set $A$, the following two condtions are equivalent. % \begin{enumerate} % \item $\alpha$ is the section of $\theta$, i.e., $\alpha\circ \theta = \id_A$. % \item The hylomorphism $\hylo_{(A, \alpha),(A, \theta)}\colon A \to A$ coincides with the identity map $\id_A$. % \end{enumerate} \end{proposition} \begin{proof} Both conditions are equivalent to the commutativity of \[ \begin{tikzcd} TA\ar[r, "T(\id_{A})"]&TA\ar[d,"\alpha"']\\ A\ar[u,"\str"]\ar[r,"\id_{A}"]&A. \end{tikzcd} \] \end{proof} Therefore, unsurprisingly, the coincidence $\G_{\Nim{1}}(=\hylo_{\Mex,\Nim{1}})=\id_{\N}$ comes from the equation $\mex\circ \nu = \id_\N$ \[ \mex\circ\nu(n)=\mex\{0,1, \dots, n-1\}=n. \] % \begin{remark}[Grundy number, Nim, and Birthday are an adjoint triple]\memo{check the definition of Birthday} % There is an interesting relationship between % \end{remark} % Where does $\mex$ come from? % We already know that there is a natural $\Pf$-coalgebra structure $\nu:\N \to \Pf(\N)$ (see \Cref{exmp:NimCoalgebra}). This is canonical in some senses. % \begin{itemize} % \item It is the sub-game of the terminal game $\H$. % \item It is $\Nim{1}$. % \item Under the conventional set-theoretic formulation of natural numbers, it is just the inclusion of the subset (von Neumann's definition). % \end{itemize} % Nothing is surprising so far. What might be a bit surprising is that $\mex$ is actually the canonical choice of a retraction of $\nu$ in a categorical sence. % Now, we need a natural function $\N\to \Pf(\N)$, and we need an opposite direction function in a canonical way. When a canonical \dq{reverse} of a map $\nu\colon \N \to \Pf(\N)$ is needed, we category theorists think like \dq{ok, then consider its adjoint!} \[ \begin{tikzcd} \N \ar[r, shift left= 5pt,"\nu" name=A]&\Pf(\N)\ar[l, shift left= 5pt, "?"name=B]\ar[phantom, from= A, to=B, "\dashv" rotate=-90] \end{tikzcd} \] And the adjoint turns out to be mex! Here, we consider the usual order on each set, namely, the usual order $\leq$ on $\N$ and the inclusion relation on $\Pf(\N)$. \memo{there is also a left adjoint. And it also gives an interesting value of a game state, called \emph{birthday} of a game} \begin{proposition}[A characterization of mex] The right adjoint of $\nu$ is $\mex$. \[ \begin{tikzcd} \N \ar[r, shift left= 5pt,"\nu" name=A]&\Pf(\N)\ar[l, shift left= 5pt, "\mex"name=B]\ar[phantom, from= A, to=B, "\dashv" rotate=-90] \end{tikzcd} \] \end{proposition} \begin{proof} Take any $n\in \N$ and $S\in \Pf(\N)$. Then, we have \begin{align*} n\leq \mex{S} &\iff n\leq \min {S^{\mathrm{c}}}\\ &\iff \nu (n)^{\mathrm{c}} \supset S^{\mathrm{c}}\\ &\iff \nu (n) \subset S. \end{align*} \end{proof} Since $\nu$ is fully faithful, its right adjoint $\mex$ should be a retract of $\nu$ thanks to the general theory of adjoint functors (and the skeletality of the posets). % In this sense, $(\N, \mex)$ is one canonical choice of $\Pf$-algerba structure on $\N$. % Then we have the canonical function from $\H$ to $\N$. % \begin{definition}\label{DefinitionMu} % $\mu:\H \to \N$ denotes the unique $\Pf$-algebra morphism from the initial algebra $(\H, \id{\H})$ to $(\N, \mex)$. % \end{definition} % \begin{theorem}[Origin of Grundy number] % % For a game $\X = (X, \str)$, the value of $x \in X$ by the canonical function coincides with the Grundy number $\G{\X}{x}$. % For a game $\X$, the composite function $\mu \circ !_{\X}$ coincide with $\mathcal{G}_{\X}$ % \[ % \begin{tikzcd} % X\ar[r,"!_{\X}"]\ar[rr,bend right,"\mathcal{G}_{\X}"']&\H\ar[r,"\mu"]&\N % \end{tikzcd} % \] % \end{theorem} % % \memo{A morphism from a coalgebra to an algebra is called a \emph{coalgebra-algebra morphism}. Furthermore, such a unique coalgebra-algebra morphism is called \emph{a hylo morphism} in computer science. Games are characterized in terms of coalgebra-algebra morphisms. See Appendix \ref{AppendixGameAsWellFounded}.} Similar phenomena are ubiquitous in this paper. For example, $\nu\colon \N \to \Pf(\N)$ also admits a right adjoint, which turns out to be $\xem$! \[ \begin{tikzcd} \N \ar[r, shift left= 5pt,"\nu" name=A]&\Pf(\N)\ar[l, shift left= 5pt, "\xem"name=B]\ar[phantom, from= A, to=B, "\dashv" rotate=90] \end{tikzcd} \] Therefore, \Cref{prop:SectionIdentity} implies that $\BirthDay_{\Nim{1}}\colon \N \to \N$ is the identity map. \begin{example}[Grundy number vs Birthday] Let $\mathrm{xem}$ be the left adjoint of $\nu$. (This is the dual of $\mex$!) Then, the induced value of a game state is what's called \emph{the birthday of a game}. \end{example} \section{Possible appendices} \section{Relationship with local state classifiers} \cite{hora2024internal} \begin{conjecture} For any monoidal categories $(\C, I_\C, \otimes_\C), (\D, I_\D, \otimes_\D)$ and a lax monoidal functor $(F\colon \C \to \D)$ \end{conjecture} \invmemo{remark: LSC} \invmemo{"almost all states are N-state"} \printbibliography \end{document}