\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]{biblatex} \renewbibmacro{in:}{} \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);% }}} \usetikzlibrary{automata, positioning, 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{\LC}{\mathbb{L}} \newcommand{\SQ}{\mathcal{T}} \newcommand{\D}{\mathcal{D}} \newcommand{\E}{\mathcal{E}} \newcommand{\F}{\mathcal{F}} \newcommand{\id}{\mathrm{id}} \newcommand{\ob}{\mathrm{ob}} \newcommand{\op}{\mathrm{op}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\FinSet}{\mathbf{FinSet}} \newcommand{\BoolAlg}{\mathbf{BoolAlg}} \newcommand{\Cont}{\mathbf{Cont}} \newcommand{\PSh}{\mathbf{PSh}} \newcommand{\Sh}{\mathbf{Sh}} \newcommand{\DFA}{\mathrm{DFA}} % \newcommand{\DFA}{\mathcal{DFA}\mathrm{}} \newcommand{\Coalg}{\mathbf{Coalg}} \newcommand{\G}{\mathbb{G}} \newcommand{\true}{\mathrm{true}} \newcommand{\Image}{\mathrm{Im}} \newcommand{\Nor}{\mathrm{N}} \newcommand{\Sub}{\mathrm{Sub}} \newcommand{\sgt}{\{\cdot\}} \newcommand{\je}{\mathbf{je}} \newcommand{\Cl}{\mathrm{Clopen}} \newcommand{\Gal}{\mathrm{Gal}} \newcommand{\A}{\Sigma} \newcommand{\MA}{{{\Sigma}^{\ast}}} \newcommand{\proMA}{\widehat{\MA}} \newcommand{\FA}{F_{\A}} \newcommand{\pFA}{\hat{\FA}} % \newcommand{\Aset}{\PSh (\MA)} \newcommand{\Aset}{\A\text{-}\Set} \newcommand{\T}{2x^{\A}} % \newcommand{\Atmt}{\T\text{-}\mathbf{Coalg}} \newcommand{\Atmt}{\mathbf{Atmt}} % \newcommand{\Lan}{\mathcal{L}\mathrm{ng}} % \newcommand{\Reg}{\mathcal{R}\mathrm{eg}} \newcommand{\Lan}{\mathcal{L}} \newcommand{\Reg}{\mathcal{R}} \newcommand{\K}{\mathcal{K}} \newcommand{\Func}[2]{[#1,#2]} \newcommand{\Pow}{\mathcal{P}} \newcommand{\HQ}{\mathrm{HQ}} \newcommand{\pt}{\mathrm{pt}} \newcommand{\f}{\mathrm{f.}} \newcommand{\of}{\mathrm{o.f.}} \newcommand{\pof}{{p_{\of}}} \newcommand{\fAtmt}{\Atmt_{\f}} \newcommand{\ofAtmt}{\Atmt_{\of}} % \newcommand{\fAset}{{\Aset}_{\f}} \newcommand{\fAset}{\A\text{-}\FinSet} \newcommand{\ofAset}{{\Aset}_{\of}} \newcommand{\AFinMon}{\A\text{-}\mathbf{FinMon}} \newcommand{\empword}{\varepsilon} \newcommand{\Lsq}{L_{\text{sq}}} \newcommand{\Cong}{\mathrm{Cong}} \newcommand{\colim}{\mathrm{colim}} \newcommand{\Filt}{\mathrm{Filt}} \newcommand{\bool}{\{\top, \bot\}} \newcommand{\CoE}{{\int} \hspace{-2pt}} \newcommand{\CoL}{{\CoE \Lan}} \newcommand{\qslc}{\mathrm{LC}_{\text{q.s.}}} \newcommand{\demph}[1]{\textit{\textbf{#1}}} \newcommand{\Geom}{\mathbf{Geom}} \newcommand{\SigmaInf}{\Sigma^{\leq \omega}} \font\maljapanese=dmjhira at 2.5ex \newcommand{\yo}{\textrm{\!\maljapanese\char"48}} \newcommand{\abs}[1]{\left | #1 \right|} \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} } \newcommand{\Lv}{{Local variety}} \newcommand{\lv}{{local variety}} \newcommand{\Lvs}{{Local varieties}} \newcommand{\lvs}{{local varieties}} \newcommand{\Dyck}{\mathrm{Dyck}} \renewcommand{\a}{\texttt{a}} \renewcommand{\b}{\texttt{b}} \newcommand{\dep}{\mathbf{d}} \newcommand{\val}{\mathbf{v}} \title{Topoi of automata II: Hyperconnected geometric morphisms, syntactic monoids, and language classes} \author{Ryuya Hora} \thanks{ZEN University. \url{ryuya_hora@zen.ac.jp}} % \date{\today} \subjclass[2020]{18F10, 68Q70, 20M35, 18B20} \keywords{Automaton, topos, regular language, hyperconnected geometric morphism, coalgebra, finite monoid, profinite word, Myhill-Nerode theorem} \begin{document} \begin{abstract} Hyperconnected geometric morphisms are a topos-theoretic generalization of the notion of surjective monoid homomorphisms. In this paper, we generalize the notion of language recognition by monoid, to arbitrary hyperconnected geometric morphisms from the topos $\Aset$. Using this, we obtain a construction of a Grothendieck topos $\SQ(C)$ for every language class $C \subset \Pow(\MA)$, which we call the syntactic topos of $C$. For a regular language $L$, the syntactic topos $\SQ(\{L\})$ coincides with the presheaf topos over the syntactic monoid $M_L$. Furthermore, the construction $\SQ$ provides a bijective correspondence between hyperconnected quotients of the topos of regular languages $\ofAset$ and the language classes that is closed under boolean operations and quotients. \end{abstract} \maketitle \tableofcontents \section{Introduction} \memo{acknowledgement Compared to \cite{gehrke2008duality, adamek2014generalized, ballester2015dual, uramoto2017semi} } As we have seen so far, the hyperconnected geometric morphism \[ \begin{tikzcd} \Aset \ar[r,"h"] & \ofAset \end{tikzcd} \] plays a central role in our theory of regular languages. This section aims to observe that other hyperconnected geometric morphisms \[ \begin{tikzcd} &\E\\ \Aset \ar[r]\ar[ru]\ar[rd] & \F\\ & \mathcal{G}\\ \end{tikzcd} \] correspond to other classes of languages. \section{Hyperconnected geometric morphisms from \texorpdfstring{$\Aset$}{Aset}} \subsection{Preliminaries 1: Hyperconnected geometric morphism} See \cite{johnstone2002sketchesv1, johnstone1981factorization} for the detailed definitions of hyperconnected geometric morphisms. \begin{definition}[Hyperconnected geometric morphisms] \label{def:hyperconnected} A geometric morphism $f\colon \E \to \F$ is \demph{hyperconnected} if $f^{\ast}$ is fully faithful and $f$ satisfies the following equivalent conditions: \begin{itemize} \item The essential image of $f^{\ast}$ is closed under taking subquotients. \item The essential image of $f^{\ast}$ is closed under taking subobjects. \item The essential image of $f^{\ast}$ is closed under taking quotient objects. \item The counit $\epsilon \colon f^{\ast}f_{\ast} \Rightarrow \id_{\E}$ is monic. \end{itemize} \end{definition} Since $f^{\ast}$ for a hyperconnected geometric morphism $f\colon \E \to \F$ is fully faithful, the codomain topos $\F$ can be regarded as a full subcategory of the domain topos $\E$. If we regard it as a full subcategory, we call it a \demph{hyperconnected quotient}, according to the terminology in \cite[][section VII.]{lawvere2007axiomatic}. \begin{proposition} For any Grothendieck topos $\E$, the partially ordered class of (equivalence classes of ) hyperconnected quotients $\HQ(\E)$ is a small complete lattice. \end{proposition} \subsection{Preliminaries 2: Local state classifier} We will recall the description of $\HQ(\E)$ given in \cite{hora2024internal}. \begin{definition} We adopt the following definitions: \begin{itemize} \item \demph{A local state classifier} of a category $\C$ is the colimit of all monomorphisms \[ \Xi \coloneqq \colim\left ( \C_{\text{mono}}\to \C \right), \] where $\C_{mono}$ denotes the subcategory consisting of all objects and all monomorphisms of $\C$. \item Its associated cocone is denoted by $\{\xi_X\colon X \to \Xi\}_{X\in \ob(\C)}$. \end{itemize} \end{definition} \begin{fact}[\cite{hora2024internal}] \label{fact:LSCClassification} For a Grothendieck topos $\E$, we have the following facts: \begin{itemize} \item $\E$ has a local state classifier $\Xi$. \item $\Xi$ admits the canonical $\land$-semilattice structure such that \[ \begin{tikzcd} &X\times Y\ar[ld, "\xi_X \times \xi_Y"']\ar[rd, "\xi_{X\times Y}"]&\\ \Xi\times \Xi\ar[rr,"\land"]&&\Xi \end{tikzcd} \] commutes for every pair of objects $(X,Y)$. \item The complete lattice of internal filters of $\Xi$, which is denoted by $\Filt(\Xi)$, is isomorphic to $\HQ(\E)$. \[ \HQ(\E) \cong \Filt(\Xi) \] \item For an internal filter $F\rightarrowtail \Xi$, the counit $\epsilon_X\colon f^* f_* X \rightarrowtail X$ of the associated geometric morphism $f\colon \E \to \F$ is given by the pullback diagram \[ \begin{tikzcd} f^* f_* X \ar[r]\ar[d, "\epsilon_X", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F\ar[d,rightarrowtail]\\ X\ar[r, "\xi_X"] &\Xi\\ \end{tikzcd} \] \end{itemize} \end{fact} From the next subsection, we will specialize this theorem to the topos $\Aset$. \subsection{The local state classifier of \texorpdfstring{$\Aset$}{Aset}.} This section describes \demph{the local state classifier} of the topos $\Aset$. % See \Cref{sssec:LSC} or \cite{hora2024internal} for details. Automata-theoretically, the local state classifier provides a categorical description of congruences, varieties, and Myhill-Nerode theorem. % Topos-theoretically, the local state classifier classifies \demph{hyperconnected quotients}., which gives a generalized variety theorem. \begin{definition}We introduce the notion of right-congruences: \begin{itemize} \item A \demph{right congruence} on $\MA$ is an equivalence relation $\sim$ such that for any $u,v,w \in \MA$, if $u\sim v$ then $uw \sim vw$. \item For two congruences $\sim $ and $ \sim'$, the order relation ${\sim} \leq {\sim'}$ means the condition: for any $u,v \in \MA$, $u\sim v$ implies $u\sim'v$. \item The poset of all congruences on $\MA$ and their order is denoted by $\Xi$. \item The action of ${\sim} \ast w$ is defined by $u \mathrel{({\sim} \ast w)} v \iff wu \sim wv$. \end{itemize} \end{definition} \begin{proposition}We have the following properties: \begin{itemize} \item Those data amount to make $\Xi$ to be an internal semilattice in the topos $\Aset$. Furthermore, this is the local state classifier \cite{hora2024internal} of the topos $\Aset$. \item In other words, the $\A$-set $\Xi$ is the colimit of all monomorphisms in $\Aset$. \item The colimit cocone $\{\xi_{X}\colon X=(Q, \delta)\to \Xi\}_{X\in \ob(\Aset)}$ is given by \[ w\mathrel{(\xi_X (q))} v \iff qw=qv. \] \end{itemize} \end{proposition} In particular, the morphism $\xi_{\Lan}\colon \Lan \to \Xi$ captures the notion of Nerode congruence. \begin{lemma} \label{lem:NerodeCongruenceAsXi} The component of the colimit cocone $\xi_{\Lan}\colon \Lan \to \Xi$ sends a language $L$ to \demph{its Nerode congruence} $\sim_{L}$, where \[ u \sim_{L} v \iff u^{-1}L = v^{-1} L. \] \end{lemma} % This means that the $\A$-set $\Xi$ is the colimit of all monomorphisms in $\Aset$. The colimit cocone will be refered to by $\{\xi_{X}\colon X=(Q, \delta)\to \Xi\}_{X\in \ob(\Aset)}$. % % To affirmatively answer the question \ref{QuestionInjectivity}, it is enough to answer the following question affirmatively: % \begin{question} % Is the function $\xi_{\Lan}$ surjective? In other words, is every congruence induced by a language? \memo{Unless $|\A|<2$, No! Consider an (accessible) automaton (with a start state) with $3$ sinks. At least $2$ of the $3$ sinks define the same language ($\emptyset$ or $\MA$).} % \end{question} \begin{proposition}[\cite{hora2024internal} for $\Aset$] \label{prop:LSCcorresinAset} There is a bijective correspondence between (equivalence classes of) hyperconnected geometric morphisms from $\Aset$ and the internal filters of $\Xi$, which furthermore correspond to subsets $F \subset \Xi$ such that \begin{itemize} \item $F$ is closed under $\MA$-actions, \[ \forall {\sim}\in F, \forall w\in \MA, ({\sim}*w)\in F. \] \item $F$ is closed under taking finite intersections (in particular, $F$ contains the top element), and \[ \text{(The trivial equivalence)} \in F \] \[ \forall {\sim}, {\sim'}\in F, ({\sim}\land {\sim'})\in F. \] \item $F$ is upward closed. \[ \forall{\sim}\in F, \forall \sim'\in \Xi, ({\sim}\leq{\sim'} \implies {\sim'}\in F). \] \end{itemize} \end{proposition} For a hyperconnected geometric morphism $h\colon \Aset \to \E$, let $F_{h}$ denote the corresponding internal filter of $\Xi$. \begin{example} \label{exmp:TheFilterForRegularOrbitFinite} For the hyperconnected geometric morphism $h\colon \Aset \to \ofAset$, the corresponding filter $F_h$ is the set of all congruences $\sim$ whose quotient set $\MA/{\sim}$ is finite. \end{example} % \subsection{Quotient monoids are hyperconnected quotient topoi} \subsection{Hyperconnected geometric morphisms subsume surjective monoid homomorphisms} In algebraic language theory, one of the most important objects is surjective monoid homomorphisms $\MA \twoheadrightarrow M$. As every full and bijective on objects functor, any surjective monoid homomorphism $\phi\colon \MA \twoheadrightarrow M$ induces a hyperconnected geometric morphism (\memo{number}\cite{johnstone2002sketchesv1}) % \[ % \ADJ{\Aset=\PSh(\MA)}{\mathrm{Ran}_{\phi}}{\PSh(M)}{ {-}\circ \phi}. % \] \begin{equation}\label{eq:HyperconnectedQuotientInducedByMonoidSurjection} \ADJ{\Aset=\PSh(\MA)}{\mathrm{Ran}_{\phi}}{\PSh(M).}{ {-}\circ \phi} \end{equation} In this section, we will rewrite this hyperconnected quotient in terms of the local state classifier, equivalently, right congruences. Notice that any surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$ induces a right congruence % \[ % u\sim_{\phi} v \iff \phi(u) \sim \phi(v). % \] \begin{equation}\label{eq:CongruenceByMonoid} u\sim_{\phi} v \iff \phi(u) \sim \phi(v). \end{equation} Furthermore, this congruence is two-sided in the following sense. \begin{definition} A right congruence ${\sim}$ is \demph{a two-sided congruence}, if \[ u\sim v \implies wuw' \sim wvw' \] for any words $u,v,w,w' \in \MA$. \end{definition} \begin{lemma}\label{lem:EquivalenceConditionsOfTwoSidedCongruences} For a right congruence ${\sim} \in \Xi$, the following conditions are equivalent: \begin{enumerate} \item $\sim$ is a two-sided congruence. % , in the sense that % \[ % v\sim v' \implies uvw \sim uv'w % \] % for any words $u,v,v',w \in \MA$. \item ${\sim}$ is a \demph{congruence of monoid}, in the sense that the quotient set $\MA/ {\sim}$ admits a (necessarily unique) monoid structure such that the quotient map \[\pi\colon \MA \twoheadrightarrow \MA/{\sim}\] is a surjective monoid homomorphism. \item For any word $w\in \MA$, we have ${\sim} \leq (\sim\ast w)\in \Xi$. \item Its upward closure $\{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ is an internal filter of $\Xi$. \end{enumerate} \end{lemma} \begin{proof} First, we prove the equivalence between $(1)$ and $(2)$. Assuming $(2)$ and $u \sim v$ (i.e., $\pi(u)=\pi(v)$), we have $\pi(wuw')= \pi(w)\pi(u) \pi(w')=\pi(w)\pi(v) \pi(w') = \pi(wvw')$, which proves $wuw'\sim wvw'$. Conversely, if $\sim$ is a two-sided congruence, then $u\sim v$ and $u'\sim v'$ imply $uu'\sim vu' \sim vv'$, which proves that the well-definedness of the monoid operation on the quotient set $\MA/{\sim}$. The condition $(3)$ is equivalent to \begin{align*} (3) & \iff \forall w\in \MA, \;\forall u,v\in \MA ( {u\sim v} \implies u \mathrel{({\sim}*w)}v)\\ & \iff \forall w,u,v,\; (u\sim v \implies wu\sim wv)\\ &\iff \text{$\sim$ is a left congruence.} \end{align*} Since ${\sim}\in \Xi$ is a right congruence, we conclude that the condition $(3)$ is equivalent to $(1)$. Lastly, we will prove the equivalence between $(3)$ and $(4)$. If $(4)$ holds, then the set $\{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ is closed under the $\MA$-action. Therefore, we have ${\sim}*w \in \{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ for any $w\in \MA$, which proves $(3)$. Conversely, we prove that $(3)$ implies $(4)$. Since the upward closure $\{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ is upward closed and closed under finite meets, it suffices to prove that it is closed under the $\MA$-action. For any ${\sim'}\in \{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ and $w\in \MA$, we have ${\sim} \leq ({\sim}*w) \leq ({\sim'}*w)$ and hence ${\sim'}*w \in \{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$. This completes the proof. \end{proof} Summarizing the above observations, we have the next proposition. \begin{proposition}[From monoid to topos] Any surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$ induces a hyperconnected geometric morphism from $\Aset$ (Diagram \ref{eq:HyperconnectedQuotientInducedByMonoidSurjection}). Furthermore, the corresponding internal filter $F\subset \Xi$ is given by % \[ % F = \{{\sim}\in \Xi \mid \forall u,v \in \MA, \phi(u)=\phi(v) \implies u\sim v\}, % \] % which is the upward closure of ${\sim_{\phi}}$ (See the notation \ref{eq:CongruenceByMonoid}) \[ F = \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}. \] \end{proposition} \begin{proof} What we have not yet proven is the equality \[ F = \{{\sim}\in \Xi \mid \forall u,v \in \MA, \phi(u)=\phi(v) \implies u\sim v\}. \] Let us regard the presheaf topos $\PSh(M)$ as a full subcategory of $\Aset$. Then the representable presheaf $M\in \PSh(M)$ is regarded as a $\A$-set $M$ equipped with the canonical action \[ M\times \MA \to M \colon (m, w) \mapsto m\phi(w). \] In particular, we have $\xi_{M}(e)\in F$ for the neutral element $e\in M$. Since we have \[ u \mathrel{\xi_{M}(e)} v \iff e \phi(u) = e\phi(v) % \iff \phi(u) = \phi(v) \iff u \sim_{\phi} v, \] we obtain ${\sim_{\phi}} \in F$. Since the internal filter $F$ is upward closed, we conclude an inclusion relation $F \supset \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}$. Conversely, we will prove $F \subset \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}$. Since the right hand side, for which we will write $F_{\phi} \coloneqq \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}$, is an internal filter (\Cref{lem:EquivalenceConditionsOfTwoSidedCongruences}), in order to prove $F\subset F_{\phi}$ it suffices to prove the inclusion relation of the corresponding hyperconnected quotients (assuming the isomorphism of poset given by \Cref{fact:LSCClassification}). \memo{this is rigorously verified by the joint surjectivity...} Take an arbitrary object $(Q, Q \times M \to Q) \in \ob(\PSh(M))$, which will be simply denoted by $Q$ by abuse of notation. What we need to prove is the inequality \[ {\sim_{\phi}} \leq \xi_{Q}(q) \text{ in } \Xi \] for every $q\in Q$, where $Q$ is regarded as a $\A$-set by $qw\coloneqq q\phi(w)$. By the Yoneda lemma in the presheaf topos $\PSh(M)$, for each $q\in Q$, we have a unique $M$-set morphism \[ \begin{tikzcd} M \ar[r,"\lceil q \rceil"] & Q \end{tikzcd} \] that sends $e\in M$ to $q \in Q$. By regarding them as $\A$-sets, we obtain the diagram \[ \begin{tikzcd} M \ar[r,"\lceil q \rceil"] \ar[rd, "\xi_{M}"']& Q\ar[d, "\xi_Q"]\\ &\Xi, \end{tikzcd} \] % we obtain a surjective $M$-set homomorphism % \[ % \pi\colon \coprod_{q\in Q} M \twoheadrightarrow Q, % \] % from the coproduct of the $Q$-copies of the representable $M$-set $M$. Regarding this as a diagram in the topos $\Aset$, for each $q\in Q$, we obtain the diagram % \[ % \begin{tikzcd} % M\ar[r, "i_{q}", rightarrowtail]\ar[rrd,"\xi_M"']& % \coprod_{q\in Q} M % % \ar[rd, "\xi_{\coprod_{q\in Q} M}"'] % % \ar[rd, "\xi"'] % \ar[r,"\pi", twoheadrightarrow]& Q\ar[d, "\xi_{Q}"]\\ % &&\Xi, % \end{tikzcd} % \] which is not necessarily commutative. Even if it is not commutative, this is lax-commutative, in the sense that $\xi_M \leq \xi_Q \circ \lceil q \rceil$. \memo{cite} Thus, we obtain \[ {\sim_{\phi}} = \xi_{M}(e) \leq \xi_Q(\lceil q\rceil (e))= \xi_Q (q), \] which completes the proof. \end{proof} \section{Interaction between hyperconnected quotients and language classes} % \texorpdfstring{$\mapsto$}{mapsto} language class construction} \subsection{Topos to language: Hyperconnected geometric morphism recognizes a language} In this section, we will generalize the notion of language recognition by surjective monoid homomorphisms to arbitrary hyperconnected geometric morphisms. Recall that a surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$ is said to \demph{recognizes} a language $L\in \Lan$ if there exists a subset $S\subset M$ such that $\phi^{-1}(S)=L$. Since the recognition by hyperconnected quotients has several forms, we will first prove the equivalence between them. We will call this equivalence the Myhill-Nerode theorem for a hyperconnected quotient due to the reason explained in \Cref{rmk:WhyIsItMyhillNerodeTheorem}. % \subsection{Myhill-Nerode theorem for a hyperconnected geometric morphism} % The following proposition connects languages and hyperconnected quotient: \begin{proposition}[Equivalence definitions of recognitions, or the the Myhill-Nerode Theorem] % for a hyperconnected quotient] \label{prop:EquivRecognitionOfLnagByHyperconnected} For a hyperconnected geometric morphism $h\colon \Aset \to \E$ and a language $L\in \Lan$, the following conditions are equivalent: \begin{enumerate} \item $L$ is an element of $h^* h_* \Lan \subset \Lan$\footnote{Since the counit $\epsilon_{\Lan}\colon h^* h_* \Lan \rightarrowtail \Lan$ is monic, we can regard it as a subset of $\Lan$.}. \item The corresponding filter $F_{h}$ contains \text{the Nerode congruence} $\sim_{L}$ of $L$ (\Cref{lem:NerodeCongruenceAsXi}). % , which is defined by % \[ % u \sim_{L} v \iff u^{-1}L = v^{-1} L. % \] \item There is a $\A$-set $(Q, \delta)$ in the topos $\E$ (regarded as a full subcategory of $\Aset$), such that $(Q, \delta)$ (with a suitable choice of an initial state $q_0$ and accept states $F\subset Q$) recognizes $L$ as an automaton. \end{enumerate} \end{proposition} \begin{proof} By \Cref{fact:LSCClassification}, we have the following pullback diagram: \[ \begin{tikzcd} h^* h_* \Lan \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\ \Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\ \end{tikzcd} \] This and \Cref{lem:NerodeCongruenceAsXi} prove the equivalence between (1) and (2). Assuming (1), the counit morphism $\epsilon_{\Lan}\colon h^* h_* \Lan \to \Lan$ itself can be regarded as an automaton (without initial state) (see \memo{cite}). This automaton (with the initial state $L\in h^* h_* \Lan$) recognizes the language $L$. This proves that (1) implies (3). Lastly, let us assume (3). If a $\A$-set $(Q, \delta)$ recognizes the language $L$, then there is a morphism $\chi_F \colon (Q, \delta) \to \Lan$ such that the image of $\chi_F$ contains $L$. If $(Q, \delta)$ is in $\E$, the universality of the counit implies that there is a lift of $\chi_F$ along the counit: \[ \begin{tikzcd} &h^* h_* \Lan \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\ (Q, \delta)\ar[ru, dashed]\ar[r, "\chi_F"]&\Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\ \end{tikzcd} \] This proves that $L$ is an element of $h^* h_* \Lan$. \end{proof} \begin{definition} We say that a hyperconnected geometric morphism $h\colon \Aset \to \E$ \demph{recognizes} a language $L\in \Lan$, if it satisfies the equivalent conditions of \Cref{prop:EquivRecognitionOfLnagByHyperconnected}. The set of languages recognized by $h\colon \Aset \to \E$ is denoted by $\LC_{h}$ (or $\LC(\E)$ by the abuse of notation). \end{definition} As we have seen, the set $\LC_h$ is in fact a sub$\A$-set $\LC_h = h^* h_* (\Lan) \xrightarrow{\epsilon_{\Lan}} \Lan$, constructed by the pullback diagram \[ \begin{tikzcd} \LC_{\Lan}= h^* h_* \Lan \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\ \Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\ \end{tikzcd} \] \begin{remark}[Myhill-Nerode theorem]\label{rmk:WhyIsItMyhillNerodeTheorem} In the case where $\E = \ofAset$, \Cref{prop:EquivRecognitionOfLnagByHyperconnected} is exactly the \demph{Myhill-Nerode theorem}, since the following pullback diagram \[ \begin{tikzcd} \Reg \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\ \Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\ \end{tikzcd} \] states that a language $L$ is regular if and only if its Nerode congruence $\sim_L$ has finitely many equivalence classes. Therefore, we can regard \Cref{prop:EquivRecognitionOfLnagByHyperconnected} as a topos-theoretic generalization of the Myhill-Nerode theorem. \end{remark} % In the theory of formal languages, it is central to study \demph{classes of languages}: % \begin{definition} % For a hyperconnected geometric morphism $h \colon \Aset \to \E$ from the Grothendieck topos $\Aset$, % \begin{itemize} % \item the \demph{associated class of language} is the subobject $\LC_h \coloneqq h^{\ast}h_{\ast} \Lan \rightarrowtail \Lan$ obtained as the component of the counit\footnote{Rigorously, one need to take the strict image of the component of the counit.}. % \item a language $L$ is \demph{recognized by $h$} if it is an element of (the underlying set of) $L \in \LC_h$. % \end{itemize} % \end{definition} % \begin{definition} % For a hyperconnected geometric morphism $h\colon \Aset \to \E$, \demph{the associated language class} is the set of languages satisfying the equivalent conditions in \Cref{prop:EquivRecognitionOfLnagByHyperconnected}, which is denoted by $\LC_{h}$. % \end{definition} % \begin{definition} % We say that a hyperconnected geometric morphism $h\colon \Aset \to \E$ \demph{recognizes} a language $L$, if they satisfy the equivalent conditions of \Cref{prop:EquivRecognitionOfLnagByHyperconnected}. % \end{definition} \begin{proposition} For a surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$, a language $L$ is recognized by $\phi_*\colon \Aset \twoheadrightarrow \PSh(M)$ if and only if $L$ is recognized by $\phi \colon \MA \twoheadrightarrow M$. \end{proposition} Furthermore, for a language $L\in \Lan$, the following conditions are equivalent: \begin{enumerate} \item $h$ recognizes $L$, i.e., $L\in \LC(h)$. \item $\phi$ recognizes $L$. % Surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$. \item ${\sim} \leq {\sim}_{L}\in \Xi$. \end{enumerate} \begin{proposition} A language $L$ is recognized by $h\colon \Aset \twoheadrightarrow \ofAset$ if and only if $L$ is regular. \end{proposition} Combining the above proposition and the main theorem of \cite{hora2024topoi}, we obtain several characterization theorems of regular languages by DFA, finite monoids, and profinite words. \subsection{Language to topos: The syntactic Grothendieck topos \texorpdfstring{$\SQ(C)$}{SQC} associated with a language class \texorpdfstring{$C$}{C}} Recall that the syntactic monoid of a language is the minimum monoid (more rigorously, the minimum quotient monoid of $\MA$) that recognizes the language. Similarly, in this section, we will define the syntactic topos $\SQ(C)$ as the minimum topos (more rigorously, minimum hyperconnected quotients) of the topos $\Aset$ that recognizes all languages of a given language class $C$. \begin{definition}\label{def:LanguageClass} A \demph{language class} is a subset $C \subset \Lan$ of the set of languages $\Lan$. % A language class is \demph{quotient-stable} if $\LC$ is a sub $\A$-set of $\Lan$, i.e., if $\forall L\in \LC, \forall w\in \MA, \; w^{-1}L \in \LC$. % The set of quotient-stable language classes will be denoted by $\qslc$. \end{definition} \memo{Before the definition, we make a remark on the order structure of the hyperconnected quotients.} \begin{definition}\label{def:SyntacticTopos} For a language class $C\subset \Lan$, its \demph{syntactic Grothendieck topos} $\SQ(C)$ is the minimum hyperconnected quotient that recognizes all languages in $C$. \end{definition} By abuse of terminology, for a language $L\in \Lan$, we call $\SQ(\{L\})$ \demph{the syntactic topos of the language $L$}. % , and write $\SQ(L)$ We write $\SQ(L)$ for $\SQ(\{L\})$ when it does not make any confusion. \begin{remark}[$\SQ(C)$ is a geometric morphism] Rigorously speaking, $\SQ(C)$ is not just a topos, but it is a topos equipped with the canonical hyperconnected geometric morphism $h \colon \Aset \twoheadrightarrow \SQ(C)$. \end{remark} % The fact that $\LC_h$ is a sub$\A$-set is equivalent to saying that it is quotient-stable: % \begin{definition}\label{dfn:quotientStable} % A \demph{language class} is a subset $\LC \subset \Lan$ of the set of languages $\Lan$. A language class is \demph{quotient-stable} if $\LC$ is a sub $\A$-set of $\Lan$, i.e., if $\forall L\in \LC, \forall w\in \MA, \; w^{-1}L \in \LC$. % The set of quotient-stable language classes will be denoted by $\qslc$. % \end{definition} % In order to calculate $\SQ$, l Let us explicitly write down the construction $\SQ$. \begin{lemma} For any family of right congruences $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$, there exists the the minimum internal filter that contains ${\sim}_{\lambda}$ for any $\lambda \in \Lambda$. \end{lemma} \begin{proof} Since an internal filter is defined by several closure properties (\Cref{prop:LSCcorresinAset}), an arbitrary intersection of internal filters is again an internal filter. Therefore, the intersection of all internal filters that contain $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$ is the minimum one. \end{proof} \begin{definition}[Generating an internal filter]\label{def:GeneratingFilter} For a family of right congruences $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$, the minimum internal filter that contains them is denoted by \[ \langle {\sim_{\lambda}}\mid \lambda\in \Lambda\rangle. \] \end{definition} % \begin{lemma} For a family of right congruences $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$, the generated internal filter $\langle {\sim_{\lambda}}\mid \lambda\in \Lambda\rangle$ can be explicitly described as \begin{equation}\label{eq:generatedFilter} \langle {\sim_{\lambda}}\mid \lambda\in \Lambda\rangle = \left\{{\sim}\in \Xi \;\middle |\; \exists k \geq 0, \; \exists \lambda_1, \dots \lambda_k\in \Lambda,\; \exists w_1, \dots w_n\in \MA, \left(\bigwedge_{i=1}^k {\sim_{\lambda_{i}}}*w_i\right) \leq {\sim}\right\} . \end{equation} % is the minimum internal filter that contains ${\sim}_{\lambda}$ for any $\lambda \in \Lambda$. % \end{lemma} % \begin{proof} % \end{proof} \begin{proposition}[Concrete description of $\SQ$]\label{prop:concreteDescritionOfSQ} For a language class $C$, the internal filter $F_{C}\subset \Xi$ corresponding to the hyperconnected quotient $\Aset\twoheadrightarrow \SQ(C)$ is given % corresponds to the internal filter $F_{C}\subset \Xi$ defined by % \[ % F_{C} = \{{\sim} \in \Xi \mid \text{There exists a finite family of languages $L_1 \dots L_k \in C$ and words $w_1, \dots w_n\in \MA$, such that $\bigwedge_{i=1}^{k} {\xi_{\Lan}(L_i)*w} \leq {\sim}$}\} % \] \[ F_{C} = \langle \xi_{\Lan}(L)\mid L \in C \rangle, % \left\{{\sim} \in \Xi \;\middle | \;\exists k\in \N, \exists L_1 \dots L_k \in C, \exists w_1, \dots w_n\in \MA, \left(\bigwedge_{i=1}^{k} {\xi_{\Lan}(L_i)*w_i}\right) \leq {\sim}\right\}. \] with the notation in \Cref{def:GeneratingFilter}. \end{proposition} \begin{proof} By \Cref{prop:EquivRecognitionOfLnagByHyperconnected}, the corresponding filter $F_{C}$ should be the % Let $F_{C}$ be % the internal filter $F_{C}\subset \Xi$ corresponding to the hyperconnected quotient $\Aset\twoheadrightarrow \SQ(C)$. the minimum internal filter that contains $\xi_{\Lan}(L)$ for any $L \in C$. % $F_{\SQ(C)}$ should be the minimum internal filter of $\Xi$ that contains $\xi_{\Lan}(L)$ for every $L \in C$, in other words, $F_{\SQ(C)}$ is the closure of $\{\sim_L \mid L \in C\}$ by the three operations in \Cref{prop:LSCcorresinAset}. % Such closure must contain $\{\simeq \in \Xi \mid \text{There exists a finite family of languages $L_1 \dots L_k \in C$, such that $\bigwedge_{i=1}^{k} {\sim_{L_i}} \leq {\sim}$}\}$ \end{proof} Combining \Cref{prop:concreteDescritionOfSQ} and \Cref{eq:generatedFilter}, we obtain the following equation \begin{equation}\label{eq:TheCorrespondingFilterForALanguageClass} F_C =\left\{{\sim} \in \Xi \;\middle | \;\exists k\in \N, \exists L_1 \dots L_k \in C, \exists w_1, \dots w_n\in \MA, \left(\bigwedge_{i=1}^{k} {\xi_{\Lan}(L_i*w_i)}\right) \leq {\sim}\right\}. \end{equation} \subsection{The construction \texorpdfstring{$\SQ$}{SQ} subsumes syntactic monoids of quasi-regular languages.} % The Myhill-Nerode theorem states that a language $L$ is regular if and only if its orbit $\{w^{-1}L\mid w\in \MA\}$ is finite. By analogy, we define the regularity of right congruence as follows. % \begin{definition} % A right congruence ${\sim}$ is \demph{regular}, if its orbit $\{{\sim}\ast w\mid w\in \MA\}$ is finite. % \end{definition} % Notice that if a language $L$ is regular, then its Nerode congruence $\sim_L$ is also regular. % \begin{remark} % \memo{Pullback diagram and normalizer operator} % \end{remark} \begin{lemma}\label{lem:SufficientAndNecessaryConditionForSyntacticMonoidGivesSyntacticTopos} For any language $L$, the following conditions are equivalent: \begin{itemize} \item The syntatic monoid $M_L$ provides the syntactic topos $\SQ(L)\simeq \PSh(M_L)$ \item There exists a finite family of words $\{w_i\}_{i=1}^n$ such that \[ {\cong_L} = \bigwedge_{i=1}^n \xi_{\Lan}(L*w_i) \] \item There exists a finite family of words $\{w_i\}_{i=1}^n$ such that, for any word $w\in \MA$, we have \[ \bigwedge_{i=1}^n \xi_{\Lan}(L*w_i) \leq \xi_{\Lan}(L*w). \] \end{itemize} \end{lemma} \begin{definition}\label{def:quasi-regularLanguages} A language $L\in \Lan$ is \demph{quasi-regular} if $\xi_{\Xi}(\xi_{\Lan}(L))\in F_{\of}$. \memo{explain $F_{\of}$} \end{definition} Let us rewrite this abstract definition. Since we have \begin{align*} u \mathrel{\xi_{\Xi}(\xi_{\Lan}(L))} v &\iff \left(\forall x,y \in \MA, x \mathrel{(\xi_{\Lan}(L)*u)}y \iff x \mathrel{(\xi_{\Lan}(L)*v)}y\right)\\ &\iff \left(\forall x,y \in \MA, ux \mathrel{\xi_{\Lan}(L)}uy \iff vx \mathrel{\xi_{\Lan}(L)}vy\right)\\ &\iff \left(\forall x,y \in \MA, (\forall z_0\in \MA, uxz_0\in L \iff uyz_0\in L) \iff (\forall z_0\in \MA, vxz_1 \in L \iff vyz_1 \in L)\right)\\ \end{align*} \begin{proposition} For a language $L$ whose Nerode congruence $\sim_{L}$ is regular (in particular for a regular language), its syntactic quotient $\SQ(L)$ is equal to the one induced by the canonical surjective monoid homomorphism $\MA \twoheadrightarrow M_L$ to the syntactic monoid $M_L$. \[ \begin{tikzcd} \SQ(L)\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(M_{L}) \end{tikzcd} \] \end{proposition} \begin{theorem} If a language $L\in \Lan$ is quasi-regular (\Cref{def:quasi-regularLanguages} $\xi_{\Xi}(\xi_{\Lan}(L))\in F_{\of}$), then $\SQ(L)$ coincides with the presheaf topos over the syntactic monoid $\pi \colon \MA \twoheadrightarrow M_L$ \[ \SQ(L) \simeq \PSh(M_L). \] \end{theorem} \subsection{The prodiscrete Galois monoid $\SQ(C) \simeq \Cont(M_C)$} This is a prodiscrete version of \cite{uramoto2016semi}. \begin{conjecture} According to \cite{rogers2023toposes}, for any language class $C\subset \Lan$, there exists a canonically constructed prodiscrete monoid $M_C$ and a discrete monoid homomorphism $\MA \to M_C$ that induces the hyperconnected geometric morphism \[ \Aset \twoheadrightarrow \SQ(C). \] \end{conjecture} \subsection{The Galois connection between language recognition and syntactic topos.} % \subsection{Galois correspondence} \begin{theorem}\label{thm:GaloisConnection} This construction $h \mapsto \LC_h$ provides a Galois connection between two complete lattices $\HQ(\Aset)$ and $\qslc$ with a left adjoint which will be denoted by $\SQ$: % \[ % \ADJ{\HQ(\Aset) \cong \Filt(\Xi)}{\LC = \xi_{\Lan}^{\ast}}{\Sub(\Lan)\cong \qslc}{}. % \] % The left adjoint in \Cref{thm:GaloisConnection} will be denoted by $\SQ$. \[ \ADJ{\HQ(\Aset)}{\LC}{\qslc}{\SQ}. \] \end{theorem} \begin{proof} We will prove it via the following paraphrase: \[ \ADJ{\HQ(\Aset) \cong \Filt(\Xi)}{\LC = \xi_{\Lan}^{\ast}}{\Sub(\Lan)\cong \qslc}{}. \] Two isomorphisms above are due to \Cref{fact:LSCClassification} and the fact that a language class is quotient-stable if and only if it is a sub$\A$-set of $\Lan$. To prove that the construction $\LC$ has a left adjoint, it is enough to prove that it preserves all infimums. Since the construction $\LC$ is just a pullback along the morphism $\xi_{\Lan}$, the proof is completed. \end{proof} Because this is a Galois connection, we automatically obtain the following bijective correspondence between \dq{fixed points.} \begin{corollary}\label{Cor:TheCorrespondence} There is a canonical isomorphism between two complete lattices \[ \Image(\SQ) \cong \Image(\LC). \] \end{corollary} \begin{proof} This is the equivalence of categories induced by the adjunction \Cref{thm:GaloisConnection}. \end{proof} We have reached an abstract viewpoint. In the following subsection, we will observe through concrete examples how these abstract \Cref{thm:GaloisConnection} and \Cref{Cor:TheCorrespondence} subsume some concrete theories of automata. For a quotient-stable language class $C$, $\SQ(C)$ is a hyperconnected geometric morphism $\Aset \to \E$. However, if it is not confusing, it will be referred to just by the codomain topos $\E$. \subsection{Examples and calculations of the correspondence} This subsection aims to give some concrete examples of the correspondence \Cref{thm:GaloisConnection} and \Cref{Cor:TheCorrespondence}. \para{Toy examples} Let us see some of the easiest examples. \begin{example}[Maximum element] The identity geometric morphism $\id_{\Aset}\colon \Aset \to \Aset$ is the maximum hyperconnected quotient. The associated language class $\LC_{\id_{\Aset}}$ is the set of all languages. Conversely, the hyperconnected quotient $\SQ(\Lan)$ is $\id_{\Aset}$, since there is a language $L$ whose Nerode congruence ${\sim_{L}}$ is trivial \footnote{If $\abs{\A}\leq 1$, it is easy to construct such a language. For the case where $\abs{\A}>1$, see \memo{Exmp:SquareLanguage}.}. \[ \begin{tikzcd} \Aset \ar[r, bend right, "\LC"', mapsto ] & \Lan \ar[l, bend right, "\SQ"', mapsto] \end{tikzcd} \] \end{example} \begin{example}[Minimum element] Since $\SQ$ is a left adjoint, it sends the empty language class $\{\}$ to the smallest hyperconnected quotient, which is the global section geometric morphism \[ !\colon \Aset \to \Set.\] % is hyperconnected. The corresponding class $\LC_{\Set}$ is the set $\{\emptyset, \MA\}$. \[ \begin{tikzcd} &\{\}\ar[ld, "\SQ"', mapsto]\\ \Set \ar[r, bend right, "\LC", mapsto ] & \{\emptyset, \MA\} \ar[l, bend right, "\SQ", mapsto] \end{tikzcd} \] \end{example} \para{Integers, and profinite integers} \begin{example}[Regular cases] For a regular language $L$, its syntactic quotient is given by \[ \begin{tikzcd} \SQ(L)\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(M_{L}) \end{tikzcd} \] since its Nerode congruence $\sim_L$ is regular. For example, for a positive interger $n>0$, let us consider the (regular) language $L_n \coloneqq \{w\mid \abs{w}_a \cong \abs{w}_b \mod n\}$, where $\abs{w}_\a$ (respectively, $\abs{w}_\b$) denotes the number of $\a$ (respectively $\b$) in the word $w$. Its Nerode congruence $\sim_{L_n}$ is given by \[ w\sim_{L_n} w' \iff \abs{w}_a - \abs{w}_b \cong \abs{w'}_a - \abs{w'}_b \mod n, \] and its syntactic quotient is given by \[ \begin{tikzcd} \SQ({L_n})\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(\Z/n\Z). \end{tikzcd} \] \end{example} \begin{example}[Non-regular example] Let us consider the (non-regular) language $L_0\coloneqq \{w\mid \abs{w}_a = \abs{w}_b\}$, where $\abs{w}_\a$ (respectively, $\abs{w}_\b$) denotes the number of $\a$ (respectively $\b$) in the word $w$. Its Nerode congruence $\sim_{L_0}$ is given by \[ w\sim_{L_0} w' \iff \abs{w}_a - \abs{w}_b = \abs{w'}_a - \abs{w'}_b, \] which is regular, since it is fixed by the word action. Then, its syntactic quotient is given by \[ \begin{tikzcd} \SQ({L_0})\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(\Z). \end{tikzcd} \] \end{example} \begin{example} The geometric morphism $\Aset \to \mathbf{Cont}(\hat{F_{\A}})$ to the topos of continuous actions of the profinite completion of the free group on $\Sigma$ is hyperconnected. The corresponding class is the set of \demph{group languages} (\memo{cite}). \end{example} \begin{example} Similarly, in the case where $\A$ is a singleton, the geometric morphism $\Aset = \sigma\text{-}\Set \to \mathbf{Cont}(\mathbb{Z}_p)$ to the topos of continuous actions of the topological group of $p$-adic integers is hyperconnected. The corresponding class is the set of languages $L$ such that $L$ is periodic and its period is a power of $p$. \end{example} \begin{example} The geometric morphism $\Aset \to \sigma\text{-}\Set = \PSh(\N)$ to the topos of discrete dynamical systems (also known as difference sets), induced by the monoid homomorphism $\MA \to \N\colon w \mapsto (\text{the length of }w)$, is hyperconnected. The corresponding class is the set of \demph{length languages} $L$, which is a language $L$ such that if $w$ and $v$ have the same length and $w \in L$, then $v \in L$. \end{example} \begin{example} The geometric morphism $\Aset \to \Aset_{\mathrm{e.f.}}$ to the topos of eventually fixed $\A$-sets is hyperconnected. The corresponding class is the set of \demph{prefix languages} $L$, which is a language $L$ such that there exists a finite set of words $P$, and a word $w \in \MA$ belongs to $L$ if and only if at least one element of $P$ is a prefix of $w$. \end{example} \begin{example} \cite{lawvere1989display, pin2010mathematical} \end{example} \begin{example} Commutative language \end{example} \begin{example} Lattice \end{example} \begin{example}[Syntactic monoid] \end{example} \begin{table}[ht] \centering \begin{tabular}{c|c} $\E = \mathrm{cod}(h)$& $\Lan_h$\\ \hline $\Aset$& $\Lan$\\ \hline $\ofAset$&$\Reg$\\ \hline $\mathbf{Cont}(\hat{F_{\A}})$& Group languages\\ \hline $\sigma\text{-}\Set$ & Length languages\\ \hline $\Aset_{\mathrm{e.f.}}$&Prefix languages\\ \hline $\Set$&$\{\emptyset, \A\}$\\ \end{tabular} \caption{A few examples of associated classes} \label{TableExampleofHQcorrespondence} \end{table} \begin{example}[Regular languages: Profinite words in \cite{pin2010mathematical}, conceptually] Let $\ofAset$ be a full subcategory of $\Aset$ that consists of orbit-finite automata. Then the embedding $\ofAset\to \Aset$ has a right adjoint, and provides a hyperconnected geometric morphism $q\colon \Aset \to \ofAset$. A language $L$ is a $q$-language if and only if $L$ is regular! \end{example} \begin{example}[Group languages] Let $\pFA$ be the profinite completion of the free group $\FA$, equipped with the canonical profinite topology. Let $\mathrm{Cont}(\pFA)$ be the topos of continuous right $\pFA$ actions (see \cite{maclane1994sheaves}). Then, the dense monoid morphism $\MA \to \pFA$ induces a hyperconnected geometric morphism $q\colon \Aset \to \mathrm{Cont}(\pFA)$. A language $L$ is a $q$-language, if and only if $L$ is a group language. \end{example} \begin{conjecture} The lattice of hyperconnected quotients of $\ofAset$ is isomorphic to the lattice of \lvs of regular languages and finite $\A$-monoids \end{conjecture} \appendix \section{Language theory} \begin{lemma} For a regular language $L$, let $(Q, \delta, F, q_0)$ be its \end{lemma} \section{The Galois connection between hyperquotients and subalgebras} % Let $T$ be an equational theory \footnote{or just a functional language}. \begin{theorem}\label{thm:GaloisConnectionBetweenHQandSubalgebras} For a Grothendieck topos $\E$, an equational theory $T$, and an $\E$-internal $T$-algebra $A$, we obtain the following Galois connection \[ \ADJ{\HQ(\Aset)}{}{\Sub_T (A)}{}. \] \end{theorem} \begin{definition}\label{def:PerfectAlgebra} An internal $T$-algebra $A$ in a Grothendieck topos $\E$ is \demph{perfect}, if the Galois connection in \Cref{thm:GaloisConnectionBetweenHQandSubalgebras} is an equivalence of the complete lattices. \end{definition} \begin{example} Let $K/\Q$ be a finite-dimensional Galois extension of the field $\Q$. Then the field $K$ is an internal $\Q$-algebra in the topos $\PSh(\Gal(K/Q))$. Then, the Galois connection in \Cref{thm:GaloisConnectionBetweenHQandSubalgebras} is the equivalence between the lattice of normal subgroups of $\Gal(K/Q)$ and the lattice of sub-Galois-extensions $K/M/\Q$. This proves that $K \in \PSh(\Gal(K/\Q))$ is perfect. \memo{Similarly, by replacing $\Q$, we can construct perfect $T$-algebra for any finite-group action topos.} \end{example} \memo{Perfect algebra seems to be preserved by hyperconnected geometric morphism} % \section{Characterizing surjective monoid homomorphisms among hyperconnected geometric morphisms} \section{Surjective monoid homomorphisms are exactly essential and hyperconnected quotients} \begin{definition} A geometric morphism \[ \ADJ{\E}{f_*}{\F}{f^*} \] is essential, if $f^*$ has a left adjoint. \end{definition} \begin{fact} A full and bijective-on-objects functor $F\colon \C \to \D$ induces a hyperconnected and essential geometric morphism \[ \ADJ{\PSh(\C)}{\mathrm{Ran}_{F}}{\PSh(\D)}{ {-}\circ F}. \] Furthermore, this construction provides a one-to-one correspondence between \begin{itemize} \item (isomorphism classes of) full and bijective-on-objects functors $F\colon \C \to \D$ and \item (equivalence classes of) hyperconnected and essential geometric morphisms from $\PSh(\C)$. \end{itemize} \end{fact} \begin{proof} The first half is easy to prove and well-known. For example, you can find the details in \cite{johnstone2002sketchesv1}. For the latter, \cite{el2002simultaneously} proves that every essential and connected geometric morphism from $\PSh(\C)$ is induced by a bijective-on-objects (and lax-epi) functor $F\colon \C \to \D$. If the induced essential geometric morphism $\mathrm{Lan}_{F} \dashv {-}\circ F \dashv \mathrm{Ran}_{F}$ is hyperconnected, the unit $\C(-, c) \twoheadrightarrow \mathrm{Lan}_{F}(\C(-,c)) \circ F = \D(F{-}, Fc)$ is epic, which means that $F$ is full. \end{proof} \begin{proposition} There is a one-to-one correspondence between (equivalence classes of) \begin{enumerate} \item Hyperconnected and essential geometric morphism $h\colon \Aset \to \E$. \item Surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$. \item Two-sided congruence ${\sim}\in \Xi$. \end{enumerate} % Furthermore, for a language $L\in \Lan$, the following conditions are equivalent: % \begin{enumerate} % \item $h$ recognizes $L$, i.e., $L\in \LC(h)$. % \item $\phi$ recognizes $L$. % % Surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$. % \item ${\sim} \leq {\sim}_{L}\in \Xi$. % \end{enumerate} \end{proposition} \begin{remark}[Detail of the correspondence] Let us clarify the correspondence between them. Between (1) and (2), from (2) a surjective monoid homomorphism $\phi\colon \MA \to N$, the corresponding (1) Hyperconnected and essential geometric morphism is given by \[ \ADJ{\PSh(\MA)}{\mathrm{Ran}_{\phi}}{\PSh(N)}{ {-}\circ \phi}. \] The converse is a little more difficult\footnote{The monoid can be recovered as an endomorphism monoid of the forgetful functor $\E \to \Aset \to \Set$}. Between (2) and (3), from (2) we can define $w\sim v$ by $\phi(w)=\phi(v)$. The converse construction is just by considering the surjection $\MA \twoheadrightarrow N$. Between (1) and (3), from (1), the corresponding internal filter $F\subset \Xi$ has a minimum element ${\sim}\in \Xi$. Conversely, for a two-sided congruence ${\sim}$, its upward closure $\{{\sim'}\mid {\sim}\leq {\sim'}\}$ is an internal filter, and the corresponding hyperconnected geometric morphism to $F$, is what we want. \end{remark} % In particular, surjective monoid homomorphisms from $\MA$ are in one-to-one correspondence with hyperconnected and essential geometric morphism from $\Aset$. % \begin{proposition} % For a hyperconnected geometric morphism $h\colon \Aset\to \E$, the following conditions are equivalent: % \begin{enumerate} % \item $h$ is essential % \item There is a surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$ such that $h$ is (equivalent to) the geometric morphism induced by $\phi$ % \[ % \Aset = \PSh(\MA) \xrightarrow{\phi_{\ast}} \PSh(N). % \] % \item The corresponding internal filter $F \subset \Xi$ is principal, in the sense that there is a minimum element ${\sim} \in F$\footnote{This is not equivalent to the existence of the minimal \demph{global} element $1 \to F$, which should be the fixed point of the quotient-action.}. % % such that ${\sim} \leq {\sim'}$ for every ${\sim'}\in \Xi$ % \end{enumerate} % \end{proposition} \section{The Dyck language is not quasi-regular}\memo{Thanks to J\'er\'emie Marqu\`es} Let $\Dyck$ denote \demph{the Dyck language} for the alphabet $\A=\{\texttt{a,b}\}$, i.e., the language of all well-parenthesized words: \begin{align*} \Dyck \coloneqq&\{w\in \MA \mid \text{No prefix of $w$ contains $\b$ more than $\a$, and $w$ has the exactly same number of $\a$ and $\b$}.\}\\ =& \{\empword, \texttt{ab}, \texttt{aabb}, \texttt{abab}, \texttt{aaabbb}, \texttt{aababb}, \texttt{aabbab}, \texttt{abaabb}, \texttt{ababab}, \texttt{aaaabbbb}, \texttt{aaababbb}, \texttt{aaabbabb}, \dots\}, \end{align*} % \[ % \Dyck\coloneqq\{w\in \MA \mid \text{No prefix of $w$ contains $\b$ more than $\a$, and $w$ has the exactly same number of $\a$ and $\b$}.\} % \] % For example, $\Dyck$ contains $\empword, \texttt{ab}, \texttt{aabb}, \texttt{abab}, \texttt{aaabbb}, \texttt{aababb}, \texttt{aabbab}, \texttt{abaabb}, \texttt{ababab}, \texttt{aaaabbbb}, \dots$. which is alternatively defined as the context-free language generated by \[ S \to \epsilon\; |\;\texttt{a}S\texttt{b} S, \] % It is well known that the number of $\Dyck$-words with length $2n$ is the $n$-th Catalan number. or as the language recognized by the infinite automaton visualized in \Cref{fig:MinimalAutomatonOfDyck}. \begin{figure}[ht] \centering \begin{tikzpicture}[shorten >=1pt, node distance=2cm, on grid, auto] \node[state, accepting, initial] (c0) {$c_{0,0}$}; \node[state, right=of c0] (c1) {$c_{0,1}$}; \node[state, right=of c1] (c2) {$c_{0,2}$}; \node[state, right=of c2] (c3) {$c_{0,3}$}; \node[state, right=of c3] (c4) {$c_{0,4}$}; \node[state, right=of c4] (c5) {$c_{0,5}$}; \coordinate (dot) at ($(c5)+(2.5,0)$); \node at (dot) {$\cdots$}; % \node (dots) [right=of c5] {$\cdots$}; \node[state, below=of c0] (c*) {$c_{*}$}; \path[->] (c0) edge[bend left] node {\a} (c1) (c1) edge[bend left] node {\b} (c0) (c1) edge[bend left] node {\a} (c2) (c2) edge[bend left] node {\b} (c1) (c2) edge[bend left] node {\a} (c3) (c3) edge[bend left] node {\b} (c2) (c3) edge[bend left] node {\a} (c4) (c4) edge[bend left] node {\b} (c3) (c4) edge[bend left] node {\a} (c5) (c5) edge[bend left] node {\b} (c4) (c0) edge[] node {\b} (c*) (c*) edge [loop below] node {a,b} (c*) (c5) edge[bend left] node {\a} ($(c5)+(1.7,0.2)$) ($(c5)+(1.7,-0.2)$) edge[bend left] node {\b} (c5); \end{tikzpicture} \caption{The minimal automaton of $\Dyck$} \label{fig:MinimalAutomatonOfDyck} \end{figure} \begin{proposition} Let us consider two conditions on $\A$-sets $(Q, \delta)$: \begin{enumerate} \item $\forall q\in Q,\; q*ab=q$. \item $\forall q\in Q, \; \exists k\geq 0,\; q*b^k \text{ is a fixed point}$. \end{enumerate} Then the topos $\PSh(M_{\Dyck})$ is the category of all $\A$-sets satisfying the condition $(1)$, and the syntactic topos $\SQ(\Dyck)$ is the category of all $\A$-sets satisfying the condition $(1), (2)$. In particular, we have $\SQ(\Dyck) \subsetneq \PSh(\Dyck)$, and $\Dyck$ is not quasi-regular. \end{proposition} In order to describe the Nerode congruence $\xi_{\Lan}(\Dyck)$, let us introduce several quantities for words: \begin{itemize} \item For a word $w$, the number of $\a$ (respectively $\b$) in $w$ is denoted by $|w|_\a$ (respectively $|w|_\b$). \item For a word $w\in \MA$, its \demph{value} $\val(w) \in \Z$ is defnied by $\val(w) \coloneqq |w|_\a -|w|_\b$. \item For a word $w\in \MA$, its \demph{depth} $\dep(w)\in \N$ is defined by the maximal value of $-\val(u)$ among all prefixes $u$ of $w$. \end{itemize} For example, the value and depth of a word $w=\texttt{abbabbaaabaaaab}$ is visualized in \Cref{fig:ValueAndDepth}. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.5,>=stealth] % Draw grid \foreach \x in {0,...,14} { \foreach \y in {-3,...,4} { \draw[gray!30] (\x,\y) rectangle (\x+1,\y+1); } } \draw[blue, dashed] (0,0) -- (15,0); % \draw[blue, thick] (6,0) -- (6,-2) node[] {}; % \draw[blue] (6,-2) node[below] {$\dep(w)=2$}; \filldraw[blue] (6,-2) circle (5pt) node[right] {$\dep(w)=2$}; % \draw[blue, thick] (15,0) -- (15,3) node[] {}; % \draw[blue] (15,3) node[right] {$\val(w)=3$}; \filldraw[blue] (15,3) circle (5pt) node[right] {$\val(w)=3$}; % Draw arrows with labels \draw[->,thick] (0,0) -- (1,1) node[midway, above] {\texttt{a}}; \draw[->,thick] (1,1) -- (2,0) node[midway, below] {\texttt{b}}; \draw[->,thick] (2,0) -- (3,-1) node[midway, below] {\texttt{b}}; \draw[->,thick] (3,-1) -- (4,0) node[midway, above] {\texttt{a}}; \draw[->,thick] (4,0) -- (5,-1) node[midway, below] {\texttt{b}}; \draw[->,thick] (5,-1) -- (6,-2) node[midway, below] {\texttt{b}}; \draw[->,thick] (6,-2) -- (7,-1) node[midway, above] {\texttt{a}}; \draw[->,thick] (7,-1) -- (8,0) node[midway, above] {\texttt{a}}; \draw[->,thick] (8,0) -- (9,1) node[midway, above] {\texttt{a}}; \draw[->,thick] (9,1) -- (10,0) node[midway, below] {\texttt{b}}; \draw[->,thick] (10,0) -- (11,1) node[midway, above] {\texttt{a}}; \draw[->,thick] (11,1) -- (12,2) node[midway, above] {\texttt{a}}; \draw[->,thick] (12,2) -- (13,3) node[midway, above] {\texttt{a}}; \draw[->,thick] (13,3) -- (14,4) node[midway, above] {\texttt{a}}; \draw[->,thick] (14,4) -- (15,3) node[midway, below] {\texttt{b}}; % Draw nodes \foreach \p in {(0,0),(1,1),(2,0),(3,-1),(4,0),(5,-1),(6,-2), (7,-1),(8,0),(9,1),(10,0),(11,1),(12,2),(13,3), (14,4), (15,3)} { \filldraw[black] \p circle (2pt); } \end{tikzpicture} \caption{Value and depth of a word $w=\texttt{abbabbaaabaaaab}$} \label{fig:ValueAndDepth} \end{figure} The definition of the Dyck language is rephrased by \[\Dyck =\{w\in \MA \mid \val(w)=0, \dep(w)=0\}.\] The equivalence classes by the Nerode congruence $\xi_{\Lan}(\Dyck)$ are \begin{align*} d_{0}=&\{w\in \MA\mid \dep(w)>0\},\\ c_{0,0}=&\{w\in \MA\mid \dep(w)=0, \val(w)=0\},\\ c_{0,1}=&\{w\in \MA\mid \dep(w)=0, \val(w)=1\},\\ c_{0,2}=&\{w\in \MA\mid \dep(w)=0, \val(w)=2\},\\ & \vdots\\ c_{0,n}=&\{w\in \MA\mid \dep(w)=0, \val(w)=n\},\\ & \vdots \end{align*} and hence its minimal automaton is given by \Cref{fig:MinimalAutomatonOfDyck}. If a word $w$ satisfies $\dep(w)>0$, then the congruence $\xi_{\Lan}(\Dyck)*w$ is trivial \[ \xi_{\Lan}(\Dyck)*w= \top \in \Xi. \] If $\dep(w)=0$, then the equivalence classes of the congruence $\xi_{\Lan}(\Dyck)*w$ are described using $k\coloneqq \val(w)\geq 0$ as follows: \begin{align*} d_{k}=&\{w\in \MA\mid \dep(w)>k\},\\ c_{k,-k}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=-k\},\\ c_{k,-k+1}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=-k+1\},\\ & \vdots\\ % c_{k,0}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=0\},\\ % c_{k,1}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=1\},\\ % & \vdots\\ c_{k,n}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=n\},\\ & \vdots \end{align*} We write $\sim_k$ for the above congruence, which is visualized as \Cref{fig:ActedcongruenceforKequalFive}. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.4] % fill light blue background where x >= 6 and x+y >= 0 using a trapezoid \fill[blue!20] (6,-6) -- (6,9.3) -- (9.3,9.3) -- (9.3,-9.3) -- cycle; \draw (10,10) node[right, blue] {$d_{5}$}; % draw axes \draw[->] (-1,0) -- (10,0) node[right] {$\dep(w)$}; \draw[->] (0,-9) -- (0,10) node[above] {$\val(w)$}; % fill vertical red strips for each n >= -8 along x=0 \foreach \n in {-5,...,9} { \pgfmathsetmacro{\xmin}{max(0, -\n)} \fill[red!20] (5.2, \n+0.2) rectangle (\xmin-0.2, \n-0.2) node[left, red] {$c_{5,\n}$}; } % draw grid points where x \geq 0 and y \geq -x, within x,y \in [-8,8] \foreach \x in {0,...,9} { \foreach \y in {-\x,...,9} { \fill (\x,\y) circle (3pt); } } \end{tikzpicture} \caption{The congruence for $k=5$} \label{fig:ActedcongruenceforKequalFive} \end{figure} The syntactic congruence $\cong_\Dyck$ is given by ${\cong_\Dyck}=\bigwedge_{k\geq 0} {\sim_k}$, which is explicitly written down as \[ u\cong_\Dyck v \iff \text{$\dep(u)=\dep(v)$ and $\val(u)=\val(v)$.} \] \memo{cite the paper that describes the syntactic monoid of the Dyck language} We will prove that $\Dyck$ does not satisfy the equivalent conditions in \Cref{lem:SufficientAndNecessaryConditionForSyntacticMonoidGivesSyntacticTopos} by proving \[{\cong_\Dyck}<\bigwedge_{k\geq 0}^n {\sim_k}\] for any $n\geq0$. This follows since we have \[ u \mathrel{\left (\bigwedge_{k\geq 0}^n {\sim_k}\right )} v \iff (\dep(u),\dep(v)>n) \lor (\dep(u)=\dep(v) \land \val(u)=\val(v)). \] \memo{Its syntactic prodiscrete monoid is given by $\MA/{\cong_\Dyck}\sqcup \{b^{\infty}a^{?}\}$, where $b^{\infty}a^{?}$ denotes the formally added absorbing element which has $\{d_k/{\cong_\Dyck}\subset \MA/{\cong_\Dyck}\}_{k\geq 0}$ as a fundamental system of open subsets.} \printbibliography \end{document}