The n-Category Café

This follows on from three previous posts, but doesn’t require you to have read the other ones — unless you want to appreciate the punchline!

1. In The Nucleus of a Profunctor: Some Categorified Linear Algebra I gave a construction which starts with an enriched profunctor between two enriched categories and gives rise to an adjoint equivalence between certain presheaves and copresheaves on the two enriched categories. This is the nucleus construction.

2. In Formal Concept Analysis I gave a construction which starts with a relation between two sets and gives rise to a Galois correspondence between certain sets of subsets of the two sets.

3. In Classical Dualities and Formal Concept Analysis I gave examples of this construction popping up all over mathematics.

In this post I’ll try to convince you that the second construction is just an example of the first. I’ll do this by explaining what familiar (?!) concepts from ordinary category theory become when you work in categories enriched over truth values. This is summarized in the following dictionary.

$$\array {\arrayopts{ \colalign{left left} \rowlines{solid} } \\ \text{category }&\text{ preorder}\\ \text{functor }&\text{ order preserving map}\\ \text{set of natural transformations}&\text{domination relation}\\ \text{internal hom object in Set }&\text{ logical implication in Truth}\\ \text{presheaf }&\text{ downward closed subset (downset)}\\ \text{copresheaf }&\text{ upward closed subset (upset)}\\ \text{category of presheaves }&\text{ downsets ordered by inclusion}\\ \text{category of opcopresheaves }&\text{ upsets ordered by containment}\\ \text{ category of presheaves on a set }&\text{ powerset of a set ordered by inclusion}\\ \text{ category of opcopresheaves on a set } & \text {powerset of a set ordered by containment}\\ \text{adjunction }&\text{ Galois connection}\\ \text{profunctor }&\text{ relation}\\ \text{nucleus of a profunctor }&\text{ Galois correspondence from a relation}\\  &   }$$

In the rest of this post (which has got quite long) I will just explain how the translation arises. It is basic enriched category theory, so if you already understand the above dictionary you can stop reading now!

Next time I hope to explain when you apply the nucleus construction when you enrich over things more like the real numbers.

The enriching category $\mathrm{Truth}$

The category of truth values, $\mathrm{Truth}$, has two objects: $\mathrm{true}$ and $\mathrm{false}$. The morphisms correspond to ‘logical entailment’ which is what working mathematicians would usually refer to as ‘implication’ but logicians reserve ‘implication’ for logical operation, we’ll see this below. Entailment is written $\vdash$ (pronounced ‘entails’), so we have $\mathrm{false}\vdash \mathrm{true}$ corresponds to the only non-identity morphism in $\mathrm{Truth}$. So the category can be simply pictured as follows. $$\mathrm{false}\longrightarrow \mathrm{true}$$ We can make this category of truth values into a monoidal category by using logical ‘and’ as the monoidal product; I’ll write this as $\wedge$.

Categories

A category enriched over $\mathrm{Truth}$, $\mathcal{C}$, consists of a set $\text {ob}\mathcal{C}$ and for each $c,c'\in \mathcal{C}$ we have the ‘hom-object’ $\mathcal{C}(c,c')\in \{ \mathrm{true}, \mathrm{false}\}$. We should think of $\mathcal{C}(c,c')$ as being the truth of a relation $c\le c'$. We need composition morphisms in this category, so for each triple, $c,c',c''\in \text {ob}\mathcal{C}$ we need a morphism in truth values $$\mathcal{C}(c',c'')\otimes \mathcal{C}(c,c')\to \mathcal{C}(c,c'');$$ in this context it means we have an entailment $$\mathcal{C}(c',c'')\wedge \mathcal{C}(c,c')\vdash \mathcal{C}(c,c''),$$ or, in other words, if $c\le c'$ and $c'\le c''$ then $c\le c''$. So we have a transitive relation. We also need an identity for each $c\in \mathcal{C}$, generally speaking this means we need a morphism (where $1$ is the monoidal unit) $$1\to \mathcal{C}(c,c);$$ in this context it means $$\mathrm{true}\vdash \mathcal{C}(c,c),$$ or, in other words, $c\le c$. So the relation is also reflexive. Thus we have a preorder.

Conversely, a preorder gives rise to a $\mathrm{Truth}$ category.

Slogan: $\mathrm{Truth}$-categories correspond to preorders.

Functors

There is a notion of an enriched functor which we can look at in this context. If we have two $\mathrm{Truth}$-categories $\mathcal{C}$ and $\mathcal{D}$ then a $\mathrm{Truth}$-functor consists of a function $F\colon \text {ob}\mathcal{C}\to \text {ob}\mathcal{D}$ and, for each pair $c,c'\in \text {ob}\mathcal{C}$, a morphism in $\mathrm{Truth}$ $$\mathcal{C}(c,c')\to \mathcal{D}(F(c),F(c'));$$ using square brackets to mean ‘the truth value of’ this is the same as $$[c\le c']\vdash [F(c)\le F(c')],$$ or, in other words, $F$ preserves the order.

Slogan: $\mathrm{Truth}$-functors correspond to order preserving maps.

Natural transformation objects

Enriched category theory is richer if we enrich over a complete closed, symmetric monoidal category. If the category is complete then we means that we can make the collection of enriched functors between two enriched categories into an enriched category. If we have $F,G\colon \mathcal{C}\to \mathcal{D}$ then we have a hom-object $[\mathcal{C},\mathcal{D}](F,G)$ and this is given by an end $$[\mathcal{C},\mathcal{D}](F,G)=\int _{c} \mathcal{D}(F(c),G(c)).$$ In the context of enriching over $\mathrm{Truth}$, this end is just a big ‘and’, or a ‘for all’, if you prefer. $$[\mathcal{C},\mathcal{D}](F,G)=\bigwedge _{c} \mathcal{D}(F(c),G(c)).$$ Rewriting this is terms of truth values of the relations we get that this means $$[F\le G] \coloneqq \bigwedge _{c} [F(c)\le G(c)].$$ In other words, given preorders $\mathcal{C}$ and $\mathcal{D}$, there is a canonical preorder on the set of order preserving functions $\mathcal{C}\to \mathcal{D}$, and this is $F\le G$ if and only if $F(c)\le G(c)$ for all $c$. We can say that $F$ is dominated by $G$ if $F\le G$.

Slogan: The $\mathrm{Truth}$-natural transformation object corresponds to the domination relation.

The closed structure

If the enriching category is closed then it can be considered as a category enriched over itself. There is a small problem here with type checking and we should be more precise. If $\mathcal{V}$ is closed then there is an internal hom functor $[-,-]\colon \mathcal{V}^{\mathrm{op}}\times \mathcal{V}\to \mathcal{V}$. We form a $\mathcal{V}$-category $\overline{\mathcal{V}}$ with the same objects as $\mathcal{V}$ but with the hom-object given by the internal hom $\overline{\mathcal{V}}(v,w):=[v,w]$. People often use the same notation for $\mathcal{V}$ and $\overline{\mathcal{V}}$; this is potentially confusing, but so you should do this with some care.

The category of truth values, $\mathrm{Truth}$, is closed and the internal hom is given by ‘logical implication’: $[a,b]:=a\Rightarrow b$. Here implication is understood in the logical operation sense and not the deductive sense (that’s what we are using entails for). So, using brackets purely for clarity, $$\begin{aligned} (\mathrm{true}\Rightarrow \mathrm{true}) &=\mathrm{true};& (\mathrm{true}\Rightarrow \mathrm{false})&=\mathrm{false};\\ (\mathrm{false}\Rightarrow \mathrm{true})&=\mathrm{true};& (\mathrm{false}\Rightarrow \mathrm{false})&=\mathrm{true}. \end{aligned}$$

Slogan: Internal hom for $\mathrm{Truth}$ is implication.

We know that $\mathrm{Truth}$-categories are the same as preorders, so this gives a natural preorder on the set $\{ \mathrm{true},\mathrm{false}\}$.

Slogan: The $\mathrm{Truth}$-category structure on $\mathrm{Truth}$ corresponds to the preorder $\mathrm{false}\le \mathrm{true}$.

Presheaves and copresheaves

As we are considering a closed enriching category $\mathcal{V}$, we can think of $\mathcal{V}$ as a $\mathcal{V}$-category and consider $\mathcal{V}$-functors into $\mathcal{V}$. This is like considering scalar valued functions on a vector space.

A presheaf on $\mathcal{C}$ is a $\mathcal{V}$-functor $P\colon \mathcal{C}^{\mathrm{op}}\to \mathcal{V}$ and a copresheaf is a $\mathcal{V}$-functor $Q\colon \mathcal{C}\to \mathcal{V}$. In the context of preorders and truth values, a presheaf is an order-reversing function $P\colon \mathcal{C}\to \{ \mathrm{true},\mathrm{false}\}$ and a copresheaf is an order-preserving function $Q\colon \mathcal{C}\to \{ \mathrm{true},\mathrm{false}\}$.

Knowing a function to $\{ \mathrm{true},\mathrm{false}\}$ is the same as knowing the preimage of $\mathrm{true}$, so we can identify a function $P\colon \mathcal{C}\to \{ \mathrm{true},\mathrm{false}\}$ with the subset $\tilde{P}=P^{-1}(\mathrm{true})\subseteq \mathcal{C}$. The order reversing condition $$\text {if }\, c\le c' \, \text { then } \, P(c')\le P(c)$$ translates into $$\text {if }\, c\le c'\, \text { and }c'\in \tilde{P}\, \text { then }\, c\in \tilde{P}.$$ So $\tilde{P}$ is a downward closed subset of the preorder $\mathcal{C}$ and all downward closed subsets arise in this way.

Similarly if $Q\colon \mathcal{C}\to \mathrm{Truth}$ is a copresheaf then it corresponds to an upward closed subset $\tilde{Q}=Q^{-1}(\mathrm{true})$.

Because presheaves are $\mathrm{Truth}$-functors, we canonically have the domination relation between them. Given presheaves $P,P'\colon \mathcal{C}^{\mathrm{op}}\to \mathrm{Truth}$ then $$P\le P'\quad \text {if and only if}\quad P(c)\le P'(c)\text { for all }c\in \mathcal{C},$$ which when translated to downward closed sets becomes $$P\le P'\quad \text {if and only if}\quad \tilde{P}\subseteq \tilde{P'}.$$

Slogan: The poset of presheaves on a preorder can be identified with the set of downward closed subsets equipped with the subset ordering.

Similarly, the domination relation on copresheaves corresponds to inclusion of the associated upward closed subsets. However, it is usually the opposite of the category of copresheaves that crops up, so this has the opposite relation.

Slogan: The poset of opcopresheaves on a preorder can be identified with the set of upward closed subsets equipped with the superset ordering.

Sets can be thought of as discrete posets, that is to say, where $c\le c'$ if and only if $c=c$. In that case all subsets are both upward closed and downward closed. In this case, then, the set of copresheaves and the set of presheaves can both be identified with the powerset of the original set.

Slogan: The poset of presheaves on a set is the powerset with the subset ordering; the poset of opcopresheaves on a set is the powerset with the superset ordering

Adjunctions

An enriched adjunction consists of a pair of enriched functors $$F\colon \mathcal{C}\leftrightarrows \mathcal{D}\colon G$$ together with an isomorphism in $\mathcal{V}$, natural in $c\in \mathcal{C}$ and $d\in \mathcal{D}$ $$\mathcal{D}(F(c),d)\cong \mathcal{C}(c,G(d)).$$ This means that when we enrich over the category of truth values we get a Truth-adjunction being a pair of order-preserving maps between posets $$F\colon \mathcal{C}\leftrightarrows \mathcal{D}\colon G$$ with the condition that $$F(c)\le d \, \text { if and only if }\, c\le G(d).$$ In other words we have the following slogan.

Slogan: A Truth-adjunction is precisely a Galois connection between preorders.

Then the adjoint equivalence induced on the fixed sets is precisely the Galois correspondence induced on the fixed set of the Galois connection.

Profunctors

A profunctor between $\mathcal{V}$-categories $\mathcal{C}$ and $D$ is an a $\mathcal{V}$-functor $$I\colon \mathcal{C}^{\mathrm{op}}\otimes \mathcal{D}\to \mathcal{V}.$$ We should remind ourselves what the definition of the tensor product of $\mathcal{V}$-cateogries is. The set of objects of $\mathcal{A}\otimes \mathcal{B}$ is the set of ordered pairs $\text {ob}\mathcal{A}\times \text {ob}\mathcal{B}$ and the hom-sets are given by $$\mathcal{A}\otimes \mathcal{B}((a,b),(a',b')):=\mathcal{A}(a,a')\otimes \mathcal{B}(b,b').$$ It is perhaps worth noting that in order to define composition we will need that $\mathcal{V}$ has some extra structure such as being symmetric or braided.

When enriching over truth values, this means that for preorders $\mathcal{A}$ and $\mathcal{B}$ the preorder on $\mathcal{A}\times \mathcal{B}$ is given by $$(a,b)\le (a',b')\quad \text { if and only if }\quad a\le a' \, \, \text {and}\, \, b\le b'.$$ A profunctor in the $\mathrm{Truth}$ case can then be identified with a subset of $\mathcal{C}\times \mathcal{D}$ which is upward closed. Writing $c\preceq d$ for $I(c,d)$, we have: $$\text {if}\, \, c\preceq d\, \, \text {and}\, \, (c,d)\le (c',d')\, \, \text {then}\, \, c'\preceq d'.$$ This can make more sense if we expand it out: $$\text {if}\, \, c'\le c\preceq d \le d' \, \, \text {then}\, \, c'\preceq d'.$$ Slogan: Profunctors between preorders correspond to relations extending the preorders

Nuclei

In the first post in this sequence I showed that a profunctor $I$ gives rise to an adjunction between presheaves and opcopresheaves, and thus to an adjoint equivalence between the fixed sets of the adjunction.

In the third post I showed how a relation between sets gives rise to a Galois connection between the powersets and thus to a Galois correspondence between the sets of closed subsets. I also gave several examples of correspondences around different areas of maths that arise in this way.

I will leave it to the interested reader to show that the Galois correspondence construction is what you get when you apply the profunctor nucleus construction to the situation of discrete $\mathrm{Truth}$-categories. It should drop out from the dictionary.

Slogan: The nucleus of a profunctor between discrete categories corresponds to the Galois correspondence between the closed subsets coming from a relation between two sets.

That’s not a very snappy slogan to end with, I grant you.

Next time

In the next post I will show how costructing the nucleus of a profunctor when you enrich over something like the real numbers instead of truth values gives rise to some dualities in other areas of maths.