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

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.

• Yeah, as @Tobias mentions "complete" is a bit of a misleading word. The property you mention is, as far as I've seen, termed "linear" or "total". – Musa Al-hassy Jul 4 '16 at 19:37
• Yes, it is true that this property is sometimes called "total". I used the word "complete" because in my corner of mathematics, that is the term which is normally used. (Which is rather unfortunate, because it risks confusion with the completely different property of Dedekind-completeness ---i.e. the existence of suprema and infima for arbitrary subsets.) However, I would avoid the word "linear", because a linear order is also antisymmetric ---i.e. it has the property that $(a \succeq b$ and $b\succeq a)$ if and only if $a=b$. But let's not get bogged down in terminology issues. – Marcus Pivato Jul 5 '16 at 7:20
• Assuming that your Category $\mathcal C$ has binary products there is a terminal span: $B\times B$ (with the projections). Now if $\mathcal C$ also has binary coproducts, you can construct a span $R \sqcup R^{op}$. Then we could define completeness as saying that $R \sqcup R^{op} \to B \times B$ is an epi for example. – Maxime Lucas Jul 5 '16 at 13:47

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?

• Thank you very much for your response, Tobias. I have edited the question to explain what I mean by "complete" for a binary relation. I also added a commuting diagram explaining what I mean by "span extension". If I understand your response, you assume $\mathcal{R}^2$ is already defined (e.g. as a product in some category), and then "composition" is a morphism $\mathcal{R}^2\rightarrow\mathcal{R}$ (i.e. an algebra). Is this correct? But part of the problem here is to define $\mathcal{R}^2$ itself. If we have pullbacks this is easy; otherwise it is not. – Marcus Pivato Jul 4 '16 at 16:51
• Yes, that's correct: I've been assuming that $\mathcal{R}^2$ is the pullback that you've mentioned. As I said in the first paragraph, I haven't answered your question, but I just wanted to point out that the "extension" that you consider in the case when pullbacks exist leads to a nice and well-understood concept. – Tobias Fritz Jul 5 '16 at 7:21

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