\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{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{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{remark}[theorem]{Remark} \newtheorem{notation}[theorem]{Notation} \newtheorem{question}[theorem]{Question} \newtheorem{idea}[theorem]{Idea} \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{\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{\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{\mex}{\mathsf{mex}} \newcommand{\xem}{\mathsf{xem}} \newcommand{\hylo}{\mathsf{hylo}} % \newcommand{\G}[2]{\mathcal{G}_{#1}(#2)} \newcommand{\G}{\mathcal{G}} \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{R}} \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{\rd}{\mathsf{Red}} \newcommand{\NP}{\mathsf{NP}} \title{Games as recursive coalgebras\\ A categorical % characterization and generalization of view on the Nim-sum} % \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} 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. \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$ srtones in each heap. Two players take turns removing stones, but on each turn, they must remove stones form 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 justfy 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 thank to my supervisor Ryu Hasegawa for his continuous supports and advices 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 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 to 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 the \dq{graph-theoretic 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 same thing to know \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{DefinitionOutcome} 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, {\to})$ 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, {\to})$, where \[ n\to 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\to 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\to m$ by \[n\to m \iff m=n-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 \otimes \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$. \item We calculate the outcome of $\X$ from the Grundy number of $\X$. \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 \otimes \Y$ is the game $(X\times Y, \rel_{\X \otimes \Y})$, where $(x,y) \rel_{\X \otimes \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) {$\otimes$}; % ===== 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 \otimes \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$, but in this paper, we prefer the tensor symbol $\X\otimes \Y$. 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} \otimes \dots \otimes \Nim{1}\] \end{example} % What we want to do is to decompose a game into smaller parts and synthesize the analysis of smaller games: % \begin{itemize} % \item We want to know the winning strategy of a complex game $\X$. % \item We devide the game $\X$ into a Conway sum of smaller games $\X = \Y \otimes \Z$. % \item We analyze the smaller games $\Y,\Z$. % \item We synthesize the properties on $\Y, \Z$ into that of the game $\X$. % \end{itemize} We want to utilize the Conway addition $\otimes$ to calculate the outcome of a state $(x,y)\in \X\otimes \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\otimes \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, {\to})$ 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\memo{cref}. \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\otimes\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 \otimes \Z$, we have \[ x=(y,z) \text{ is a $P$-state} {\iff} \G_{\Y\otimes\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 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, {\to}\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\to x'\}. \end{equation} If a graph $\X=(X, {\to})$ 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{PropositionTerminalRecursiveCoalgebra} 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, {\to}\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\to x'\} % \end{equation} In terms of coalgebras, any graph $\X=(X, {\to})$ 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:GamesFiniteTimeIsRecursiveness} For any graph $\X=(X, {\to})$ 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} \memo{write proof, and cite} \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} \begin{theorem} The category of games is equivalent to the category of recursive $\Pf$-coalgebras. \[ \Gs\simeq \RecCoalg{\Pf} \] \end{theorem} \begin{proof} % Notice that our formulation of games is a special case of $\Pf$-coalgebra. 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}. To prove the essential image of the fully faithful functor is the full subcategory of recursive coalgebras, it suffices to see that a $\Pf$-coalgebra $(X,\str)$ is recursive if and only if the corresponding graph satisfies the \dq{finite time} condition. If the graph satisfies the finite time condition, we can resursively construct the unique coalgebra-algebra morphism, and prove that it is recurisive coalgebra. Conversely, suppose a coalgebra $\X= (X,\str)$ is a recursive coalgebra. Define a $T$-algebra $\A=(\N,\xem)$ by \[ \xem(S) \coloneq \min\{n \in \N\mid \text{for any }m\in S, m\hylo_{\A,\X}(x')$. By the well-foundedness of the poset $(\N,<)$, this proves that thecorresponding graph of the coalgebra $\X=(X, \str)$ satisfies the finite time condition, thus is a game. \end{proof} \begin{remark} \cite{adamek2020well} \end{remark} 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. See next subsection. % \section{Category of games}\label{SectionCategoryOfGames} \subsubsection{Digression: An elementary description of the category of games}\label{ssec:ElementaryDescriptionOfTheCategoryOfGames} So far, we have seen a combinatorial (non-categorical) and classically well-known framework for analysing games by decomposing them with Conway addition and synthesizing them with Grundy number. In this subsection, we will define the category of games, which will be rephrased in category-theoretic terminology in the latter part of this paper. 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. \memo{Write a sketch} Modifying such a problematic point, we define the notion of game morphism utilizing the \dq{path-lifting property}: \begin{definition}[Game morphism]\label{DefinitionGameMorphism} A \demph{game morphism} from a game $\X = (X, \rel_{\X})$ to $\Y = (Y, \rel_{\Y})$ is a function $f\colon X \to Y$ such that \begin{description} \item[Graph morphism] if $x\rel_{\X} x'$ then $f(x) \rel_{\Y} f(x')$. \label{ConditionGraphpreserving} \item[Path-lifting] if $f(x) \rel_{\Y} y$, then there exists $x' \in \X$ such that $x\rel_{\X}x'$ and $f(x')= y$. \label{conditionLocallySurjective} \end{description} \end{definition} \memo{{\cite[][Example 2.7.]{adamek2005introduction}} \begin{quote} 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} } Later, we will see that this notion of game morphisms coincides with the notion of coalgebra homomorphisms \memo{ref}, and that game morphisms preserve all \dq{recursively defined data} of games, including ending states, outcomes, Grundy numbers, and birthdays. \begin{notation}\label{NotationCategoryOfGames} The category of games and game morphisms is denoted by $\Gs$, and the canonical forgetful functor is denoted by $U \colon \Gs \to \Set$. \end{notation} \begin{remark}[Categorical properties of the category of games] How well does the category of games behave categorically? 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{itemize} \item The category of games $\Gs$ is locally finitely presentable. In particular, it has all small limits and small colimits. \item The forgetful functor $U\colon \Gs \to \Set$ is cocontinuous, but not continuous. % \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 has all small limits, all small colimits, a small generating set, a subobject classifier, epi-mono factorization, ... \memo{write} \end{itemize} \end{remark} \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 Possibly the most important game is, the terminal object of $\Gs$. This subsection aims to descrbe the terminal game. First, we recall the set-theoretic notion of hereditarily finite sets. Informally speaking, hereditarily finite sets are sets that are described by finite number of parentheses, like $\{\{\},\{\{\{\}\}\},\{\{\}\}\}$. \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 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] \end{remark} Notice that, by definition, $\Pf(\H)$ is set-theoretically equal to $\H$. Therefore, $\H$ admits the canonical $\Pf$-algebra structure \[\id_{\H}:\H \to \Pf(\H)\] and $\Pf$-coalgebra structure \[\id_{\H}:\Pf(\H) \to \H.\] \begin{proposition}\label{PropositionInitialAlgebraIsHereditarilyFiniteSets} The $\Pf$-algebra $\H$ is the initial $\Pf$-algebra. \end{proposition} \begin{proof} Since $\Pf$ preserves filtered colimits, we can utilize Adamek's construction of the initial algebra (\memo{cite}). Since the set $\H$ is the colimit of \[ \begin{tikzcd} \emptyset \ar[r]& \Pf(\emptyset) \ar[r]& \Pf(\Pf(\emptyset)) \ar[r]&\Pf(\Pf(\Pf(\emptyset))) \ar[r]&\cdots \H, \end{tikzcd} \] this completes the proof. \end{proof} \begin{definition}[Terminal game]\label{DefinitionUniversalGame} The \demph{terminal game} $\H=(\H,\to)$ is a game whose underlying set is the set of all hereditrily finite set $\H$ and whose relation $\rel$ is defined by \[A \rel B \iff B \in A.\] \end{definition} \begin{proposition}\label{PropositionUniversalIsTerminal} The terminal game $\H$ is the terminal object of $\Gs$. \end{proposition} \begin{proof} This is due to Proposition \Cref{PropositionTerminalRecursiveCoalgebra} and Proposition \Cref{PropositionInitialAlgebraIsHereditarilyFiniteSets}. % , it is enough to prove that $\H$ is the initial $T$-algebra. \end{proof} \begin{remark}[Ackerman's interpretation] There is another way to describe the terminal game, using natural numbers $\N$ instead of hereditarily finite sets $\H$. Consider a $\Pf$-algebra structure on $\N$ defined by % One canonical choice of such bijection is \[b: \Pf(\N)\to \N \colon S \mapsto \sum_{s\in S} 2^s.\] % on the set of natural numbers $\N$. It is simply a 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 $T$-algebra $(\N,b)$ is also an initial object in $\Alg{\Pf}$, and hence also gives the terminal object in $\Gs \simeq \RecCoalg{\Pf}$. This is what we called the binary exponent nim in Example \Cref{exmp:BinaryExponentNimOrTerminalGame}. \end{remark} \begin{notation} For a game $\X$, the unique game morphism to $\H$ is denoted by $\rd_{\X}\colon \X \to \H$. \end{notation} \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{remark}[Two definitions of combinatorial games]\label{RemarkTwoDefinitionsOfCombinatorialGames} \end{remark} \invmemo{"almost all states are N-state"} \invmemo{Is it related to the product-exp description of games?} \begin{example}[The universal game: Hereditarily finite sets]\label{ExampleHereditarilyFiniteSets} \memo{write the game!} \end{example} \begin{definition}[Birthday] \end{definition} \subsection{Recursively defined values are hylomorphisms} \begin{definition} A \demph{game evaluation} to a set $A$ is a family of functions \[ \{v_{\X}\colon X\to A\}_{\X=(X, \str)\text{: game}}. \] from all games to the set $A$. A game evaluation is \demph{recursively defined} if there exists a $\Pf$-algebra $\A=(A, \alpha)$ such that for any game $\X$, the function $v_{\X}$ is equal to the corresponding hylomorphism $\hylo_{\A, \X}\colon X \to A$. \end{definition} \begin{example} Grundy number $\{\G_{\X}\colon X \to \N\}$ is recursively defined by the $\Pf$-algebra $(\N, \mex\colon \Pf(\N) \to \N)$. \end{example} \begin{example} Outcome $\{X \to \{N,P\}\}$ is recursively defined by the $\Pf$-algebra $(\{N,P\}, o)$, where \[ o\colon \Pf(\{N,P\})\to \{N,P\}\colon S \mapsto \begin{cases} P &(P \notin S)\\ N &(P\in S). \end{cases} \] \end{example} \begin{remark} There is a $\Pf$-algebra homomorphism from $(\N,\mex)$ to $(\{N,P\}, o)$. This proves the proposition \memo{cite}. \end{remark} \begin{example} Birthday $\{b_{\X}\colon X \to \N\}$ is recursively defined by the $\Pf$-algebra $(\N,\xem)$ \[ \xem \colon \Pf(\N)\to \N\colon S \mapsto \min\{n \in \N\mid \text{for any }m\in S, m 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} 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{DefinitionGameMorphism}. \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{Forgetful-cofree adjunction % 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\to x'\}$ and $\{y_i\mid 1 \leq i \leq n\}=\{y'\in Y\mid y\to 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} \end{remark} \printbibliography \end{document}