\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz-cd}
\usepackage{cleveref}
\usepackage[style=alphabetic,sorting=nyt]{biblatex}
\renewbibmacro{in:}{}
\addbibresource{CommonBiblio20240922.bib}

\theoremstyle{plain}
\newtheorem{proposition}{Proposition}[section]
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{fact}[proposition]{Fact}

\theoremstyle{definition}
\newtheorem{example}[proposition]{Example}
\newtheorem{definition}[proposition]{Definition}
\newtheorem{remark}[proposition]{Remark}

\newcommand{\C}{\mathcal{C}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\Lan}{\mathcal{L}}
\newcommand{\LC}{\mathbb{L}}
\newcommand{\SQ}{\mathcal{T}}
\newcommand{\HQ}{\mathrm{HQ}}
\newcommand{\Filt}{\mathrm{Filt}}
\newcommand{\A}{\Sigma}
\newcommand{\MA}{{{\Sigma}^{\ast}}}
\newcommand{\Aset}{\A\text{-}\Set}
\newcommand{\of}{\mathrm{o.f.}}
\newcommand{\ofAset}{{\Aset}_{\of}}
\newcommand{\demph}[1]{\textit{\textbf{#1}}}

\title{Topoi of automata II: Hyperconnected geometric morphisms and syntactic topoi}
\author{Ryuya Hora}
\thanks{ZEN University. \url{ryuya_hora@zen.ac.jp}}
\date{}
\subjclass[2020]{18F10, 68Q70, 18B20}
\keywords{Automaton, topos, language, hyperconnected geometric morphism, local state classifier}

\begin{document}
\begin{abstract}
For a hyperconnected geometric morphism from the topos of $\A$-sets, we formulate language recognition using the local state classifier. For a language class $C$, we construct the associated syntactic Grothendieck topos $\SQ(C)$.
\end{abstract}
\maketitle

\begin{center}
\emph{Prepreprint v0.1 (15 August 2026). This work is in progress and does not constitute the complete version of the project. The present public version contains only the part that does not require further mathematical observations.}
\end{center}

\tableofcontents

\section{Introduction}

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 work considers other hyperconnected geometric morphisms
\[
\begin{tikzcd}
&\E\\
    \Aset \ar[r]\ar[ru]\ar[rd] & \F\\
    & \mathcal{G}
\end{tikzcd}
\]
and their associated classes of languages.

\section{Hyperconnected geometric morphisms from \texorpdfstring{$\Aset$}{A-Set}}

\subsection{Hyperconnected geometric morphisms}

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{Local state classifiers}

We recall the description of $\HQ(\E)$ given in \cite{hora2024internal}.

\begin{definition}
We adopt the following definitions:
\begin{itemize}
    \item A \demph{local state classifier} of a category $\C$ is the colimit of all monomorphisms
    \[
    \Xi \coloneqq \mathop{\mathrm{colim}}\left(\C_{\mathrm{mono}}\to \C\right),
    \]
    where $\C_{\mathrm{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$, 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}

\subsection{The local state classifier of \texorpdfstring{$\Aset$}{A-Set}}

This section describes the local state classifier of the topos $\Aset$.

\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 that $u\sim v$ implies $u\sim'v$ for any $u,v \in \MA$.
    \item The poset of all right 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$ if and only if $wu \sim wv$.
\end{itemize}
\end{definition}

\begin{proposition}
We have the following properties:
\begin{itemize}
    \item These data make $\Xi$ 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 \quad\Longleftrightarrow\quad 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 its Nerode congruence $\sim_{L}$, where
\[
u \sim_{L} v \quad\Longleftrightarrow\quad u^{-1}L = v^{-1}L.
\]
\end{lemma}

\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$ contains the trivial equivalence and is closed under finite intersections:
    \[
    \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'} \Longrightarrow {\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}

\section{Language recognition and syntactic topoi}

\subsection{Language recognition by a hyperconnected geometric morphism}

\begin{proposition}[Equivalent definitions of recognition]
\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$.
    \item The corresponding filter $F_h$ contains the Nerode congruence $\sim_L$ of $L$.
\end{enumerate}
\end{proposition}

\begin{proof}
By \Cref{fact:LSCClassification}, we have the 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.
\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$ is denoted by $\LC_h$.
\end{definition}

The set $\LC_h$ is the sub-$\A$-set $\LC_h=h^*h_*\Lan\rightarrowtail\Lan$ constructed by the pullback diagram
\[
\begin{tikzcd}
    \LC_h=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}
\]

\subsection{The syntactic Grothendieck topos associated with a language class}

\begin{definition}
\label{def:LanguageClass}
A \demph{language class} is a subset $C \subset \Lan$ of the set of languages $\Lan$.
\end{definition}

\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}

For a language $L\in \Lan$, we call $\SQ(\{L\})$ the syntactic topos of $L$ and write $\SQ(L)$ for $\SQ(\{L\})$ when no confusion can arise.

\begin{remark}[$\SQ(C)$ is a geometric morphism]
Rigorously speaking, $\SQ(C)$ is not just a topos, but a topos equipped with the canonical hyperconnected geometric morphism $h\colon \Aset \twoheadrightarrow \SQ(C)$.
\end{remark}

\begin{lemma}
For any family of right congruences $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$, there exists a minimum internal filter that contains ${\sim}_{\lambda}$ for every $\lambda \in \Lambda$.
\end{lemma}

\begin{proof}
Since an internal filter is defined by closure properties listed in \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{proposition}[Filter corresponding to $\SQ(C)$]
\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 by
\[
F_C=\langle \xi_{\Lan}(L)\mid L\in C\rangle.
\]
\end{proposition}

\begin{proof}
By \Cref{prop:EquivRecognitionOfLnagByHyperconnected}, the corresponding filter $F_C$ is the minimum internal filter that contains $\xi_{\Lan}(L)$ for every $L\in C$.
\end{proof}

\section*{Acknowledgements}

This work was supported by JSPS KAKENHI Grant Numbers JP24KJ0837 and JP26K24500.

\printbibliography

\end{document}