Relation Lifting

(draft)

Extending a functor from functions to relations is important to coalgebra for at least two reasons. Relation lifting can be used to define bisimulations and also to define Moss's coalgebraic logic. In the latter case, the idea is to apply the lifted functor to the satisfiability relation.

Relation lifting can be defined in at least two ways, via spans and via cospans. In both cases the idea is to first represent a relation by a pair of arrows, and then to apply the functor to these arrows.

In the following let

$\mathsf{R}\mathsf{e}\mathsf{l}$ be the category which has sets as objects and relations as arrows.

Span-Based Relation Lifting

The idea of the span-based relation lifting of a functor

$T$ is to "tabulate" a relation

$R$ by a span

$X\stackrel{p}{\leftarrow }R\stackrel{q}{\to }Y$ and then to apply the functor

$T$ to the projections, obtaining

$TX\stackrel{Tp}{⟵}TR\stackrel{Tq}{⟶}TY$.

Definition: Let

$T:\mathsf{S}\mathsf{e}\mathsf{t}\to \mathsf{S}\mathsf{e}\mathsf{t}$ and

$X\stackrel{p}{\leftarrow }R\stackrel{q}{\to }Y$ be a relation. Then

$$\bar{T}:\mathsf{R}\mathsf{e}\mathsf{l}\to \mathsf{R}\mathsf{e}\mathsf{l}$$

is the relation given by

$$\bar{T}R=\{(a,b)\in TX\times TY\mid \mathrm{\exists }w\in TR.Tp(w)=a\mathrm{\&}Tq(w)=b\}$$

Remark: This formulation is specific to set-functors, but can be generalised to other base categories.

Fact:

$\bar{T}$ preserves composition (and therefore is a functor on

$\mathsf{R}\mathsf{e}\mathsf{l}$) if

$T$ preserves weak-pullbacks.

Example/Exercise: Let

$\mathcal{P}$ be the powerset functor. It is an interesting exercise to check that

$(a,b)\in \bar{\mathcal{P}}X$ iff

$$\begin{array}{c}\mathrm{\forall }x\in \mathcal{a}.\mathrm{\exists }y\in b.xRy\\ \mathrm{\forall }y\in \mathcal{b}.\mathrm{\exists }x\in a.xRy\end{array}$$

Fact:

$\bar{\mathcal{P}}:\mathsf{R}\mathsf{e}\mathsf{l}\to \mathsf{R}\mathsf{e}\mathsf{l}$ is a functor. If

$R$ is a partial order then

$\bar{\mathcal{P}}R$ is a partial order.

Extending Set-Functors to Ordered Sets

The cospan-based relation lifting starts from the cotabulation (or collage) of a relation

$R$ by a cospan

$X\stackrel{j}{\to }\mathbf{R}\stackrel{k}{\leftarrow }Y$, where

$\mathbf{R}$ is an order on the disjoint union

$X+Y$ given by

$(u,v)\in \mathbf{R}$ iff

$u=v\in X$ or

$(u,v)\in R$ or

$u=v\in Y$.

Thus, in order to apply a set-functor

$T$ to

$j$ and

$k$, we need extend

$T$ from sets to orders. This follows the same idea as the relation lifting in the previous section, but now one closes under reflexivity and transitivity (and quotients by anti-symmetry in the case one works with posets).

Definition: Let

$(X,\le )$ be a pre-order. Write

$X\stackrel{p}{\leftarrow }\le \stackrel{q}{\to }X$ for the two projections. Then

$\tilde{T}(X,\le )$ has carrier

$TX$ and the order on

$\tilde{T}(X,\le )$

is the smallest order containing

$$\{(a,b)\in TX\times TX\mid \mathrm{\exists }w\in T(\le ).Tp(w)=a\mathrm{\&}Tq(w)=b\}.$$

This defines a functor

$$\tilde{T}:\mathsf{O}\mathsf{r}\mathsf{d}\to \mathsf{O}\mathsf{r}\mathsf{d}$$

where

$\mathsf{O}\mathsf{r}\mathsf{d}$ can be preorders or posets.

Remark: The surjection

$TX\stackrel{s}{\to }\tilde{T}(X,\le )$ has a universal property as the universal solution to the inequation to

$s\circ Tp\le s\circ Tq$. Category theoretically, we can say that

$s$ is the coinserter of

$(Tp,Tq)$ and also that

$\tilde{T}$ is the (order-enriched) left Kan extension of

$DT$ along

$D$ where

$D$ is the embedding of sets into (discrete) ordered sets.

The following fact allows us to use known results about the span-based relation lifting to compute the order-extension of a set-functor in many examples.

Fact: If

$T$ preserves weak pullbacks, then applying

$\tilde{T}$ to a preorder

$(X,\le )$ agrees with applying the relation lifting

$\bar{T}$ to

$\le$.

Example: Let

$(X,\le )$ be a preorder. For subsets

$a,b\subseteq X$ we have

$a\le b\in \tilde{\mathcal{P}}(X,\le )$ iff

$$\begin{array}{c}\mathrm{\forall }x\in \mathcal{a}.\mathrm{\exists }y\in b.x\le y\\ \mathrm{\forall }y\in \mathcal{b}.\mathrm{\exists }x\in a.x\le y\end{array}$$

In domain theory, this is also known as the Egli-Milner order. When restricted to convex subsets (and modified wrt the empty subset)

$\tilde{\mathcal{P}}$ is known as the Plotkin powerdomain. See also my review of powerdomains.

Cospan-Based Relation Lifting

To cotabulate a relation

$R\subseteq X\times Y$ by a cospan

$$X\stackrel{j}{\to }\mathbf{R}\stackrel{k}{\leftarrow }Y$$

we need to recall the collage

$\mathbf{R}$ of a relation

$R$. This notion can also be defined in case

$X$ and

$Y$ are ordered sets and

$R$ is weakening-closed, that is,

$$\frac{x^{\prime }\le xRy\le y^{\prime }}{x^{\prime }R{y}^{\prime }}.$$

We give the more general definition, because it shows that the cospan-based relation lifting cannot only be used to extend set-functors but also ordered functors.

If

$R\subseteq X\times Y$ is a weakening relation, then the collage

$\mathbf{R}$ is an order on the disjoint union

$X+Y$ such that

$x\mathbf{R}y$ if (i)

$x\le y$ in

$X$ or (ii)

$xRy$ or (iii)

$x\le y$ in

$Y$.

Given a functor

$T:\mathsf{S}\mathsf{e}\mathsf{t}\to \mathsf{S}\mathsf{e}\mathsf{t}$, ^[1] we can use the collage to give a cospan-based definition of relation lifting.

Definition: Let

$R\subseteq X\times Y$. Then

$$\hat{T}:\mathsf{R}\mathsf{e}\mathsf{l}\to \mathsf{R}\mathsf{e}\mathsf{l}$$

is defined

$(a,b)\in \hat{T}R$ if

$a\le b$ in

$\tilde{T}\mathbf{R}$.

Fact: If

$T$ preserves weak pullbacks then

$\bar{T}=\hat{T}$.

Conclusion

The span-based relation lifting can be generalised to ordered sets an is well-behaved if the functor preserves weak pullbacks.

The cospan-based relation lifting is ineherently order enriched, but can be applied to the discrete case if we extend the functor to ordered sets.

One application of relation lifting is to define coalgebraic bisimulation. Here the span-based and the cospan-based definition agree if the functor preserves weak pullbacks, but in general it is only cospan bisimilarity that captures coalgebraic behavioural equivalence/preorder.

The cospan-based relation lifting generalises from ordered sets to Lawvere metric spaces and other categories enriched over a quantale.

References

References can be found in the survey article

• Kurz, Velebil: Relation Lifting.

---

1. (or a functor on preorders or posets) ↩︎