Agent-assistance disclosure: this work was prepared with AI-agent assistance (drafting, code, experiments) under human direction. The authors, writing as Third Projection Collective, take responsibility for its content. Open proofs are marked [OPEN] in the text.
\begin{document}\maketitle \begin{abstract} Patterson showed that the comprehensive factorization of Street and Walters restricts to categories with finite products. This gives an initial-functor semantics for e-graphs over algebraic theories. He remarked that the factorization will not directly extend to finite limits. We prove that, for \emph{finitely complete} domains, it does: the (initial, discrete opfibration) factorization restricts to an orthogonal factorization system on the category $\Lex$ of small finitely complete categories and finite-limit-preserving functors. The key facts are that the classifying copresheaf $\pi_0(F\downarrow -)$ is a filtered colimit of representables whenever the domain is finitely complete, \emph{regardless} of whether $F$ is lex, and that lex discrete opfibrations are exactly the categories of elements of lex copresheaves. $\Lex$ is not a full subcategory of $\mathbf{Cat}$, so the restriction criterion of Berger and Kaufmann for full replete subcategories does not apply as stated. We give counterexamples showing finite completeness of the domain is needed. We also show what this does and does not give for an e-graph calculus over essentially algebraic theories. A finite presentation calculus, and the $(\infty,1)$-version sketched in a recent note, remain \emph{open}. \end{abstract}
\section{Introduction}
Patterson~\cite{patterson2,patterson3} proposes initial functors as the operational semantics of e-graphs. Diagrams related by initial functors have the same limits. The ideal e-diagram of a diagram $D$ is its comprehensive factorization~\cite{sw73}. Part~3~\cite{patterson3} proves the factorization restricts to $\mathbf{Cart}$ and remarks that it will not directly extend from categories with finite products to categories with all finite limits''. A note on higher e-graphs~\cite{hcsEG} (Corollary 7.3) states that both factors are lex for lex $F$ between finitely complete categories, but proves neither orthogonality in $\Lex$ nor the converse direction needed for it. We give complete 1-categorical proofs.
\paragraph{Contributions.} Lemma~\ref{lem:flat} (the classifier is lex for any $F$ out of a finitely complete category); Lemma~\ref{lem:elts} (lex discrete opfibrations correspond to lex copresheaves and create finite limits); Theorem~\ref{thm:ofs} (an orthogonal factorization system on $\Lex$); Examples~\ref{ex:need} and~\ref{ex:F}, which delimit the hypotheses; and Section~\ref{sec:egraph}, an honest account of consequences for e-graphs.
\paragraph{Conventions.} $F:C\to D$ is \emph{initial} if every comma category $F\downarrow d$ (objects $(c,\,Fc\to d)$) is non-empty and connected. This is the convention under which pulling back along $F$ preserves limits. Discrete opfibrations over $D$ are equivalent to copresheaves $Y:D\to\Set$ via $\El(Y)$. The comprehensive factorization of $F$ is $C\xrightarrow{E}\El(Y_F)\xrightarrow{\pi}D$ with $Y_F=\mathrm{Lan}_F 1\cong\pi_0(F\downarrow -)$~\cite{sw73}.
\section{Results} \begin{lemma}\label{lem:flat} If $C$ is small and finitely complete and $F:C\to D$ is any functor, then $Y_F$ preserves finite limits. \end{lemma} \begin{proof} By the coend formula, $Y_F=\mathrm{Lan}_F1\cong\mathrm{colim}_{c\in C^{op}}D(Fc,-)$, the colimit indexed by $\El(1)^{op}=C^{op}$~\cite[X.4]{maclane}. $C^{op}$ is filtered: it is non-empty (it has the terminal object of $C$); two objects have a common cocone, namely their product in $C$; and two parallel arrows $f,g:b\to a$ of $C$ are equalized by $e:\mathrm{eq}(f,g)\to b$, which in $C^{op}$ coequalizes them. Each $D(Fc,-)$ preserves all limits, and filtered colimits commute with finite limits in $\Set$~\cite[IX.2]{maclane}. So $Y_F$ preserves those finite limits that exist in $D$. \end{proof}
\begin{lemma}\label{lem:elts} Let $D$ be finitely complete and $Y:D\to\Set$. Then: (i) if $Y$ is lex, $\El(Y)$ is finitely complete and $\pi:\El(Y)\to D$ creates finite limits; (ii) if $\El(Y)$ is finitely complete and $\pi$ is lex, then $Y$ is lex. \end{lemma} \begin{proof} (i) Let $(d_j,y_j)_{j}$ be a finite diagram in $\El(Y)$ with limit cone $p_j:d\to d_j$ in $D$. Since $Y(d)\cong\lim Y(d_j)$ via the $Y(p_j)$, there is a unique $y\in Y(d)$ with $Y(p_j)(y)=y_j$. Given a cone $(e,z)\to(d_j,y_j)$, the induced $h:e\to d$ satisfies $Y(p_j)(Y(h)z)=y_j$, hence $Y(h)z=y$. So $h$ is a morphism of $\El(Y)$, unique because $\pi$ is faithful. Every cone over the diagram that $\pi$ sends to a limit cone has its apex determined in this way, so $\pi$ creates the limit. (ii) Let $t$ be terminal in $\El(Y)$; then $\pi t=1$. For $y\in Y(1)$ the unique map $(1,y)\to t$ lies over $\mathrm{id}_1$, so $y$ equals the element $y_t\in Y(1)$ carried by $t$, so $Y(1)$ is a singleton. For a pullback $d=d_1\times_{d_0}d_2$ in $D$ and $(y_1,y_2)\in Y(d_1)\times_{Y(d_0)}Y(d_2)$, the cospan $(d_1,y_1)\to(d_0,y_0)\leftarrow(d_2,y_2)$ has a pullback $(d',y')$ in $\El(Y)$. Its image is a pullback since $\pi$ is lex, so $d'\cong d$, and $y'$ maps to $(y_1,y_2)$: this proves surjectivity of $Y(d)\to Y(d_1)\times_{Y(d_0)}Y(d_2)$. For injectivity, two elements $y,y'\in Y(d)$ with the same images give two cones over the cospan with apexes $(d,y),(d,y')$ and legs over the projections. Both factor through the pullback $(d,y'')$ by maps over $\mathrm{id}_d$, so $y=y''=y'$. \end{proof}
\begin{theorem}\label{thm:ofs} Let $\mathcal E$ be the lex initial functors and $\mathcal M$ the lex discrete opfibrations, both in $\Lex$. Then $(\mathcal E,\mathcal M)$ is an orthogonal factorization system on $\Lex$, and the factorization of a lex $F$ is its comprehensive factorization. \end{theorem} \begin{proof} \emph{Factorization.} Let $F:C\to D$ be lex. By Lemma~\ref{lem:flat}, $Y_F$ is lex, so by Lemma~\ref{lem:elts}(i) $\El(Y_F)$ is finitely complete and $\pi$ is lex and creates finite limits. $E$ is lex: for a finite limit cone $\lambda$ in $C$, $\pi E\lambda=F\lambda$ is a limit cone, and $\pi$ creates (hence reflects) limits. $E$ is initial~\cite{sw73}. \emph{Orthogonality.} Let $e:A\to B$ be in $\mathcal E$, $p:X\to Z$ in $\mathcal M$, and $u:A\to X$, $v:B\to Z$ lex with $pu=ve$. By the comprehensive factorization system on $\mathbf{Cat}$~\cite{sw73} there is a unique functor $h:B\to X$ with $he=u$ and $ph=v$. Write $X\simeq\El(Y)$ with $Y$ lex by Lemma~\ref{lem:elts}(ii). Then $p$ reflects finite limits by Lemma~\ref{lem:elts}(i). For a finite limit cone $\lambda$ in $B$, $ph\lambda=v\lambda$ is a limit cone, so $h\lambda$ is one: $h$ is lex. Uniqueness holds already in $\mathbf{Cat}$. \emph{Closure.} Both classes contain isomorphisms and are closed under composition (as they are in $\mathbf{Cat}$, and lex functors compose). This together with unique factorization and orthogonality gives an OFS. \end{proof}
\begin{remark} Berger and Kaufmann~\cite{bk17} (Definition 1.13 and Lemma 1.1) give a criterion for a comprehension scheme to restrict to a full replete subcategory of the ambient category. $\Lex$ has the same objects as the finitely complete part of $\mathbf{Cat}$ but fewer morphisms, so their criterion does not apply verbatim. Theorem~\ref{thm:ofs} supplies the missing argument, namely that the classifier is lex and that the filler is lex. We do not claim the result is unknown to experts; we were unable to find it stated in the literature. \end{remark}
\begin{example}\label{ex:need} Finite completeness of the domain is needed in Lemma~\ref{lem:flat}. Let $C=\{a,b\}$ be discrete, $D=1$, and $F$ the unique functor. Then $Y_F(*)=\pi_0(C)$ has two elements, so $Y_F$ does not preserve the terminal object. \end{example} \begin{example}\label{ex:F} Lemma~\ref{lem:flat} does not need $F$ to be lex, but Theorem~\ref{thm:ofs} does: the factor $E$ is lex iff $F=\pi E$ is, since $\pi$ creates finite limits. For instance, take $C=1$ and $F:1\to D$ picking a non-terminal object $d_0$. Then $Y_F=D(d_0,-)$ is lex, but $E$ is not. \end{example}
\section{What this gives e-graphs}\label{sec:egraph} A model of an essentially algebraic theory presented by a small finitely complete $T$ is a lex functor $T\to\Set$. Limits of an arbitrary finite diagram $D:J\to T$ are preserved by restriction along initial functors in any category, so Patterson's rules are already \emph{sound} for diagrams in $T$. Theorem~\ref{thm:ofs} adds that, for lex diagrams $D:J\to T$ with $J$ finitely complete, the ideal e-diagram stays inside $\Lex$. Every intermediate category is finitely complete and every intermediate map preserves the partial-operation structure. The difficulty Patterson points to is real at a different place: free finitely complete categories on finite data are infinite, so lex diagrams are not finite data structures. \todo{OPEN: a finite presentation of lex e-diagrams (for instance via finite limit sketches with flat completion) with a terminating saturation procedure; a worked example such as the theory of categories.} \todo{OPEN: the $(\infty,1)$-categorical version, i.e.\ restriction of the initial/left-fibration factorization to finitely complete $\infty$-categories; the note~\cite{hcsEG} sketches the factor computation but not orthogonality.}
\section{Conclusion} For finitely complete domains the comprehensive factorization restricts to $\Lex$. The lex classifier comes for free from filteredness, and the filler is lex because lex discrete opfibrations create limits. Agent assistance: drafted with an AI agent under human direction; the authors (Third Projection Collective) are responsible for the content. \bibliographystyle{eptcs}\bibliography{refs} \end{document}