<style type="text/css"> .reveal ul { display: block; } .reveal ol { display: block; } .reveal { font-size: 36px; } .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> ## The Blacktriangle Calculus <br> #### 1st GALAI Workshop, Jan 26, 2024 <br> ###### Alexander Kurz ###### Chapman University <br> ###### in collaboration with Apostolos Tzimoulis (Vrije Universiteit van Amsterdam) <br> --- ### Complete Lattices Relation $p:X\times A\to 2$. $p^\uparrow:\mathcal DX\to\mathcal UA$, $p^\uparrow(\phi)=\{a\in A \mid \forall x\in\phi\,.\, p(x,a)\}$ $p^\downarrow:\mathcal UA\to\mathcal DX$, $p^\downarrow(\psi)=\{x\in X \mid \forall a\in\psi\,.\, p(x,a) \}$ <span class="custom-space"></span> Rewrite this as $p^\uparrow(\phi)=\bigwedge_x (\phi(x)\Rightarrow p(x,-)) = \phi\blacktriangleright p$ $p^\downarrow(\psi)=\bigwedge_a(\psi(a)\Rightarrow p(-,a)) = p\blacktriangleleft \psi$ --- ### Complete Lattices (2) <span class="custom-space"></span> **Example:** Let $X=\{x_1,x_2,x_3\}$ and $A=\{a_1,a_2,a_3\}$ and $p=\{(x_1,a_1),(x_2,a_1), (x_2,a_2), (x_3,a_3)\}$ Order $\mathcal DX$ by inclusion and $\mathcal UA$ by reverse inclusion. **Fact:** $p^\uparrow\dashv p^\downarrow$. Hence, $p^\uparrow p^\downarrow$ and $p^\downarrow p^\uparrow$ are closure operators. The **MacNeille completion** of $p$ is the set $\mathcal P$ of all $(\phi,\psi)$ with $$\phi=p^\downarrow \psi \quad\quad p^\uparrow\phi=\psi$$ --- ## Enriching over a Quantale <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> An **$\Omega$-space** is a category enriched over a quantale $\Omega$. --- ## Non-Commutative Quantales <span class="custom-space"></span> Let $\Omega$ be a quantale. 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. An **$\Omega$-relation** $R: X\looparrowright A$ is a function $X\times A\to\Omega$ s.t. $$X(x',x)\cdot R(x,y)\le R(x',y)$$ $$R(x,y)\cdot Y(y,y')\le R(x,y')$$ <font size=5pt color=grey>(aka bimodule, profunctor, distributor, weakening relation, monotone relation, ...) </font> --- ## Many-Valued Relations <br> Composition of $\Omega$-relations has both residuals $$R\bullet - \ \dashv\ R\blacktriangleright - \quad\quad\quad - \bullet S\ \dashv \ -\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} --- ## Fuzzy Downsets and Upsets <span class="custom-space"></span> The elements of $\mathcal DX$ are $\Omega$-relations $X\looparrowright 1$ with homs $$\mathcal DX(\phi',\phi)=\phi'\blacktriangleright\phi =\bigwedge_{x\in X} (\phi' x\rhd \phi x)$$ The elements of $\mathcal UA$ are $\Omega$-relations $1\looparrowright A$ with homs $$\mathcal UA(\psi,\psi')=\psi \blacktriangleleft \psi'=\bigwedge_{a\in A} (\psi a\lhd \psi' a)$$ --- ## The Blacktriangle Calculus <span class="custom-space"></span> $$(\phi\blacktriangleright p)\blacktriangleleft \psi = \phi\blacktriangleright (p \blacktriangleleft \psi)$$ $$X(-,x)\blacktriangleright p = p(x,-)$$ $$p \blacktriangleleft A(a,-) = p(-,a)$$ $$(p\blacktriangleleft p(x,-)) \blacktriangleright p=p(x,-)$$ $$p\blacktriangleleft (p(-,a) \blacktriangleright p)=p(-,a)$$ --- ## The MacNeille Insertion <span class="custom-space"></span> $$\overline\ : X+A\to \mathcal P$$ <span class="custom-space"></span> $$\mathcal P(\overline x,\overline a) = p(x,a)$$ $$\mathcal P(\overline a, \overline a') = p(-,a)\blacktriangleright p(-,a')$$ $$\mathcal P(\overline x,\overline x') = p(x,-)\blacktriangleleft p(x',-)$$ $$\mathcal P(\overline a,\overline x) = p(-,a) \blacktriangleright p\blacktriangleleft p(x,-)$$ --- ## The MacNeille Yoneda Lemma <br> \begin{gather} \mathcal P(\overline x, (\phi,\psi)) = p(x,-)\blacktriangleleft\psi = \phi(x)\\ \mathcal P(\overline a, (\phi,\psi)) = \phi\blacktriangleright p(-,a) = \psi(a) \end{gather} --- ## Weighted (Co)Limit Completion <span class="custom-space"></span> The colimit of $\ \overline\ :X\to\mathcal P$ weighted by $\phi$ is the upset of $\phi$ $$(p\blacktriangleleft (\phi\blacktriangleright p),\phi\blacktriangleright p)$$ <span class="custom-space"></span> The limit of $\ \overline\ :A\to\mathcal P$ weighted by $\psi$ is the downset of $\psi$ $$(p\blacktriangleleft \psi,(p\blacktriangleleft \psi)\blacktriangleright p)$$ <span class="custom-space"></span> **Corollary:** $\mathcal P$ is complete. Moreover, every $(\phi,\psi)\in\mathcal P$ is - the colimit of $X\to\mathcal P$ weighted by $\phi$, - the limit of $X\to\mathcal P$ weighted by $\psi$. --- ## Questions? --- ## Appendix \begin{gather} \tiny (\phi\blacktriangleright p)(a)=\bigwedge_x (\phi(x)\rhd p(x,a))\\ \tiny (p\blacktriangleleft\psi)(x)=\bigwedge_a (p(x,a)\lhd \psi(a))\\ \tiny \psi\bullet C(-,c) = \psi(c) \\ \tiny C(c,-)\bullet\phi = \phi(c) \\ \end{gather}