Embrace Negativity

One way to explain categories is to say that the morphisms of a category represent relationships between the objects. I think this is too optimistic. Thinking more negatively, we may ask: “what sort of structure has norphisms between objects representing negative relationships?”. In this paper the authors define norphisms using enriched category theory. In this post I will do the same, but using a simpler enrichment.

For the already indoctrinated, this post is about (\mathsf{Bool}^{op},\vee, \bot)-enriched categories where \mathsf{Bool} is the category \bot \implies \top i.e. the category with two objects (\bot and \top) and a unique non-identity arrow from \bot \to \top. Before unpacking what this means, I will tell you how they are interpreted. A (\mathsf{Bool}^{op},\vee, \bot)-category has an underlying graph. The graph

is a \mathsf{Bool}^{op}-enriched category. The edges of this structure represent unavoidable obstructions. The unavoidableness pops right out of the definition of enrichment. To see that we need to unpack the definition of \mathsf{Bool}^{op}-enrichment.

In a V-category for each object x there is a V-morphism e_x : I \to G(x,x) where I is the monoidal unit of V. In our case, for a \mathsf{Bool}^{op}-category G, we have a morphism in \mathsf{Bool} denoted G(x,x) \implies \bot. Because \bot is the bottom element of \mathsf{Bool}, this means that G(x,x)=\bot so you can’t have an obstruction from an object to itself. If you don’t go anywhere, then you can’t get stuck! You may obtain the composition law by again reversing the arrows and the monoidal structure. This gives

G(x,z) \implies G(x,y) \vee G(y,z)

So if you can’t get from x to z, then either you can’t get from x to y or you can’t get from y to z. Note that this law is the contrapositive of the transitive law of posets G(x,y) \and G(y,z) \implies G(x,z). For this reason my collaborator named these structures contraposets.

The cool thing about contraposets is that when you glue contraposets together they get smaller! Let’s take the example of the contraposet from before and add another vertex without any obstruction.

This is no longer a contraposet because now the obstructions can be avoided by going to the extra vertex. The smallest contraposet containing the above edges is the following:

It’s magical to me that all of the obstructions dissappear. The lesson here is clear: we can avoid our failures when we work together!

3 Likes

Lovely post Jade!

I’m possibly the 100th person to ask this, but… can one work with topological obstructions as contraposets?

I think the baby case would be the following: you start with a topological space X and construct the contraposet of the negation of its connectivity relation. I’m going to call it \overline\Pi_0. That is you take |X| as your objects and set \overline\Pi_0(x,y) = \top iff x is in a different connected (possibly by arcs) componet than y.

Notice that this is literally the connectivity relation \Pi_0, seen as a \sf Bool-enriched category, after a change of enrichment along \neg : \sf Bool \to Bool^{\rm op}

Then the phenomenon you exhibit gives me hope that if X \leftarrow Z \to Y a span of topological space (think of it as a glueing plan), then the map \overline\Pi_0(X +_Z Y) \to \overline\Pi_0(X) +_{\overline\Pi_0(Z)} \overline\Pi_0(Y) is an iso. This is a kind of ‘van Kampen theorem’: \overline\Pi_0 preserves pushouts.

Here’s a sketch of the proof: it’s reasonable that the two contraposets have the same objects. Now obstructions ‘from X to Y’ in the second contraposet are such that x \not\to y iff for every z, x \not\to z and z \not\to y. But these are the same obstructions we have in \overline\Pi_0(X +_Z Y), since a point in x is disconnected from a point in y after the glueing along Z iff there is no z such that x is connected to z and z is connected to y.

1 Like

Nice, I think that is correct. We need to be a little bit careful about colimits of contraposets. You are implicitly claiming that on objects they are given by the pushout of sets right? I am pretty sure that this is true. Recall that morphisms of contraposets go forward on the objects and backwards on the edges.

Something I want to show you is the definition of apartness relations which are groupoidal contraposets. The people who defined these were interested in topology, so their work may be related to your construction.

1 Like