\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{cleveref} \usepackage{array} \usepackage[style=alphabetic,sorting=nyt]{biblatex} \renewbibmacro{in:}{} % \addbibresource{biblio.bib} \addbibresource{CommonBiblio20240922.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);% }}} \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{\2}{\mathbf{2}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathcal{C}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \newcommand{\F}{\mathcal{F}} \newcommand{\id}{\mathrm{id}} \newcommand{\Pow}{\mathcal{P}} \newcommand{\op}{\mathrm{op}} \newcommand{\ob}{\mathrm{ob}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\FinSet}{\mathbf{FinSet}} \newcommand{\dSet}{\sigma{\text{-}}\mathbf{Set}} \newcommand{\PSh}{\mathbf{PSh}} \newcommand{\dPSh}{\sigma{\text{-}}\mathbf{PSh}} \newcommand{\Sh}{\mathbf{Sh}} \newcommand{\Top}{\mathbf{Top}} \newcommand{\preTop}{\mathbf{preTop}} \newcommand{\Int}{\mathrm{Int}} \newcommand{\res}{\mathrm{res}} \newcommand{\Cont}{\mathbf{Cont}} \newcommand{\Func}[2]{[#1,#2]} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\demph}[1]{\textbf{#1}} \font\maljapanese=dmjhira at 2.5ex \newcommand{\yo}{\textrm{\!\maljapanese\char"48}} \newcommand{\con}{\mathrm{con}} \newcommand{\Cat}{\mathbf{Cat}} \newcommand{\GoL}{\mathbf{GoL}} \renewcommand{\S}{\mathcal{S}} % \title{Geometry of Conway's game of life, (and a bit of relative topos)} % \title{What is the geometry behind Conway's game of life? \\ a first step with a relative topos} \title{A space$\rtimes$time for Conway's game of life} \author{Ryuya Hora} \thanks{Graduate School of Mathematical Sciences, University of Tokyo. \url{hora@ms.u-tokyo}} % \date{\today} \subjclass[2020]{MSC} \keywords{Keywords} \begin{document} \begin{abstract} Conway’s Game of Life is a discrete model (discrete space and discrete time) of biological behavior based on blinking points on a lattice $\Z^2$. Although the Game of Life is clearly ``geometric" in some sense (for example, one can refer to scenarios like `two gliders approaching each other'), it doesn't seem very sensible to describe its discrete and dynamic geometry in terms of topological spaces. % It's too discrete! Then, \demph{what is the intrinsic geometry within Conway’s Game of Life?} While a topological space $X$ can be regarded as a relative topos over (static) sets $\Gamma \colon \Sh(X) \to \Set$, we construct % propose to answer this question by considering % a pretopological space as a “time-evolving topological space.” From this, we construct a \demph{relative topos} over the topos of discrete dynamical systems $\gamma \colon \dPSh(\Z^2, \Int) \to \dSet$ and show that Conway’s Game of Life can naturally be regarded as an object of the topos $\dPSh(\Z^2, \Int)$. % This (mathematically trivial) result is the first step to % % These considerations represent a mathematical first step in % an author’s speculative research goal, leaving many directions for further development. The author must clarify that the mathematical contents are not very non-trivial so far. To conclude, we present several remaining questions. \end{abstract} \maketitle \tableofcontents \section{Introduction} \subsection{Why topos?} Conway’s Game of Life, which will be formally defined in \cref{def:conmap}, is a discrete model (discrete space and discrete time) of biological behavior (see \cref{fig:MovingGlider}). % based on blinking points on a lattice $\Z^2$. Although the Game of Life is clearly ``geometric" in some sense (for example, one can refer to scenarios like “two gliders approaching each other”), it doesn't seem very sensible to describe its geometry in terms of topological spaces. Our motivating question is: \begin{question}\label{thequestion} What is the intrinsic geometry within Conway’s Game of Life? \end{question} The first observation is that it has two completely different features compared to topological spaces: \begin{description} \item[Conway's game of life is discrete] We consider a countable-size lattice $\Z^2$. \item[ Conway's game of life is dynamic] We consider a time-evolution of the state $\Pow(\Z^2)\to \Pow(\Z^2)$. \end{description} Hence, we'd better consider a broader framework of topology. Our framework to consider is not topological spaces, but \demph{topos theory}, which is suitable to deal with discrete geometry. \begin{quote}{\cite[][A.Grothendieck]{grothendieck1992recoltes}} C’est le thème du topos, et non celui des schémas, qui est ce “lit”, ou cette “rivière profonde”, où viennent s’épouser la géométrie et l’algèbre, la topologie et l’arithmétique, la logique mathématique et la théorie des catégories, le monde du continu et celui des structures “discontinues” ou “discrètes”.\footnote{chatGPT translation: It is the theme of the topos, and not that of schemes, which serves as this “bed,” or this “deep river,” where geometry and algebra, topology and arithmetic, mathematical logic and category theory, the world of the continuum and that of “discontinuous” or “discrete” structures come together in union.} \end{quote} Surprisingly, the topos-theoretic framework is not only suitable to deal with discrete space but also dynamical systems: % Not only every topological space $X$ is a topos by the construction $X\mapsto \Sh(X)$, in % the topos-theoretic framework, % discrete dynamical systems also form a topos: \begin{definition}[The topos of discrete dynamical systems] A discrete dynamical system\footnote{it is also called \demph{difference sets} in \cite{tomasic2020topos}} is a pair $(X,f)$ of a set $X$ and a function $X\xrightarrow{f} X$. The category of discrete dynamical systems (and the obvious notion of morphisms) is denoted by $\dSet$\footnote{the notation is borrowed from \cite{tomasic2020topos}}. \end{definition} Since $\dSet$ is just a presheaf category $\dSet \simeq \PSh(\N)$, it is a topos (See \cref{fig:BENZU}). \begin{figure} \centering \begin{tikzpicture} \draw[thick] (0,0) circle (3.5cm) node[above right=2.5cm,align=center] {topoi}; \draw[thick] (-1,-0.5) circle (1.5cm) node[above = 1.5cm] {topological spaces\footnote{It is more accurate to say locales.}}; \node at (-1,0) [above]{$\Sh(S^1)$}; \draw[->] (-1,-0) -- (-1,-1); \node at (-1,-0.5) [right]{$\Gamma$}; \node at (-1,-1) [below]{$\Sh(1)\simeq \Set$}; \node at (2,0) [above]{$\textbf{\large ?}$}; \draw[->] (2,-0) -- (2,-1); \node at (2,-0.5) [right]{$\gamma$}; \node at (2,-1) [below]{$\dSet$}; \end{tikzpicture} \caption{topoi subsume topology and dynamics} \label{fig:BENZU} \end{figure} Our question is now: % \begin{question}[\cref{thequestion}, in terms of topoi]\label{question:topoi} % What is the \dq{correct} topos in which Conway’s Game of Life is naturally an object? % \end{question} \begin{question}[\cref{thequestion}, in terms of topoi]\label{question:topoi} In what topos does Conway’s Game of Life live? % naturally an object? \end{question} There are two trivial answers to \cref{question:topoi}: \begin{description} \item[Discrete] Conway's game of life $(\{\top, \bot\}_{(x,y)\in \Z^2})$ is an object of the topos $\prod_{(x,y)\in \Z^2} \Set$ \item[Dynamic] Conway's game of life $\Pow(\Z^2)\to \Pow(\Z^2)$ is an object of the topos $\dSet$. \end{description} These naive answers are not satisfying since $\prod_{(x,y)\in \Z^2} \Set$ misses its dynamics, and $\dSet$ misses its geometry. \subsection{Why relative topos?} This note aims to propose a better (not conclusive) answer to this question by considering a relative topos over the base topos $\dSet$. \begin{definition} A \demph{relative topos} over the base topos $\S$, is a topos $\E$ equipped with a % \memo{bounded} geometric morphism \[ \gamma \colon \E \to \S. \] \end{definition} % (\memo{Mention some history}) A Grothendieck topos is canonically a relative topos over the base topos $\Set$ by the global section geometric morphism $\Gamma \colon \E \to \Set$. For each object $X\in \E$, we have the \textbf{set} of global sections $\Gamma(X)$. Similarly, for a relative topos $\E\to \dSet$ over the base topos $\dSet$, each object $X\in \ob(E)$ has has the \demph{discrete dynamical system} of global sections $\gamma_{\ast}(X)\in \ob(\dSet)$. % This is an analog to the usual global section functor % \[ % \gamma\colon \Sh(X) \to \Set % \] % in the case of sheaf topos $\Sh(X)$ over a topological space, which is a relative topos over the base topos of (static) sets $\Set$. Therefore, the relative topos theory over $\dSet$ is a \dq{dynamical geometry}, which is extensively studied in \cite{tomasic2020topos}. With that knowledge, our final formulation of \cref{thequestion} is the following: \begin{question} What is the suitable relative topos $\E \to \dSet$ such that \begin{itemize} \item there is an object $\GoL$, called Conway's game of life, and \item its global section $\gamma_* (\GoL)$ coincides with the game of life map $\Pow(\Z^2) \to \Pow(\Z^2)$? \end{itemize} \end{question} \Cref{prop:conclusion} provides an answer to this question, (but not in a conclusive way). \section{Conway's game of life} \begin{notation} We adopt the following notations. \begin{itemize} \item Let $\2$ denote the two-element (po)set of truth values $\2 \coloneqq \{0,1\}$, which is interpreted as $0= \text{dead}$ and $1=\text{alive}$. \item For a set $X$, let $\Pow(X)$ denote the set of functions $X \to \2$, which is canonically isomorphic to the powerset of $X$. \item For an point $(x,y)\in \Z^2$, its \demph{neighbors} is the set $N_{(x,y)} \coloneqq \{(x+i,y+j) \in \Z^2 \mid i,j \in \{-1,0,1\}\} \subset \Z^2$. \end{itemize} \end{notation} We define Conway's game of life as an endofunction on $\Pow(\Z^2)$. If you don't know the intuition behind it, see \href{https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life}{[Wikipedia]}, \href{https://youtu.be/C2vgICfQawE}{[YouTube: epic conway's game of life]}, or something. There are lots of fascinating explanations online! \begin{definition}\label{def:conmap} \demph{Conway's game of life} is the function $\con \colon \Pow(\Z^2) \to \Pow(\Z^2)$ defined by \[ \con(f)(x,y) \coloneqq \begin{cases} 1 & \text{if }f(x,y)=1\text{ and } \# (N_{x,y} \cap f^{-1}(1))\in \{3,4\},\\ 1 & \text{if }f(x,y)=0\text{ and } \# (N_{x,y} \cap f^{-1}(1)) = 3, \\ 0 & \text{otherwise.} \end{cases} \] \end{definition} The glider is possibly the most famous phenomenon in Conway's game of life (see \cref{fig:MovingGlider}). \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.5] % Frame 1 \begin{scope}[shift={(0,0)}] \node at (4.5, 9.5) {\textbf{Frame 1}}; % Grid \foreach \x in {0,1,...,9} { \foreach \y in {0,1,...,9} { \draw[gray!50] (\x,\y) rectangle (\x+1,\y+1); } } % Glider \fill[black] (2,3) rectangle (3,4); \fill[black] (3,4) rectangle (4,5); \fill[black] (4,2) rectangle (5,3); \fill[black] (4,3) rectangle (5,4); \fill[black] (4,4) rectangle (5,5); \end{scope} % Frame 2 \begin{scope}[shift={(12,0)}] \node at (4.5, 9.5) {\textbf{Frame 2}}; % Grid \foreach \x in {0,1,...,9} { \foreach \y in {0,1,...,9} { \draw[gray!50] (\x,\y) rectangle (\x+1,\y+1); } } % Glider \fill[black] (3,2) rectangle (4,3); \fill[black] (3,4) rectangle (4,5); \fill[black] (4,3) rectangle (5,4); \fill[black] (4,4) rectangle (5,5); \fill[black] (5,3) rectangle (6,4); \end{scope} % Frame 3 \begin{scope}[shift={(24,0)}] \node at (4.5, 9.5) {\textbf{Frame 3}}; % Grid \foreach \x in {0,1,...,9} { \foreach \y in {0,1,...,9} { \draw[gray!50] (\x,\y) rectangle (\x+1,\y+1); } } % Glider \fill[black] (3,4) rectangle (4,5); \fill[black] (4,2) rectangle (5,3); \fill[black] (4,4) rectangle (5,5); \fill[black] (5,3) rectangle (6,4); \fill[black] (5,4) rectangle (6,5); \end{scope} % Frame 4 \begin{scope}[shift={(0,-12)}] \node at (4.5, 9.5) {\textbf{Frame 4}}; % Grid \foreach \x in {0,1,...,9} { \foreach \y in {0,1,...,9} { \draw[gray!50] (\x,\y) rectangle (\x+1,\y+1); } } % Glider \fill[black] (3,3) rectangle (4,4); \fill[black] (4,4) rectangle (5,5); \fill[black] (4,5) rectangle (5,6); \fill[black] (5,3) rectangle (6,4); \fill[black] (5,4) rectangle (6,5); \end{scope} % Frame 5 \begin{scope}[shift={(12,-12)}] \node at (4.5, 9.5) {\textbf{Frame 5}}; % Grid \foreach \x in {0,1,...,9} { \foreach \y in {0,1,...,9} { \draw[gray!50] (\x,\y) rectangle (\x+1,\y+1); } } % Glider \fill[black] (3,4) rectangle (4,5); \fill[black] (4,5) rectangle (5,6); \fill[black] (5,3) rectangle (6,4); \fill[black] (5,4) rectangle (6,5); \fill[black] (5,5) rectangle (6,6); \end{scope} % Frame 6 \begin{scope}[shift={(24,-12)}] \node at (4.5, 9.5) {\textbf{Frame 6}}; % Grid \foreach \x in {0,1,...,9} { \foreach \y in {0,1,...,9} { \draw[gray!50] (\x,\y) rectangle (\x+1,\y+1); } } % Glider \fill[black] (4,3) rectangle (5,4); \fill[black] (4,5) rectangle (5,6); \fill[black] (5,4) rectangle (6,5); \fill[black] (5,5) rectangle (6,6); \fill[black] (6,4) rectangle (7,5); \end{scope} \end{tikzpicture} \caption{Moving glider} \label{fig:MovingGlider} \end{figure} \section{Naive observations % : what is the geometry of Conway's game of life? }\label{sec:NaiveObservations} We have simply defined Conway’s Game of Life as an endofunction, ignoring its geometric structure. So, what is the geometry here? % And what if it isn’t a topological space? We want to capture two aspects: \begin{itemize} \item The rules are defined \demph{locally}, and \item The whole state changes \demph{globally}. \end{itemize} So a naive idea to capture the geometric aspect is to consider \demph{sheaves} on a space $\Z^2$ valued in $\2\coloneqq \{0,1\}$ \[ \Z^2 \supset U \to \2. \] But there is an obvious problem: there is no suitable topology on $\Z^2$. % The author does not think there is a suitable topology on $\Z^2$ so that we can capture the geometry of Conway's game of life. (For example, if $N_{(x,y)}$ is open for every $(x,y) \in \Z^2$, the space becomes discrete.) So, we consider a generalized notion of interior operator. For a subset $S\subset \Z^2$ and a ``current state" $S \to\2$, the next state \[ \Int(S)\to \2 \] is defined on a smaller subset \[ \Int(S) \coloneqq \{(x,y)\in \Z^2\mid N_{(x,y)} \subset S \} \subset S. \text{ (see \cref{fig:InteriorOfInterior})} \] \begin{figure} \centering \begin{tikzpicture}[scale=0.5] \foreach \x in {0,...,14} { \foreach \y in {0,...,14} { \draw[gray] (\x, \y) rectangle ++(1, 1); } } % Fill gray!30 cells \foreach \x/\y in { 1/13, 7/13, 10/13, 7/12, 8/12, 9/12, 5/11, 6/11, 7/11, 9/11, 10/11, 13/11, 5/10, 10/10, 11/10, 3/9, 4/9, 5/9, 10/9, 3/8, 9/8, 10/8, 11/8, 12/8, 3/7, 4/7, 7/7, 8/7, 9/7, 4/6, 5/6, 7/6, 5/5, 7/5, 8/5, 3/4, 4/4, 5/4, 6/4, 7/4, 4/3, 5/3, 6/3, 4/2, 4/1, 10/1, 11/1 } { \fill[black!30] (\x, \y) rectangle ++(1, 1); } % Fill gray!50 cells \foreach \x/\y in { 8/11, 6/10, 7/10, 8/10, 9/10, 6/9, 8/9, 9/9, 4/8, 5/8, 6/8, 7/8, 8/8, 5/7, 6/7, 6/6, 6/5 } { \fill[black!50] (\x, \y) rectangle ++(1, 1); } % Fill gray!100 cells \foreach \x/\y in { 7/9 } { \fill[black!100] (\x, \y) rectangle ++(1, 1); } \end{tikzpicture} \caption{$\Int^2 \subsetneq \Int$} \label{fig:InteriorOfInterior} \end{figure} So, we want to consider $\Int \colon \Pow(\Z^2)\to \Pow(\Z^2)$ as an ``interior operator" on the space $\Z^2$. The next section aims to formulate this idea. % But this is NOT idempotent $\Int\Int \neq \Int$. So this does not define a topological space, but defines a \demph{pretopological space}. \section{Pretopological spaces} We start by recalling that topologies can be fully recovered by the corresponding interior operator: \begin{fact}[Topology in terms of interior operator] Topologies on a set $X$ are in one-to-one correspondence with \demph{interior operators}\footnote{categorically, this data is called a lex comonad on $\Pow(X)$.}, i.e., a function $\Int \colon \Pow(X) \to \Pow(X)$ such that \begin{description} % \item[order-preserving] $S\subset T \implies \Int(S) \subset \Int(T)$ \item[lex] $\Int$ preserves finite inf. $\Int(S\cap T)=\Int(S)\cap \Int(T)$ and $\Int(X) =X$ % ($=$ binary meet and top). \item[counit] $\Int(S) \subset S$ \item[idempotent] $\Int(S) = \Int(\Int(S))$ \end{description} \end{fact} The condition \dq{lex} implies that the function $\Int$ preserves the inclusion order $S\subset T \implies \Int(S) \subset \Int (T)$. We define pretopology as a dynamic version of topology, i.e., a non-idempotent interior operator. \begin{definition} % \memo{cite: pretopology and \cite{rieser2021grothendieck}} A \demph{pretopology}\footnote{The same data, written in terms of closure operator, is called Cech closure space. See \cite{rieser2021grothendieck} for example.} on a set $X$ is a function $\Int \colon \Pow(X) \to \Pow(X)$ such that \begin{description} % \item[order-preserving] $S\subset T \implies \Int(S) \subset \Int(T)$ \item[lex] $\Int$ preserves finite inf. $\Int(S\cap T)=\Int(S)\cap \Int(T)$ and $\Int(X) =X$ % ($=$ binary meet and top). \item[counit] $\Int(S) \subset S$ \end{description} A \demph{pretopological space} is a set $X$ equipped with a pretopology. \end{definition} (This is a lex pointed endofunctor on $\Pow(X)$.) \begin{example} Every topological space is a pretopological space. \end{example} \begin{example}[Graph] For a directed graph $(V, E \subset V^2)$, the function $\Int \colon \Pow(V) \to \Pow(V)$ defined by \[ \Int(S) \coloneqq \{v\in S\mid v\to v' \implies v' \in S\}. \] is a pretopology. If it is reflexive, i.e., $\{(v,v)\mid v\in V\} \subset E$, the graph structure is reconstructed by the induced pretopology, since $v\to v' \iff v\notin \Int(V\setminus \{v'\})$. % A \demph{non-reflexive directed graph} is a pair $(V,E)$ of the set of vertices and the set of edges $E\subset V^2$ that satisifies the non-reflexivity $E\cap \{(v,v)\mid v\in V\}= \emptyset$. \end{example} \begin{example} The pair $(\Z^2, \Int)$ in \cref{sec:NaiveObservations} is a pretopological space induced by the following graph (Figure \ref{fig:Graph}). \end{example} \begin{figure} \centering \begin{tikzpicture}[scale=1.0] \def\size{3} \def\extend{0.5} \foreach \x in {-1,0,...,\size} { \foreach \y in {-1,0,...,\size} { \fill (\x, \y) circle (5pt); \foreach \dx/\dy in {1/0, 0/1, -1/0, 0/-1, 1/1, 1/-1, -1/1, -1/-1} { \draw[thick] (\x, \y) -- ++(\dx, \dy); } } } \node[anchor=east] at (-2, 1) {\Huge $\cdots$}; \node[anchor=west] at (4, 1) {\Huge $\cdots$}; \node[anchor=north] at (1, -2) {\Huge $\vdots$}; \node[anchor=south] at (1, 4) {\Huge $\vdots$}; \end{tikzpicture} \caption{The graph on Conway's game of life} \label{fig:Graph} \end{figure} As a slogan, \demph{pretopological spaces are a dynamical version of topological space}, so that topological spaces coincide with ``static" (i.e., $\Int\Int=\Int$) pretopological spaces. \section{Dynamical presheaf topos on a pretopological space} \begin{definition} A \demph{dynamical presheaf}\footnote{This name might be confusing when the pretopological space is a topological space, since this does not coincide with the usual notion of presheaves.} on a pretopological space $(X, \Int)$ is a presheaf ($=$ functor) \[ F\colon \Pow(X)^{\op} \to \Set \] equipped with a family of operators \[ \{\sigma_S \colon F(S) \to F(\Int(S))\}_{S\in \Pow(X)} \] such that \[ \begin{tikzcd} F(S)\ar[d,"\res"]\ar[r,"\sigma_S"]&F(\Int(S))\ar[d,"\res"]\\ F(T)\ar[r,"\sigma_T"]&F(\Int(T)) \end{tikzcd} \] commutes. The category of dynamical presheaves is denoted by $\dPSh(X, \Int)$. \end{definition} % \begin{definition}(Game of life, as an presheaf) % \demph{Conway's game of life} is the object $\GoL$ of the presheaf topos $\dPSh(\Z^2, \Int)$, defined to be a functor $\GoL\colon \Pow(\Z^2)^{\op}\to \Set$ % \[ % \GoL(S) \coloneqq \Pow(S) % \] % equipped with the conway's game of life map (\cref{def:conmap}) % \[ % \con \colon \GoL(S) \to \GoL(\Int(S))) % \] % \end{definition} \begin{example}[Game of life, as a dynamical presheaf] % Conway's game of life is a dynamical presheaf on the pretopological space $(\Z^2, \Int)$. \demph{Conway's game of life}, denoted by $\GoL$, is a dynamical presheaf on the pretopological space $(\Z^2, \Int)$, defined to be a functor $\GoL\colon \Pow(\Z^2)^{\op}\to \Set$ \[ \GoL(S) \coloneqq \Pow(S) \] equipped with the restriction of conway's game of life map $\con\colon \Pow(S) \to \Pow(\Int(S))$(\cref{def:conmap}). \end{example} Note that a pretopological space $(X, \Int)$ can be regarded as a functor \[ \N \to \Cat \] that sends the unique object $\ast\in \ob(\N)$ to $\Pow(X)\in \ob(\Cat)$ and $1\colon \ast \to \ast$ to the interior operator $\Int \colon \Pow(X) \to \Pow(X)$\footnote{Here, we only use the condition that $\Int$ preserves the inclusion order.}. \begin{definition} For a pretopological space $(X, \Int)$ % a set $X$ and an order-preserving map $\Int \colon \Pow(X) \to \Pow(X)$, we define the category $\Pow(X)\rtimes_{\Int} \N$\footnote{Some textbooks in topos theory, including \cite{johnstone2002sketchesv2} refers to this category by the opposite notation ($\N \rtimes \Pow(X)$, which I don't understand the reason.)} to be the Grothendieck construction of the functor $\N \to \Cat$ described above. % \[ % \N \to \Cat. % \] More concretely, in the category $\Pow(X)\rtimes_{\Int} \N$, \begin{description} \item[object] object is a subset of $X$ \item[morphism] morphism from $U$ to $V$ is a natural number $n\in \N$ such that $U \subset \Int^n (V)$ \item[composition] the composite of $U \xrightarrow{n}V \xrightarrow{m}W$ is $U \xrightarrow{n+m}W$. \end{description} \end{definition} \begin{proposition}[Dynamical presheaf is a presheaf]\label{prop:DynamicalPresheafisAPresheaf} For any pretopological space\footnote{Pretopology is too strong to prove this proposition. It is enough to assume that $\Int$ preserves the inclusion order.}, we have the following equivalence of categories: \[ \dPSh(X, \Int) \simeq \PSh(\Pow(X)\rtimes_{\Int} \N) \] \end{proposition} \begin{proof} We define a category $C(X, \Int)$ by \begin{description} \item[objects] subsets of $X$, \item[morphism $U\xrightarrow{\subset} V$] if $U\subset V$, \item[morphism $\Int(U)\xrightarrow{1} U$] for any $U\in \Pow(X)$, \item[relations] $U_1\xrightarrow{\subset}U_2\xrightarrow{\subset}\cdots \xrightarrow{\subset}U_n = U_1\xrightarrow{\subset}U_n$ for any $n\geq 1$,and \item[relations] $\Int(U) \xrightarrow{1}U \xrightarrow{\subset} V = \Int(U) \xrightarrow{\subset} \Int(V) \xrightarrow{1} V$ for any $U\subset V$. \end{description} Since $\PSh(C(X, \Int)) \simeq \dPSh(X,\Int)$, it is enough to prove $C(X, \Int) \cong \Pow(X)\rtimes_{\Int} \N$. Every morphism $U \to V$ can be shown to be equal to a morphism of the form of \[ U \xrightarrow{\subset} \Int^n(V) \xrightarrow{1}\Int^{n-1}(V) \xrightarrow{1} \cdots \xrightarrow{1} \Int(V) \xrightarrow{1} V. \] This completes the proof. \end{proof} \begin{corollary} The category $\dPSh(\Z^2, \Int)$ is a presheaf topos, in which Conway's game of life $\GoL$ is an object. \end{corollary} \section{As a relative topos over the topos of discrete dynamical systems} % \cite[][lemma C.2.5.3]{johnstone2002sketchesv2} % \cite[][Section 13]{tomasic2020topos} All of the contents in this section is just an example of a general theory of relative topoi. \begin{proposition}[Special case of {\cite[][part 13.13]{tomasic2020topos}}] A pretopological space $(X,\Int)$ defines an internal poset in the topos of discrete dynamical systems $\dSet$. \end{proposition} \begin{proof} The object of objects is $\Pow(X)$ equipped with the endofunction $\Int$. Since $\Int$ preserves the order, the object of morphisms $\{(U,V)\mid U\subset V\}\subset \Pow(X)^2$ is also an object of $\dSet$. It is obvious that all the related maps, namely $\mathrm{dom},\mathrm{cod},\mathrm{id}$, are morphisms in $\dSet$, and they satisfy the equations for being an internal category. \end{proof} \begin{theorem}[{Special case of \cite[][lemma C.2.5.3]{johnstone2002sketchesv2} or \cite[][Section 13]{tomasic2020topos}}] A dynamical presheaf is precisely an internal presheaf of $\Pow(X)$ in the topos $\dSet \coloneqq \PSh(\N)$. \[ \dPSh(X, \Int) \simeq \PSh_{\dSet}(\Pow(X), \Int) \] In particular, the category of dynamical presheaves $\dPSh(X)$ is a relative topos over the base topos $\dSet$. \end{theorem} \begin{proof} Due to \cref{prop:DynamicalPresheafisAPresheaf}, this is a special case of \cite[][lemma C.2.5.3]{johnstone2002sketchesv2} or \cite[][Section 13]{tomasic2020topos}. The concrete calculation according to the definition of internal presheaves (see, for example, \cite{maclane1994sheaves}) is not hard. \end{proof} \begin{lemma}\label{lem:adjoint}For a pretopological space $(X, \Int)$, let $\pi\colon \Pow(X)\rtimes_{\Int} \N \to \N$ be the projection functor, which sends $U\xrightarrow{n} V$ to $\ast \xrightarrow{n} \ast$. Then $\pi$ admits both left adjoint and right adjoint. \end{lemma} \begin{proof} The fully faithful embedding $\iota_{\emptyset}\colon \N \to \Pow(X)\colon \ast \mapsto \emptyset$ is the left adjoint, and another fully faithful embedding $\iota_{X}\colon \N \to \Pow(X)\colon \ast \mapsto X$ is the right adjoint. \end{proof} \begin{proposition}\label{prop:conclusion} There is an adjoint quintuple \[ \begin{tikzcd}[column sep =100 pt] \dPSh(X,\Int) \ar[r, "\gamma_! = \mathrm{ev}_{\emptyset}", shift left=20pt] \ar[r, "\gamma_* = \mathrm{ev}_{X}", shift right=20pt, thick]& \dSet \ar[l, "\gamma^* = {-}\circ \pi"', thick] \ar[l, shift right =40pt, "\mathrm{Lan}_{\iota_{\emptyset}}"'] \ar[l, shift left =40pt, "\mathrm{Ran}_{\iota_{X}}"']. \end{tikzcd} \] Furthermore, the discrete dynamical system of global sections of $\GoL$, which is defined to be $\gamma_* (\GoL)$ is isomorphic to Conway's game of life $\con \colon \Pow(\Z^2) \to \Pow(\Z^2)$ (\cref{def:conmap}). \end{proposition} \begin{proof} The existence of the adjoint quintuple is an immediate corollary of \cref{lem:adjoint}. Since the global section functor $\gamma_{\ast}$ is just the evaluation functor at $\Z^2$, the latter statement follows. \end{proof} \begin{remark}[Adjoint quintuple is superficial] As we will mention in \cref{todo:subtopoi}, what we should consider is not $\dPSh(\Z^2, \Int)$ itself, but some subtopos of $\dPSh(\Z^2, \Int)$. % For the better subtopos In the sense that this adjoint quintuple would not exist for the ``better subtopos," I do not consider the existence of the adjoint quintuple to be an essential property of the Conway Game of Life. \end{remark} \section{Remaining questions: This is not the goal!} % \para{The author's goal} % The author's motivation is strongly related to the book \textit{Selfish gene} \cite{dawkins1976selfish}, which was one of the direct reasons to major in topos theory. There is an clear mathematical structure, but to the author's knowledge, \begin{remark}[Speculative and personal motivation] The author's original motivation is closely related to Richard Dawkins' ``Selfish Gene" \cite{dawkins1976selfish}. Explaining how it could be related is neither the purpose of this text nor within the author's capacity. (If I need to try to articulate a little, for example, I'm interested in how we can mathematically state ``A glider is moving".) What can be stated clearly is that this book is undoubtedly one of the reasons why I chose to study topos theory. Moreover, understanding the abstract phenomena described in the book—phenomena that are mathematical in nature but not written in mathematical terms—has been a strong source of my passion for mathematics. \end{remark} Besides this \dq{ultimate goal,} we list several mathematical questions that still remain. \para{1. Subquotiet of \texorpdfstring{$\dPSh(\Z^2, \Int)$}{dPSh}} Is the topos $\dPSh(\Z^2, \Int)$ the \dq{best} topos containing Conway's game of life in some sense? % Although the question itself is too ambiguous, I would say NO! First and foremost, this topos is just a presheaf topos, and we don't consider any sheaf conditions. \begin{todo}[Subtopos]\label{todo:subtopoi} Define a nice Grothendieck topology on the category $\Pow(X)\rtimes_{\Int} \N$ (or its modified version) so that \begin{itemize} \item $\Pow_{\text{fin}}(\Z^2) \subset \Pow(\Z^2)$ is dense, and \item $\GoL$ is naturally a sheaf. \end{itemize} \end{todo} In other words, we need to take an appropriate \demph{subtopos} of the topos $\dPSh(\Z^2, \Int)$ or define an internal site in $\dSet$. (\cite{rieser2021grothendieck} might have done a similar thing already, but the author could not read it\footnote{Since the author could not find a rigorous definition of $\mathcal{L}(X,c)$ in the literature. The author guesses that the topos in the article is localic and hence is not equivalent to $\dPSh(\Z^2,\Int)$.}.) Possibly, the first step is to consider the apparent essential subtopos (= level) $\PSh(\Pow_{\text{fin}}(\Z^2)\rtimes_{\Int} \N)$, which satisfies the above two conditions. Secondly, we have ignored all symmetries that $\dPSh(\Z^2, \Int)$ possesses. For example, the group $\Z^2\rtimes D_4$ acts on the infinite graph (\cref{fig:Graph}). This action lifts to an action on $\dPSh(\Z^2, \Int)$. \begin{todo}[Quotient toposes] We need to quotient the topos $\dPSh(\Z^2, \Int)$ (or its subtopos) by its symmetries (like the action of $\Z^2\rtimes D_4)$. \end{todo} \para{2. Modal logic} Another motivation to consider the graph (\cref{fig:Graph}) is the implicit modal logic behind \demph{minesweeper}, inspired by a discussion with Sekiyama. While a topology $\Int \colon \Pow(X) \to \Pow(X)$ is a reflexive and transitive relation, which provides a semantics for S4 logic, I wonder the semantics by pretopology $\Int \colon \Pow(X) \to \Pow(X)$ for T logic is in some sense, captured by the topos $\dPSh(\Z^2, \Int)$. The author does not know the answer due to the lack of knowledge in this field. (\cite{awodey2014topos} might help?) % \para{generalities: comparisons} \para{3. Real analogy} Though we have considered the discrete dynamical systems, we can do the same thing for $\R_{\geq 0}$ (not for $\N$). The resulting topos $\PSh(\Pow(X)\rtimes \R_{\geq 0})$ might be of interest in the relationship with persistent homology (see \cite{rieser2021vcech}) or the solution space sheaf of the wave equation. \para{4. Doctrinal point of view} % (See \cite{tomasic2020topos, connes2017geometry, johnstone2002sketchesv1}.) The functor $\N \to \Cat$ corresponding to a pretopological space $(X, \Int)$ factors through the category of meet semilattices \[ \N \to \mathbf{MSLattice} \to \Cat. \] This implies that the construction of $\dPSh(X, \Int)$ is an example of classifying topos of primary doctrine \cite{wrigley2024doctrinal}, except that $\N$ is not cartesian. \para{5. topoi of systems} The author situates the topos $\dPSh(\Z^2, \Int)$ within what he calls the \demph{topoi of systems.} Other examples include the topos of discrete dynamical systems $\dSet$, the topos of time evoluting set $\Sh(\N, \leq)$, the topos of word actions $\Sigma{-}\Set$, or the topos of automata $\mathbf{Atmt}$ (see \cite{hora2024topoi}). They share a lot of properties. For example, they are \'{e}tendue, and they are naturally relative topoi over $\dSet$. What's interesting about such topoi of systems, is the notion of point, which serves as an "observation point of view on the systems". So our question is: what is the category of points of $\dPSh(\Z^2, \Int)$ (or, more interestingly, of its suitable subtopos)? % \begin{itemize} % % \item Sekiyama's dynamical modal logic on minesweeper % % \item Conway's game of life % % \item Selfish gene % % \item \cite{rieser2021grothendieck} % % \item Quotient by the action of $\Z^2 \rtimes D_4$ % % \item Persistent homology and $\Pow(M)\rtimes \R_{\geq 0}$. % \end{itemize} % \appendix % \section{topos theory} % For a small category $\C$, $\PSh(\C)$ denotes its presheaf category, defined by $\PSh(\C) \coloneqq [\C^\op, \Set]$ % \begin{definition} % A category $\E$ is a \demph{(Grothendieck) topos}, if there exists % \begin{itemize} % \item a small category $\C$, % \item a fully faithful functor $\iota\colon \E \hookrightarrow \PSh(C)$, and % \item a finite limit preserving left adjoint $L \dashv \iota$. % \end{itemize} % \end{definition} % To read this note, it suffices to know presheaf topoi. % \begin{proposition} % For a small category $\C$, its presheaf category $\PSh(\C)$ is a topos. % \end{proposition} % \begin{proof} % You can take $L,\iota$ as $\id_{\PSh(\C)}$. % \end{proof} % \begin{example} % For a topological space $X$, its category of sheaves $\Sh(X)$ is a topos,due to the sheafification functor $L \colon \PSh(\mathcal{O}(X))\to \Sh(X)$. % \end{example} \para{Acknowledgement} % I woul % Baez, Sekiyama, This article was written for the \href{https://adventar.org/calendars/10265}{[Category Theory Advent Calendar 2024].} I am grateful to Yuto Kawase for providing this opportunity. All pictures in this text are written by chatGPT 4o. \printbibliography \end{document}