Spans as binary relations: reflexivity, transitivity, and completeness?

Question

Let $\mathcal{C}$ be a category, let $B$ be an object in $\mathcal{C}$, and let $\mathcal{R}$ be a span from $B$ to itself. (That is: $\mathcal{R}$ is a diagram $B \stackrel{r_1}{\longleftarrow} R \stackrel{r_2}{\longrightarrow} B$, where $R$ is some other object in $\mathcal{C}$, and $r_1$ and $r_2$ are $\mathcal{C}$-morphisms.) It is common to think of $\mathcal{R}$ as a sort of "abstract binary relation" on $B$. (Indeed, if $\mathcal{C}$ is the category of sets, then it is easy to represent every "ordinary" binary relation on a set $B$ as a span, and to interpret every span on $B$ as an ordinary binary relation.)

If $B$ is a set, then a weak order on $B$ is a binary relation on $B$ which is complete, reflexive, and transitive. I am interested in defining something analogous to a weak order in an abstract category, so I need something analogous to these three properties for abstract spans.

Reflexivity is straightforward. If $\mathcal{R}$ is a span from $B$ to itself an abstract category, then we can define $\mathcal{R}$ to be reflexive if it extends the identity span (that is, the span $B \stackrel{I}{\longleftarrow} B \stackrel{I}{\longrightarrow} B$, where $I$ is the identity morphism). But the definition for the other two properties is not so obvious. So my question is this:

Is there a way to reformulate the properties of completeness and transitivity for spans on abstract categories?

(To be clear, a binary relation $\succeq$ on a set $B$ is complete (or total) if, for all $a,b\in B$, either $a\succeq b$ or $b\succeq a$. The binary relation $\succeq$ is transitive if, for all $a,b,c\in B$, if $a\succeq b$ and $b\succeq c$, then $a\succeq c$.)

If $\mathcal{C}$ admits all pullbacks, then we can define the "composition" of the span $\mathcal{R}$ with itself in the obvious way, to obtain a span that I will denote by $\mathcal{R}^2 = (B \stackrel{q_1}{\longleftarrow} Q \stackrel{q_2}{\longrightarrow} B)$, for some object $Q$ and morphisms $q_1$ and $q_2$. Then we can define $\mathcal{R}$ to be transitive if $\mathcal{R}^2$ is "extended" by $\mathcal{R}$, by which I mean there is a commuting diagram

$$ \begin{array}{ccccc} & & Q \\ &\stackrel{q_1}{\swarrow} & \downarrow & \stackrel{q_2}{\searrow} \\ B &\stackrel{r_1}{\leftarrow} & R & \stackrel{r_2}{\rightarrow} & B \end{array} $$

However, if $\mathcal{C}$ does not admit all pullbacks, then this strategy doesn't work; is there another way to define "transitive" in this context?

This seems like an obvious question, and I would not be surprised if someone already answered it years ago. However, I am not an expert in category theory, and I have not been able to find an answer in any of the obvious places. I would be very grateful if someone could point me to any literature or make any other suggestions.

Answer 1

This is not really an answer to your question, but I'd like to point out that your "extension" definition probably isn't quite what you want yet. Of course this may well depend on your intended application, but there nevertheless is a standard definition which turns out to be the "right" way to describe e.g. certain 2-categorical considerations. This standard answer is what I'll explain in the following.

Transitivity is a property of relations, but it should be taken to be a structure at the level of spans! The "extension" that you mention is conventionally taken to consist of a map $\mathcal{R}^2\to\mathcal{R}$ called composition, in such a way that the original span together with this map satisfies the properties required of an internal category. So you can think of $A$ as your "object of morphisms", $B$ is your "object of objects", the two legs of the span are the domain and codomain maps, while the composition map $\mathcal{R}^2\to\mathcal{R}$ is composition, and reflexivity results in identities. All these pieces of structure must be compatible in the sense of the category axioms.

Is this a useful concept in your situation?

I don't know what to do in the absence of pullbacks. I also don't know what it means for a binary relation to be "complete". You're not talking about the ordering being complete, are you? Could you elaborate?

Answer 2

Some more suggestions for completeness/totality:

If $\mathcal{C}$ has binary products and coequalizers, then define the unordered pairs from $B$ as the coequalizer $$ B\times B \overset{id}{\underset{swap}{\overset{\longrightarrow}{\longrightarrow}}} B\times B \overset{\kappa}\twoheadrightarrow B_2 $$

Definition 1

A relation $\mathcal{R} = (R,r_1,r_2)$ is complete (total) if the composition $$ R \overset{\langle r_1,r_2\rangle}{\longrightarrow} B×B \overset\kappa\twoheadrightarrow B_2 $$ is an epimorphism.

Definition 2

A relation $\mathcal{R}$ is complete (total) if there is some morphism $f: B×B\to R$ with $$ \begin{array}{ccccc} B×B & \stackrel{f}{\rightarrow} & R\\ \!\!\!\!\!\kappa \downarrow && \downarrow \langle r_1,r_2\rangle\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\\ B_2 &\stackrel{\kappa}{\leftarrow} & B×B \end{array} $$

Note that by epimorphism laws, the second definition implies the first.

Regarding Transitivity & Pullbacks

You do not need all pullbacks, but only those of $r_1$ and $r_2$. That means you only require $\mathcal{R}\circ\mathcal{R}$ to exist.

Maybe it suffices in your case require some weak pullback of $r_1$ along $r_2$ to exist? Then one could say that $(R,r_1,r_2)$ is transitive if there is some weak pullback of $r_1$ along $r_2$, called $(P,p_1,p_2)$, which is extended by $\mathcal{R}$. (And in case the pullback exists, it is equivalent to your definition using pullbacks).