← topoi-for-automata-wakate
20240820.tex
\documentclass[dvipdfmx,14pt, aspectratio=169]{beamer}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{amsmath,amssymb}
\usepackage{mathtools}
\usepackage{pifont}% http://ctan.org/pkg/pifont
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\1}{\mathbf{L}}
\newcommand{\R}{\mathbf{R}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\A}{\Sigma}
\newcommand{\MA}{{{\A}^{\ast}}}
\newcommand{\Aset}{\A\text{-}\Set}
\newcommand{\Atmt}{\mathbf{Atmt}}
\newcommand{\ofAset}{\A\text{-}\Set_{\text{o.f.}}}
\newcommand{\ofAtmt}{\mathbf{Atmt}_{\text{o.f.}}}
\newcommand{\memo}[1]{{\color{red}メモ: #1}}
\newcommand{\demph}[1]{\textbf{#1}}
% \newcommand{\Lan}{\mathcal{L}\textrm{angage}}
\newcommand{\Lan}{\textrm{Langage}}
\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question}
\usetheme{Darmstadt}
\usecolortheme{seahorse}
\setbeamertemplate{items}[default]
\setbeamertemplate{theorems}[default]
\setbeamertemplate{blocks}[default]
\AtBeginSection[]
{
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
\title{オートマトン理論の道具としてのtopos}
\author{洞龍弥}
\institute[]{東京大学数理科学研究科博士1年}
\date[2024年8月30日]{2024年8月30日\\}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
\section{自己紹介}
\begin{frame}{自己紹介}
\begin{description}
\item[氏名] 洞龍弥
\item[所属1] 東京大学数理科学研究科博士1年
\item[所属2] 国立情報学研究所(NII)RA
\item[興味] 最近は圏論，topos理論，coalgebra, など
\pause
\item[近況] Topos$\times$automataにかなりワクワクしている！
\end{description}
\end{frame}
\begin{frame}{個人的経験}
% オートマトンは専門ではないが，個人的には特別な存在．
\begin{enumerate}
\item[B1] 進化論の授業でオートマトンを知る．(注)
\item[B1]圏論的な最小化問題について自由研究をする．[pdf 1]
% (implicitにtoposに触れる)
\item[B4] Sipserでオートマトンを学ぶ．[pdf 2]
% Powerset constructionの豊穣圏的な
\item[M?] オートマトンがToposを為すことに気づく．
\item[M2] Sin'ya先生の話を聞き，profinite group toposとの関係に気づく
\item[D1] 局所有限オートマトンがtoposを為すことに気づく．(本気になる！)
\item[D1] word-action toposでtoposの未解決問題が解ける!(j.w.w. Yuhi Kamio)
\end{enumerate}
\end{frame}
\begin{frame}{想定聴衆}
\begin{itemize}
\item オートマトン理論や形式言語理論にモチベーションがある．
\item 圏や関手についてはなんとなく知っているが，toposやcoalgebraについてはよく知らない．
\item 位相空間論についてもよく知らない．
\item 位相群や離散群論や無限木の組み合わせ論や代数的トポロジーに興味がある人\demph{も}混ざっている．
\end{itemize}
\end{frame}
\begin{frame}{この発表で伝えたいこと:}
\begin{enumerate}
\item[\xmark] Topos理論との詳細な関係を解説(pdf執筆中)
\item[\xmark] オートマトン理論がtopos theoristにとってなぜ興味深いか
\item[\xmark] オートマトン理論の層理論($\simeq$topos理論)的な幾何学的再解釈
\item[\xmark] なぜ今，このテーマが現実的なのか？ (Morgan)
\item[\cmark] \textbf{オートマトン理論においてtopos理論が有用かもしれないこと}
\end{enumerate}
\end{frame}
\begin{frame}{免責事項}
私の興奮は，抽象的なアイデアと具体的な計算が噛み合ったことによるものなのであって，したがって決して一方を説明することで共有できるものではない．しかし，私は今日前者についてしか話さない．
\pause
それでも面白いと信じてる！
\end{frame}
\input{WholePicture}
\begin{frame}{橋の建設}
Topos理論(や圏論)は，多くの数学の分野に橋をかけてきた．
\pause
正直，橋がかかりそうな場所はまだ大量にある．大事なのは，次を問うこと．
\begin{itemize}
\item 橋を通じて何を運びたいか？
\item それを運べるだけの強靭な橋を作れるか？
\end{itemize}
Toposによる架橋という意味では，オートマトン理論と幾何学に一番可能性を感じている．
\end{frame}
\begin{frame}{
Toposがオートマトン理論に何をもたらせるか
}
\begin{itemize}
\item 統一言語として
\begin{itemize}
\item coalgebraic approach
\item algebraic approach (classes of (finite) monoids)
\item Topological (profinite) approach
\item ...
\end{itemize}
\item \textbf{幾何学との橋として}
\begin{itemize}
\item Sheaf theoretic intuition
\item 幾何学的不変量 (fundamental group, cohomology, ...)
\item Galois theory
\end{itemize}
\end{itemize}
\end{frame}
\section[導入]{導入: Grothendieckの肩に乗る}
\begin{frame}{Toposとは: 権威主義タイム(1/3)}
\begin{columns}
\begin{column}{0.3\textwidth}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{Alexander_Grothendieck.jpg}
\caption{Grothendieck}
\end{figure}
\end{column}
\begin{column}{0.7\textwidth}
\textit{トポスのテーマは，スキームのテーマから生まれました．スキームが出現したのと同じ年です---しかしトポスのテーマは，その広がりにおいては，遥かに源になったスキームのテーマを超えています．}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Toposとは: 権威主義タイム(2/3)}
\begin{columns}
\begin{column}{0.3\textwidth}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{Alexander_Grothendieck.jpg}
\caption{Grothendieck}
\end{figure}
\end{column}
\begin{column}{0.7\textwidth}
\textit{幾何学と代数，トポロジーと数論，数理論理とカテゴリー論，連続の世界と「不連続」または「離散」構造の世界が結び合う，この「ベッド」，あるいはこの「深い川」は，スキームのテーマではなくて，トポスのテーマです．}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Toposとは: 権威主義タイム(3/3)}
\begin{columns}
\begin{column}{0.3\textwidth}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{Alexander_Grothendieck.jpg}
\caption{Grothendieck}
\end{figure}
\end{column}
\begin{column}{0.7\textwidth}
スキームのテーマが新しい幾何学の核心としてあるとすれば，トポスのテーマはこの幾何学の外皮あるいは住まいです．それは，豊かな幾何学的響きを持つ同一の言語によって，\textbf{数学上の事柄からなる広大な宇宙のあれこれの地域から由来する，相互に非常に隔たった状況に共通する「エッセンス」を繊細に捉える}ために私がひろく構想したものです．
\end{column}
\end{columns}
\end{frame}
\begin{frame}{先例: Toposの生まれと数論幾何学}
Grothendieckは，Weil予想(リーマン予想の有限体類似)を解くために，幾何学を操作論的に刷新した．
\[
\text{空間} \leftarrow\text{操作}
\]
これにより，数論を含むまでに空間概念を拡張し，数論に"幾何学的操作"を輸入した．
\end{frame}
\begin{frame}{野望}
Grothendieckが数論に対してやったことを，(Grothendieckの作った道具をそのまま用いて)オートマトン理論でやる！
\end{frame}
\begin{frame}{圏論$\times$オートマトン}
\begin{itemize}
\item Coalgebraic (or manadic) approach {\small(古典的，超綺麗で面白い！)}
{\tiny
\begin{itemize}
\item {}[Adámek,
Free algebras and automata realizations in the language of categories. 1974]
\item {}[Goy, \textbf{Petrişan}, and Aiguier, Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces, 2021]
% \item 教科書 [Jacobs, Introduction to Coalgebra. 2016] がある．
\end{itemize}
}
\item Functorial approach {\small(最小化問題や一般化へ)}
{\tiny
\begin{itemize}
\item{} [Colcombet and Petri, Automata Minimization: A Functorial Approach. 2020]
\item{} [Iwaniack, Automata in toposes, and general Myhill-Nerode theorems. 2023]
\end{itemize}
}
\item Topos \textbf{of} automata
{\tiny
\begin{itemize}
\item {}[Lawvere, Functorial concepts of complexity for finite automata. 2004]
\item \textbf{我々！} "topos-geometry of automata"
\end{itemize}
}
\end{itemize}
\end{frame}
\begin{frame}{我々のやること}
各種のAutomatonがtoposを成す！(びっくり)
\begin{description}
\item[これまで] toposの中でオートマトン理論をやる
\begin{center}
$\leftarrow$ topos $=$ 数学の宇宙
\end{center}
\item[我々] topos of automataを使って幾何学を展開する
\begin{center}
$\leftarrow$ topos $=$ 空間
\end{center}
\end{description}
\end{frame}
\section{ざっくりTopos}
\begin{frame}{Topos(不本意な定義)}
\begin{definition}[Topos]
圏$\E$が\demph{(Grothendieck) topos}であるとは，
\begin{itemize}
\item ある小圏$\C$と忠実充満な埋め込み
$i\colon \E\hookrightarrow \PSh(\C)$が存在し，
\item さらに$i$の左随伴$L$が存在し
\item さらに$L$が全てのfinite limitを保つことをいう．
\end{itemize}
\end{definition}
要は,
\pause
\begin{center}
Grothendieck topos $=$ 特別いい感じの圏．
\end{center}
\end{frame}
\begin{frame}{Toposは空間の一般化}
\begin{example}[Sheaf topos]
位相空間(やlocaleやsite)$X$について，$X$上の層の圏$\mathbf{Sh}(X)$はtoposである．
\end{example}
% $\downarrow$これだけでいい
\begin{example}[Presheaf topos]
小圏$\C$について，$\C$上のpresheafの圏$\PSh(\C)\coloneqq [\C^\op,\Set]$はtoposである．
\end{example}
\end{frame}
\begin{frame}{Toposはレア！}
\begin{enumerate}
\item Toposは(その目的からして)かなり手を動かせる幾何学を展開してくれる．
\item しかし，興味ある数学的対象がtoposをなすことはレアで，いかにトポスを構成するかが肝心．
\begin{itemize}
\item $\mathbf{Top},\mathbf{Scheme},\mathbf{Ab},\mathbf{CRing},\mathbf{Group},\mathbf{Vect}$はtoposではない．
\end{itemize}
\item (いろんな)Automataはそれ自体が(いろんな)toposを成す！
\end{enumerate}
\end{frame}
\begin{frame}{ここまでのまとめ}
\begin{itemize}
\item[idea] Toposは空間概念の拡張のためにGrothendieckが考案した，位相空間の一般化(注)である．
\item[idea] 興味ある数学的対象自体がtoposを為すのはレア．
\item[idea] Toposがあれば，(かなり手を動かせる幾何学が展開できる．)
\item[fact] Toposは，物としては非常に特別な性質($\neq$? 構造)を持った圏である．
\item[fact] Presheaf categoryはtoposである．
\end{itemize}
\memo{アイデアは幼稚，計算によって実感が湧く．本当は計算についても話したい．}
\end{frame}
\section[第一のtopos]{第一のtopos: \texorpdfstring{$\Aset$}{Sigma-set}}
\begin{frame}{定義$\Aset$}
\begin{itemize}
\item $\A$は(有限とは限らない) set of alphabets.
\item $\MA\coloneqq \coprod_{n\geq 0}\A^n$は$\A$の有限文字列の集合．
\item $\A$-setとは，$(Q,\delta\colon Q\times \A\to Q)$.言い換えれば，集合$Q$への右$\MA$作用
% \item Automatonとは，$(Q, \delta\colon Q\times \A \to Q, F\subset Q)$のこと．(始点はデータに入れない．)
\end{itemize}
\begin{definition}
$\Aset$ は$\A$-setとその作用を保つ写像の圏．
\end{definition}
\begin{proposition}[$\A$-sets form a topos]
$\Aset \simeq \PSh(\MA)$はpresheaf categoryで，特にtopos.
\end{proposition}
\end{frame}
\begin{frame}{空間($\neq$位相空間)としての$\Aset$}
絵に描くのはすごく難しい．
\begin{itemize}
\item ブーケ$\bigvee_{a\in \A}S^1$の性質と，
\item カントール空間$\A^{\omega}$の性質
\end{itemize}
を併せ持っている．
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{pictures/WhyBouquetAndCantor.jpeg}
\end{figure}
\end{frame}
\begin{frame}{ブーケっぽい空間としての$\Aset$}
\begin{proposition}[Easy]
$\Aset$は連結かつ局所連結
\end{proposition}
\begin{proposition}[Easy]
$\Aset$の基本群は$\A$で生成される自由群．
\end{proposition}
\end{frame}
\begin{frame}{カントール空間っぽい空間としての$\Aset$}
\begin{proposition}[Points {[Hora 準備中]}]
$\Aset$はsurjective pointを一つ持ち，他に$\omega$-wordsの同値類\footnote{最初の有限文字をeditする操作の同値類}ごとに一つpointがある．\memo{本当は話したい！}
\end{proposition}
\begin{proposition}[Subspaces {[Hora, Iwaniack, and Morgan 準備中]}]
$\Aset$のsubspaceは，$\A^{\omega}$の`自己相似部分空間\footnote{localeとして}'と一対一に対応する．\memo{本当は話したい！}
\end{proposition}
\end{frame}
\begin{frame}{Digression}
\begin{proposition}[`Quotients' {[Kamio, Hora 2024]}]
$|\A|\geq\omega$なら，$\Aset$のquoteintはproper class個ある．特に，Lawvereの未解決問題第一番は肯定的に解決される！
\end{proposition}
\begin{question}
トンプソン群($T$?)との関係性．よっぽど$\A^{\omega}/T$っぽい．
\end{question}
\end{frame}
\begin{frame}{ここまでのまとめ}
\end{frame}
\section[{第二のtopos}]{第二のtopos: \texorpdfstring{$\Atmt$}{Atmt}}
\begin{frame}{定義 $\Atmt$}
この発表のオートマトンの定義には，始点や有限性は含めない\footnote{後に出てくる．}
\begin{definition}[$\Atmt$]
オートマトンとは，集合$Q$と写像$\delta\colon Q\times \A\to Q$と部分集合$F\subset Q$の組 $(Q, \delta, F)$．オートマトンと，オートマトンの構造を保つ写像の圏を$\Atmt$と書く．
% 射とは，これらの構造を保つ写像．オートマトンの圏
\end{definition}
\end{frame}
\begin{frame}{$\Atmt$ はトポス}
\begin{definition}[言語の圏]
言語が対象で，射$L\to L'$が$w\in \MA$で$L=w^{-1}L'$なるものとすると，圏$\Lan$ができる．これを\demph{言語の圏}という．
\end{definition}
\begin{theorem}[オートマトン=言語上のpresheaf]
$\Atmt\simeq \PSh(\Lan)$. 特に，$\Atmt$はtopos.
\end{theorem}
スペインでのVictorの反応:
\pause
`No Way!'
\end{frame}
\begin{frame}{$\Atmt$と言語認識}
$\Atmt$は実は"coalgebraの圏"というものになっている．次はcoalgebra界隈では有名な話．
\begin{definition}
\demph{The automaton of languegaes} $\1\coloneqq (\P(\MA), \delta, F)$は，状態集合が言語全体で，$\delta(L,a)=a^{-1}L$, $L\in F\iff \varepsilon\in L$なるautomaton.
\end{definition}
\begin{theorem}[古典的な定理]
$\Atmt$のterminal objectは$\1$であり，terminal への一意的な射$!\colon (Q, \delta, F)\to \1$は$q\in Q$を($q$を始点とした時に)認識される言語に移す．
\end{theorem}
\end{frame}
\begin{frame}{$\Atmt$ の幾何学(かなり未知)}
\begin{proposition}[Essential points ($\subset$ points)]
$\Atmt$のessential point と言語$L\in \P(\MA)$は一対一に対応する.
\end{proposition}
\begin{proposition}[Open subtopoi ($\subset$ Subtopoi)]
$\Atmt$のopen subtoposと言語クラス$C\subset \P(\MA)$で
\[
L\in C \implies w^{-1}L\in C (\forall w\in \MA)
\]
なるものは一対一に対応する．
\end{proposition}
\end{frame}
\begin{frame}{$\Atmt$ の幾何学(かなり未知)}
\begin{proposition}[局所連結性]
$\Atmt$は，$\Aset$の\'{e}tale covering $\Atmt\twoheadrightarrow \Aset$である．特に，$\Atmt$も局所連結である．
\end{proposition}
\begin{question}
$\Atmt$のpoint, subtopos, quotient topos, hyperconnected quotient, Aufhebung relation, は何か？
\end{question}
やるべきことだらけ
\end{frame}
\begin{frame}{ここまでのまとめ}
\end{frame}
\section[{第三のtopos}]{第三のtopos: $\ofAset$}
\begin{frame}{いかにして有限性と向き合うか？}
正則言語の理論には，当然ながら有限性が必須！私は，(Grothendieck) toposと(有限)組み合わせ論は相性が悪いと思い込んでいた．
\pause
実は，これがめちゃめちゃうまくいく！
\end{frame}
\begin{frame}{$\ofAset$}
\begin{definition}[Orbitwise-finite $\A$-set]
$\A$-set $(Q, \delta\colon Q\times \A\to Q)$が\demph{orbitwise-finite}であるとは，任意の$q\in Q$について$ \{qw\mid w\in \MA\}$が有限であることをいう．Orbitwise-finite automataからなる圏を$\ofAset$と書く．
\end{definition}
\begin{theorem}[ちょっと非自明]
$\ofAset$はtopos.
\end{theorem}
これは($\Sigma \neq \emptyset$なら)もはやpresheaf toposではない．
\end{frame}
\begin{frame}{余談: 一般論がある}
実は，$\ofAset$は$\Aset$の"quotient topos"になっている
\begin{proposition}[{Quotient$\to$ Language class構成}]
$\Aset$のQuotient toposがあると，言語クラスが一つ定まる．
\end{proposition}
\begin{example}
% $\mathbf{Cont}(\widehat{\MA})$
$\ofAset$から得られる言語クラスは正則言語．
\end{example}
\begin{example}
"Profinite-group-completion actions" $\mathbf{Cont}(\widehat{F\MA})$から得られる言語クラスは群言語．
\end{example}
\end{frame}
\begin{frame}{余談of 余談: 一般論がある}
さらに，$\Sigma=\{*\}$のとき，離散力学系の理論になる！
\begin{example}
$\ofAset$から得られる言語クラスはeventually 周期的な列$\subset \N$．
\end{example}
\begin{example}
$\mathbf{Cont}(\widehat{F\MA})= \mathbf{Cont}(\widehat{\Z})$から得られる言語クラスは周期的な列$\subset \N$．
\end{example}
\begin{example}
$p$進整数
$\mathbf{Cont}(\widehat{\Z_p})$から得られる言語クラスは周期が$p$冪列．
\end{example}
\end{frame}
\begin{frame}{ここまでのまとめ}
\end{frame}
\section{第四のtopos: $\ofAtmt$}
\begin{frame}{$\ofAtmt$}
\begin{definition}[orbitwise-finite automata]
Automaton $(Q, \delta, F)$が \demph{orbitwise-finite} とは，$\A$-setして orbitwise-finite なことをいう．Orbitwise-finite automataからなる圏を$\ofAtmt$と書く．
\end{definition}
\begin{theorem}[(ちょっと非自明)]
$\ofAtmt$はtopos.
\end{theorem}
これは(少なくともa prioriには)presheaf categoryでもcoalgebraの圏でもない．
\end{frame}
\begin{frame}{$\Atmt$と正則言語認識}
\begin{definition}
\demph{The automaton of regular languegaes} $\R$は，正則言語からなるautomaton of language $\1$の部分auotomaton.
% $\coloneqq (\P(\MA), \delta, F)$は，状態集合が正則言語全体で，$\delta(L,a)=a^{-1}L$, $L\in F\iff \varepsilon\in L$なるautomaton.
\end{definition}
\begin{theorem}[古典的な定理]
$\ofAtmt$のterminal objectは$\R$であり，terminal への一意的な射$!\colon (Q, \delta, F)\to \R$は$q\in Q$を($q$を始点とした時に)認識される正則言語に移す．
\end{theorem}
\end{frame}
\section[計算するべきこと]{計算するべき(できる)ことがたくさん！}
\begin{frame}{今後計算すべきこと}
\begin{enumerate}
\item 橋をかける
\begin{itemize}
% \item $4$つのトポスの基本的な幾何学的対象(点，部分空間，商空間，など)
\item 点 ("無限語と，それをinputしたときの振る舞い")
\item 部分空間 ("言語クラス?")
\item 商空間 ("オートマトンのクラス$\to$言語クラス?")
\item ハイパー商 ("monoidのクラス")
\end{itemize}
\item ものを運ぶ
\begin{itemize}
\item Covering Galois (cf. topological proof of Nielsen–Schreier theorem)
\item Cohomology (cf. Grothendieck's original motivation for Weil conjecture)
\item Representation theroy (cf. representations of profinite groups)
\end{itemize}
\end{enumerate}
\end{frame}
\end{document}
\begin{frame}{}
\end{frame}