<style type="text/css"> .reveal ul { display: block; } .reveal ol { display: block; } .reveal { font-size: 30px; } .reveal p { text-align: left; margin-top: 25px; margin-bottom: 25px; /* Adjust the value as needed */ } .custom-space { display: block; margin-top: 50px; /* Less space than <br> */ } .reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6 { text-transform: none; /* no forced upper case in headings*/ } .reveal .slides section h1:after, /* not doing much*/ .reveal .slides section h2:after, .reveal .slides section h3:after { content: ''; flex-grow: 1; /* This will make the pseudo-element grow */ display: block; /* Converts the pseudo-element to a block, allowing it to be sized */ } </style> ## Canonical Extensions of Quantale-Enriched Categories <br> #### TACL, July 4, 2024 <br> ###### Alexander Kurz ###### Chapman University <br> ###### jww Apostolos Tzimoulis (Vrije Universiteit van Amsterdam) <br> --- ###### <font color=grey>(this page is empty)</font> $$\newcommand{\cont}{{\bf I}}$$ --- ### Motivation - Many-valued logic ( -> quantales) - Formal context canalysis ( -> MacNeille completion) - Modal logic over formal contexts ( -> canonical extension) --- ### Complete Lattices "Incidence" relation $\cont:X\times A\to 2$. $\cont^\uparrow:\mathcal DX\to\mathcal UA\quad$, $\quad\cont^\uparrow(\phi)=\{a\in A \mid \color{blue}{\forall x\in X\,.\, x\in\phi \Rightarrow \cont(x,a)}\}$ $\cont^\downarrow:\mathcal UA\to\mathcal DX\quad$, $\quad\cont^\downarrow(\psi)=\{x\in X \mid \color{blue}{\forall a\in A \,.\, \cont(x,a) \Leftarrow a\in\psi} \}$ <span class="custom-space"></span> Rewrite this as $\cont^\uparrow(\phi) \ =\ \bigwedge_x (\,\phi(x)\Rightarrow \cont(x,-)\,) \ =\ \color{blue}{\phi\blacktriangleright \cont}$ $\cont^\downarrow(\psi) \ =\ \bigwedge_a(\, \cont(-,a) \Leftarrow \psi(a)\,) \ =\ \color{blue}{\cont\blacktriangleleft \psi}$ --- ### MacNeille Completionasdfasdf The following is sometimes known as the Isbell adjunction: $$ \cont^\uparrow\dashv \cont^\downarrow $$ Order-enriched: $\cont^\uparrow \cont^\downarrow$ and $\cont^\downarrow \cont^\uparrow$ are closure operators. The **MacNeille completion** $\mathcal M(I)$ is the set of fixed points $$(\phi,\psi),$$ that is, $$\color{blue}{\phi\blacktriangleright\cont} = \psi \quad\quad\quad\quad \phi = \color{blue}{\cont\blacktriangleleft\psi}$$ --- ## Enriching over a Quantale A quantale is a monoid $(\Omega,e,\cdot)$ in the category of sup-lattices. $$ b\,\sqsubseteq\, \color{blue}{a\rhd c} \quad \Leftrightarrow \quad a \cdot b \,\sqsubseteq\, c \quad \Leftrightarrow \quad a\,\sqsubseteq\, \color{blue}{c\lhd b} $$ <span class="custom-space"></span> **Example**: The Lawvere Quantale. **Example**: The quantale of all languages. **Example**: The quantale of all binary relations on a set. **Example**: Relational presheaves for an arbitrary quantale. <span class="custom-space"></span> We call an **$\Omega$-space** a category enriched over a quantale $\Omega$. --- ## Non-Commutative Quantales Define $\Omega^o$ to be $\Omega$ with reverse multiplication. For an $\Omega$-space $X$ define $X^o(x,y) = X(y,x)$. **Fact:** $\ X^o$ is $\Omega^o$-enriched iff $X$ is $\Omega$-enriched. Intuitively, a **relation** should be a functor $R:X^o\otimes A\to \Omega$. **Def:** An **$\Omega$-relation** $\color{blue}{R: X\looparrowright A}$ is a function $X\times A\to\Omega$ s.t. $$X(x',x)\cdot R(x,y)\sqsubseteq R(x',y)$$ $$R(x,y)\cdot Y(y,y')\sqsubseteq R(x,y')$$ <font size=5pt color=grey>(aka bimodule, profunctor, distributor, weakening relation, monotone relation, ...) </font> --- ## Weighted Relations and Implications <br> $$(R\bullet S)(x,z)=\bigvee_{y\in Y}R(x,y)\cdot S(y,z).$$ Weighted implications $\blacktriangleright$ and $\blacktriangleleft$ are defined as residuals $$R\bullet - \ \dashv\ \color{blue}{R\blacktriangleright - }\quad\quad\quad - \bullet S\ \dashv \ \color{blue}{-\blacktriangleleft S}$$ which implies \begin{gather} R\bullet (R\blacktriangleright T) \,\le \, T \quad\quad T\le R\blacktriangleright (R\bullet T) \\[1ex] (T\blacktriangleleft S)\bullet S \,\le\, T \quad\quad T \,\le\, (T\bullet R)\blacktriangleleft R \end{gather} --- ## Weighted Downsets and Upsets <span class="custom-space"></span> The elements of $\mathcal DX$ (presheaves) are $\Omega$-relations $X\looparrowright 1$ with homs $$\color{blue}{\mathcal DX(\phi',\phi)}=\phi'\blacktriangleright\phi =\bigwedge_{x\in X} (\phi' x\rhd \phi x)$$ The elements of $\mathcal UA$ (co-presheaves) are $\Omega$-relations $1\looparrowright A$ with homs $$\color{blue}{\mathcal UA(\psi,\psi')}=\psi \blacktriangleleft \psi'=\bigwedge_{a\in A} (\psi a\lhd \psi' a)$$ --- ## Weighted Limits and Colimits <span class="custom-space"></span> $G:D\to B$, $\phi\in\mathcal DD$, $\psi\in\mathcal UD$. <span class="custom-space"></span> The weighted colimit ${\rm colim}_\phi\,G$ is the solution of \begin{gather*} B(\color{blue}{{\rm colim}_\phi G},b) = \phi\blacktriangleright B(G,b) \end{gather*} <span class="custom-space"></span> The weighted limit ${\rm lim}_\psi G$ is the solution of \begin{gather*} B(b, \color{blue}{{\rm lim}_\psi G}) = B(b,G)\blacktriangleleft\psi \end{gather*} <span class="custom-space"></span> $B\to\mathcal DB$ preserves limits, $B\to\mathcal UB$ preserves colimits. $\mathcal UB$ ($\mathcal DB$) is the free (co)completion of $B$ with weighted (co)limits. --- ### MacNeille Completion  --- ### Algebra of Weighted Relations (Examples) $$(\phi\blacktriangleright \cont)\blacktriangleleft \psi = \phi\blacktriangleright (\cont \blacktriangleleft \psi)$$ $$X(-,x)\blacktriangleright \cont = \cont(x,-)$$ $$\cont \blacktriangleleft A(a,-) = \cont(-,a)$$ $$(\cont\blacktriangleleft \cont(x,-)) \blacktriangleright \cont=\cont(x,-)$$ $$\cont\blacktriangleleft (\cont(-,a) \blacktriangleright \cont)=\cont(-,a)$$  --- ## The MacNeille Insertion <span class="custom-space"></span> $$\overline\ : X+A\to \mathcal M$$ <span class="custom-space"></span> $$\mathcal M(\overline x,\overline a) = \cont(x,a)$$ $$\mathcal M(\overline a, \overline a') = \cont(-,a)\blacktriangleright \cont(-,a')$$ $$\mathcal M(\overline x,\overline x') = \cont(x,-)\blacktriangleleft \cont(x',-)$$ $$\mathcal M(\overline a,\overline x) = \cont(-,a) \blacktriangleright \cont\blacktriangleleft \cont(x,-)$$ <span class="custom-space"></span> <font size=5pt color=grey>(These formulas show how the distance $\cont(x,a)$ determines all other distances in $\cal M$.) </font> --- ## The MacNeille Yoneda Lemma <br> \begin{gather} \mathcal M(\overline x, (\phi,\psi)) = \cont(x,-)\blacktriangleleft\psi = \phi(x)\\ \mathcal M((\phi,\psi),\overline a) = \phi\blacktriangleright \cont(-,a) = \psi(a) \end{gather} <br> <font size=5pt color=grey>(These formulas compute distances from $x$ and distances to $a$ with the Yoneda lemma.) </font> --- ## Weighted (Co)Limit Completion <span class="custom-space"></span> The colimit of $\ \overline\ :X\to\mathcal M$ weighted by $\phi$ is the upset of $\phi$ $$\phi\blacktriangleright \cont$$ <span class="custom-space"></span> The limit of $\ \overline\ :A\to\mathcal M$ weighted by $\psi$ is the downset of $\psi$ $$\cont\blacktriangleleft \psi$$ <span class="custom-space"></span> **Corollary:** $\mathcal M$ is complete. $X$ and $A$ are dense in $\cal M$: every $(\phi,\psi)$ is - the colimit of $X\to\mathcal M$ weighted by $\phi$, - the limit of $A\to\mathcal M$ weighted by $\psi$. --- ## Canonical Extension $C^\delta$ <br>  ---  **Theorem (compactness):** $C^\delta(\lim_f [-],{\rm colim}_{i}[-])=\cont (f,i).$ <font size=5pt color=grey>(In the case of 2-valued logic this property reads $\bigwedge f \le \bigvee i\ \Rightarrow \ f\cap i \not=\emptyset$.) </font> --- ## Selected References <span class="custom-space"></span> <font size=5pt> 1. F.W. Lawvere. Metric spaces, generalized logic and closed categories. 1973. 1. R. Betti and S. Kasangian. A quasi-universal realization of automata, 1982. 1. Jan Rutten. Weighted colimits and formal balls in generalized metric spaces. 1998. 1. Isar Stubbe. Categorical structures enriched in a quantaloid. 2005. 1. Dusko Pavlovic. Quantitative concept analysis. 2012. 1. Simon Willerton. Tight spans, Isbell completions and semi-tropical modules. 2013. 1. Richard Garner. Topological functors as total categories. 2014. 1. Soichiro Fujii. Completeness and injectivity. 2021. 1. J. Michael Dunn, Mai Gehrke, Alessandra Palmigiano. Canonical extensions and relational completeness of some substructural logics. 2005. </font> <span class="custom-space"></span> <font size=4pt color=grey> [1]: generalized metric spaces as enriched categories; [2]: automata as categories enriched over the quantale of languages; [3] weighted limits and colimits in metric spaces; [4]: quantale-enriched category theory; [5]: quantale-enriched generalizations of formal concept analysis; [6]: MacNeille completion of metric spaces; [7,8]: MacNeille completions of quantale-enriched categories; [9]: canonical extensions of posets. </font> --- ## Ongoing and Future Work <span class="custom-space"></span> Expanding canonical extensions with modal operators (AiML) Proof theory (jww Giuseppe Greco) Applications to many-valued (fuzzy) formal concept analysis (FCA) Category theory of quantale-enriched FCA (duality theory) Applications to logic (completeness) Relation algebra of weighted relations Axiomatizing double categories of weighted relations