(this page is empty)

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

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

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.

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')\]

(aka bimodule, profunctor, distributor, weakening relation, monotone relation, …)

Weighted Relations and Implications

\[(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

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

\(G:D\to B\), \(\phi\in\mathcal DD\), \(\psi\in\mathcal UD\).

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

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

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

\[\overline\ : X+A\to \mathcal M\]

\[\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,-)\]

(These formulas show how the distance \(\cont(x,a)\) determines all other distances in \(\cal M\).)

The MacNeille Yoneda Lemma

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

(These formulas compute distances from \(x\) and distances to \(a\) with the Yoneda lemma.)

Weighted (Co)Limit Completion

The colimit of \(\ \overline\ :X\to\mathcal M\) weighted by \(\phi\) is the upset of \(\phi\)

\[\phi\blacktriangleright \cont\]

The limit of \(\ \overline\ :A\to\mathcal M\) weighted by \(\psi\) is the downset of \(\psi\)

\[\cont\blacktriangleleft \psi\]

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

Theorem (compactness): \(C^\delta(\lim_f [-],{\rm colim}_{i}[-])=\cont (f,i).\)

(In the case of 2-valued logic this property reads \(\bigwedge f \le \bigvee i\ \Rightarrow \ f\cap i \not=\emptyset\).)

Selected References

Ongoing and Future Work

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