← species-generating-functions
shortmain.tex
\documentclass[dvipdfmx,14pt,notheorems]{beamer}
\usepackage{array}
\usepackage{eqparbox}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usepackage{tikz-cd}
\usepackage{amsthm}
\usepackage{amsmath,amssymb}
\usepackage{mathrsfs}
\usepackage{graphics}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{array,booktabs,float}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usepackage{url}
\usepackage{mathtools}
\usepackage{color}
\usepackage{txfonts}
\graphicspath{ {images/} }
%\usepackage{luatexja-fontspec}
%\setmainjfont{MS Mincho}
\usepackage[utf8]{inputenc}
\usepackage{newunicodechar}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Triv}{\mathrm{Triv}}
\newcommand{\INE}{\mathrm{IsNonEmpty}}
\newcommand{\IE}{\mathrm{IsEmpty}}
\newcommand{\IS}{\mathrm{IsSingleton}}
\newcommand{\BT}{\mathrm{BiTree}}
\newcommand{\IsOdd}{\mathrm{IsOdd}}
\newcommand{\IsEven}{\mathrm{IsEven}}
\newcommand{\PPer}{\mathrm{PPer}}
\newcommand{\Per}{\mathrm{Per}}
\newcommand{\Cycle}{\mathrm{Cycle}}
\newcommand{\SubSet}{\mathrm{SubSet}}
\newcommand{\Arr}{\mathrm{Arr}}
\newcommand{\Equiv}{\mathrm{Equiv}}
\newcommand{\hsp}{\hspace{10pt}}
\newcommand{\gf}{F}
\definecolor{ccomb} {RGB}{254, 102, 0}
\definecolor{cfunc} {RGB}{ 0, 0, 255}
\newcommand{\comb}[1]{\textcolor{ccomb}{#1}}
\newcommand{\func}[1]{\textcolor{cfunc}{#1}}
\newcommand{\dq}[1]{``{#1}''}
\newcommand{\innt}{\int \hspace{-5pt}}
\newcommand\blfootnote[1]{%
\begingroup
\renewcommand\thefootnote{}\footnote{#1}%
\addtocounter{footnote}{-1}%
\endgroup
}
\newcommand{\memo}[1]{\blfootnote{memo: #1}}
\makeatletter
\newcounter{eqtabular}
\newsavebox\eqtabularbox
\newcolumntype{C}{>{\begin{lrbox}{\eqtabularbox}}c<{\end{lrbox}%
\eqmakebox [\the\c@eqtabular @eqtabular]%
{\unhcopy\eqtabularbox}}}
\newcolumntype{R}{>{\begin{lrbox}{\eqtabularbox}}c<{\end{lrbox}%
\eqmakebox [\the\c@eqtabular @eqtabular][r]%
{\unhcopy\eqtabularbox}}}
\newenvironment{eqtabular}[2][c]
{%
\stepcounter{eqtabular}%
\tabular[#1]{#2}%
}
{%
\endtabular
}
\makeatother
\usepackage{bxdpx-beamer}
\usepackage{pxjahyper}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\tikzset{>={Latex[width=3mm,length=3mm]}}
\usetheme{Darmstadt}
\usecolortheme{seahorse}
\setbeamertemplate{items}[default]
\setbeamertemplate{navigation symbols}{}
\AtBeginSection[]
{
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
\title{圏論と組合せゲーム理論}
\author{洞龍弥}
\institute[]{東京大学数理科学研究科修士2年}
\date[2023年8月21日]{2023年8月21日\\ 第7回日本組合せゲーム理論研究集会}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
\begin{frame} \frametitle{圏論と組合せゲーム理論}
\begin{tikzpicture}[scale = 1.4]
\foreach \x in {0,5}
{
\draw[thick] (0+\x,0)--(3+\x,0)--(3+\x,3)--(0+\x,3)--cycle;
\draw[thick] (0+\x,0)--(3+\x,0)--(3+\x,3)--(0+\x,3)--cycle;
}
\draw (1.5,1.5) node{圏論};
\draw (1.5+5,1.5) node{組合せゲーム理論};
\pause
\foreach \y in {0,1, 2}
{
\draw[thick,->] (3.2,{1*(0.5+\y)})--(4.8,{1*(0.5+\y)});
\draw (4,2) node{興味};
\draw (4,1) node{関心};
% \draw (4,{0.5*(1+\y)}) node{$\varheartsuit$};
}
\end{tikzpicture}
% \pause
% \begin{center}
% 圏論で組合せゲームがなぜ注目されてきたのか
% \end{center}
\end{frame}
% \begin{frame} \frametitle{裏タイトル}
% 圏論からのラブレター
% \end{frame}
\input{TTIOS}
% \begin{frame} \frametitle{目的}
% 三つのことを伝える:
% \begin{itemize}
% \setlength{\itemsep}{15pt}
% \item 圏論から見て組合せゲーム理論が魅力的かつ強力なこと
% \item 圏論が組合せゲーム理論と他の数理科学を繋ぎ得ること
% \item これらを可能にする数学的構造:\\ \dq{Symmetric Monoidal Closed Category}
% \end{itemize}
% \end{frame}
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents
\end{frame}
\section{数学的でない事例}
\begin{frame} \frametitle{数学的でない事例}
% まずは，何が起こっているか事例を紹介する．
まずは，圏論界隈で組合せゲーム理論が実際に議論されている様を，\textbf{数学的でない事例}を用いて伝える．
\end{frame}
\begin{frame} \frametitle{事例: 研究集会にて}
\begin{columns}
\begin{column}{0.5\textwidth}
圏論の研究集会
\vspace{20pt}
\begin{itemize}
\setlength{\itemsep}{15pt}
\item Category Theory 2023
\item CSCAT 2023
\end{itemize}
\end{column}
\begin{column}{0.6\textwidth}
\includegraphics[width = \textwidth]{images/Mex.jpeg}
\end{column}
\end{columns}
\end{frame}
\begin{frame} \frametitle{事例: 研究室にて}
以下の人々が研究の文脈でConway Gameの議論をしていた
\begin{itemize}
\setlength{\itemsep}{8pt}
\item 指導教官(プログラミング言語の圏論的意味論)
\item 研究室の先輩(数学の基礎付け HoTT)
\item RIMS CS
\end{itemize}
\pause
\begin{block}{参考文献{\footnotesize (A. Blass. 1992)}}
A game semantics for linear logic
% {\footnotesize Annals of Pure and Applied logic 56.1-3 (1992): 183-220.}
\end{block}
% \begin{block}{記念碑的論文}
% A game semantics for linear logic (A. Blass)\\
% {\footnotesize Annals of Pure and Applied logic 56.1-3 (1992): 183-220.}
% \end{block}
\end{frame}
\begin{frame} \frametitle{事例: Quantum Gravity Seminar 2006}
\begin{center}
\includegraphics[scale = 0.1]{images/Baez.jpeg}
\end{center}
% \begin{columns}
% \begin{column}{0.3\textwidth}
% \end{column}
% \begin{column}{0.3\textwidth}
% \end{column}
% \begin{column}{0.3\textwidth}
% 4
% \end{column}
% \end{columns}
\pause
\begin{block}{Proposition (Intro by Dolan)}
\[
\begin{cases}
\text{この値が}0 &\iff \text{先手必勝}\\
\text{この値が}1 &\iff \text{後手必勝}
\end{cases}
\]
\end{block}
\end{frame}
\section{交流者としての組合せゲーム}
\include{TTIOS}
\begin{frame} \frametitle{交流者としての組合せゲーム}
ゲームの圏は圏論的振る舞いが格別に良いため，他の数(理科)学との相互翻訳が可能！
{\centering
\includegraphics[width=1\textwidth]{images/summarizeSMCC.jpeg}
}
\end{frame}
% \begin{frame} \frametitle{圏論的架橋}
% \begin{enumerate}
% \setlength{\itemsep}{13pt}
% \item Symmetric Monoidal Closed Categories
% \item Compact Closed Categories
% \item (free) Cartesian Closed Categories
% \item Categorical Semantics
% \item Differential Categories
% \item Coalgebras
% \end{enumerate}
% \end{frame}
\begin{frame} \frametitle{Symmetric Monoidal Closed Categories}
\begin{columns}
\begin{column}{0.8\textwidth}
\begin{block}{Informal Definition: SMCC}
Symmetric Monoidal Closed Categoryとは，圏(対象と射)とテンソル積 $X\otimes Y$と内部Hom $X\multimap Y$からなる構造である．
\end{block}
\begin{table}[]
\footnotesize
\begin{tabular}{|l|l|l|}
\hline
圏論 & 線型代数 & 組合せゲーム理論 \\ \hline
対象 $X$ & 線型空間 $X$ & Conway \textbf{ゲーム} $X$ \\ \hline
射 $f\colon X\to Y$ & 線型写像 $f$ & $-X+Y$の後手\textbf{必勝戦略} \\ \hline
テンソル積$\otimes$ & $X\otimes Y$ & ゲームのConway \textbf{和} \\ \hline
内部Hom $\multimap$ & $\mathrm{Hom}(X,Y)$ & -X+Y \\ \hline
\end{tabular}
\end{table}
\end{column}
\begin{column}{0.2\textwidth}
\includegraphics[scale=0.06]{images/SMCC.jpeg}
\end{column}
\end{columns}
\end{frame}
\begin{frame} \frametitle{Symmetric Monoidal Closed Categories}
\begin{block}{参考文献 {\footnotesize(J. C. Baez, M. Stay. 2009)}}
Physics, Topology, Logic and Computation: A Rosetta Stone
\end{block}
\begin{table}[]
\footnotesize
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
圏論 & 物理 & topology & 論理 & 計算 & 線型代数 & ゲーム \\ \hline
対象 & Hilb.sp. & 多様体 & 命題 & 型 & 線型空間 & ゲーム \\ \hline
射 & 演算子 & cob. & 証明 & program & 線型写像 & 必勝戦略 \\ \hline
$\otimes$ & Joint sys. & 並列 & 論理積 & 積の型 & $V\otimes W$ & ゲームの和 \\ \hline
$\multimap$ & (口頭)& (口頭) & $P\to Q$ & 関数型 & Hom & -A+B \\ \hline
\end{tabular}
\end{table}
\pause
他の行の例:
\begin{itemize}
\item $X\to X\otimes X$(の非存在)
\item $X\otimes (X\multimap Y)\to Y$
\end{itemize}
% $\mathrm{id}_{X}$，$\Delta_{X}$(の非存在)
% ，$\chi(X)$，不動点定理，
% 他の列: Sheaf, Vect.bund., 複体，範疇文法，\dq{資源理論}
\end{frame}
% \begin{frame} \frametitle{Compact Cosed Categories}
% \begin{block}{ゲームの圏を有名にした論文}
% Remarques sur la Th\'eorie des Jeux \`a deux personnes
% {\footnotesize(1977, Andr\'e Joyal)}
% \end{block}
% \end{frame}
\begin{frame} \frametitle{Compact Closed Categories}
\begin{columns}
\begin{column}{0.8\textwidth}
\begin{block}{Informal Definition:\\ Compact Closed Category}
Compact Closed Categoryとは，各対象$X$が双対対象$X^{\ast}$をもつような特別なSMCCである.
\end{block}
\begin{table}[]
\footnotesize
\begin{tabular}{|l|l|l|}
\hline
圏論 & 線型代数 & 組合せゲーム理論 \\ \hline
対象 $X$ & \textbf{有限次}線型空間 $X$ & Conway \textbf{ゲーム} $X$ \\ \hline
射 $f\colon X\to Y$ & 線型写像 $f$ & \textbf{必勝戦略} \\ \hline
テンソル積$\otimes$ & $X\otimes Y$ & ゲームのConway \textbf{和} \\ \hline
内部Hom $\multimap$ & $\mathrm{Hom}(X,Y)$ & -X+Y \\ \hline
双対対象 $X^{\ast}$ & $X^{\ast}$ & -X \\ \hline
\end{tabular}
\end{table}
\end{column}
\begin{column}{0.2\textwidth}
\includegraphics[scale=0.06]{images/ccc.jpeg}
\end{column}
\end{columns}
\end{frame}
\begin{frame} \frametitle{Compact Closed Categories}
\begin{block}{参考文献 {\footnotesize(A. Joyal. 1977)}}
Remarques sur la Th\'eorie des Jeux \`a deux personnes
% {\footnotesize(1977, Andr\'e Joyal)}
\end{block}
% \vspace{15pt}
% 他の例:vector bundles, chain complexes, cobordisms(\dq{topology}), an ordered abelian group(潰れた姿)
% \vspace{15pt}
共通構造の例:
\begin{itemize}
\setlength{\itemsep}{8pt}
\item 対象$X$のEuler characteristic $\chi(X)$
\item 射のトレース$\mathrm{Tr}(f)$
\item Grothendieck群
\item 不動点定理
\item (表現論)
\end{itemize}
% $X\multimap Y = X^{\ast}\otimes Y$，
\end{frame}
\section{道具としての組合せゲーム}
\include{TTIOS}
\begin{frame} \frametitle{Cartesian Closed Category}
Game description of the free CCC.
{\centering
\includegraphics[width=\textwidth]{images/CCCTri3.jpeg}
}
% \memo{Frobenius algebras}
\end{frame}
\begin{frame} \frametitle{Game Semantics (ゲーム意味論)}
論理学で論理体系を設計したとき，何が示せて何が示せないかを知りたい．
\begin{itemize}
\item 何が示せるか $\to$ 示せばいい．
\item 何が示せないか $\to$
\pause\textbf{意味論}を見る．
\end{itemize}
\pause
命題や証明に数学的対象を割り振り，論理体系の性質と数学的対象の性質を結びつける．
{
\centering
\includegraphics[width= \textwidth]{images/OpenSemantics.jpeg}
}
\end{frame}
\begin{frame} \frametitle{Game Semantics (ゲーム意味論)}
Linear Logicと呼ばれる論理体系の意味論としてゲーム(の為す圏)が有用であることがわかった．
\hspace{20pt}
\begin{block}{参考文献{\footnotesize (A. Blass. 1992)}}
A game semantics for linear logic
% {\footnotesize Annals of Pure and Applied logic 56.1-3 (1992): 183-220.}
\end{block}
\hspace{20pt}
400件以上引用され，現在も活発に研究されている．
% \memo{Rust, Quantum}
\end{frame}
\section{目的としての組合せゲーム}
\include{TTIOS}
\begin{frame} \frametitle{目的としての組合せゲーム}
これまで，(私の知る限りは)組合せゲーム界に聞こえるような貢献をこれまで圏論はそこまで果たしていない．
\vspace{20pt}
これから，現代的な圏論が貢献する可能性を感じている．
\end{frame}
\begin{frame} \frametitle{微分構造}
\begin{block}{Rota-Baxter equation ($\lambda=0$)}
% 環$A$上のRota-Baxter operator とは
\[R(x)R(y)=R(R(x)y+xR(y))\]
% を満たす$A$加群準同型 $R\colon A\to A$．
\end{block}
\vspace{15pt}
例:積分版ライプニッツ則
\[\textstyle\int\hspace{-5pt} f\cdot\int\hspace{-5pt} g =\int\left(\hspace{2pt} \int\hspace{-5pt} f \cdot g + f \cdot\hspace{-3pt}\int\hspace{-5pt} g\hspace{2pt}\right)\]
\pause
% \vspace{0pt}
\begin{block}{ニム和の再帰的定義式}
$\mathrm{mex}(S)\oplus \mathrm{mex}(T) = \mathrm{mex}(\mathrm{mex}{S}\oplus T \cup S\oplus \mathrm{mex}{T})$
\end{block}
\end{frame}
\begin{frame} \frametitle{微分構造}
ゲームの和もライプニッツ則に似ているが，未発展．
\begin{block}{参考文献 {\footnotesize (J. Laird, M. Giulio, and M. Guy. 2013)}}
Constructing differential categories and deconstructing categories of games
\end{block}
個人的には，組合せゲームの母関数理論の存在を期待している．
\begin{block}{参考文献{\footnotesize (F. Loregian, T. Trimble. 2021)}}
Differential 2-rigs
\end{block}
\end{frame}
\begin{frame} \frametitle{Coalgebras}
\begin{block}{Informal Definition: Coalgebra}
% 圏$C$とその自己関手$T\colon C \to C$について，その
Coalgebraとは対象$X$からその\dq{変形}$TX$への射$X\to TX$のこと．
\end{block}
\vspace{15pt}
例: $X \to P(X)$は集合$X$上の二項関係のこと．
\vspace{15pt}
Coalgebraは計算機科学などで，(オートマトンなどの)システムを定式化し振る舞いを解析するのに用いられてきた．
% \begin{block}{参考文献{\footnotesize (B. Jacobs. 2012)}}
% Introduction to Coalgebra. Towards Mathematics of States and Observations (本)
% \end{block}
\end{frame}
\begin{frame} \frametitle{Coalgebras}
Coalgebraは組合せゲームの拡張(停止性無し)に用いられた．
\begin{block}{参考文献{\footnotesize (F. Honsell, M. Lenisa. 2011)}}
Conway Games, algebraically and coalgebraically
\end{block}
私は，well-founded coalgebraという，再帰計算と深く関わるcoalgebraを用いて組合せゲーム(停止性有り)を調べている．
\begin{block}{参考文献{\footnotesize (J. Ad\'amek, S. Milius, L. S. Moss. 2020)}}
On Well-Founded and Recursive Coalgebras
\end{block}
\end{frame}
\begin{frame} \frametitle{Coalgebras}
個人的に示したこと:
\vspace{10pt}
\begin{itemize}
\item 不偏ゲームのwell-founded coalgebraを用いた定式化
\item ゲームの各種の量(Grundy数, 誕生日など)を\textbf{Hylomorphism}として導出 \\ \dq{Grundy数 $\vdash$ 一山ニム $\vdash$ 誕生日}
\item Conway additionがSymmetric Monoidal Categoryとしての構造を定めること
\item これらからNim和が導出されること
\end{itemize}
\end{frame}
% \section{個人の研究}
\section{まとめ}
\include{TTIOS}
\begin{frame} \frametitle{個人的に今後調べたいこと}
\begin{itemize}
\item \textbf{指数つき半環}との関係 ($x+x^x$はどんなゲーム?)
\item Nim和が何者なのか
\item Conway additionの特徴付け
\item Coalgebraic な SMCC構造
\item Nim和のLSCとしての導出
\item Differential Structureと母関数の理論
\item 他のスタイルのゲームを統一するcoalgebraicな枠組みを作り，各種ゲーム間の概念を交流させる
\item ゲームの線型表現
\item topos of games
\end{itemize}
\end{frame}
\end{document}
\begin{frame} \frametitle{}
\end{frame}