I have the following structure that to me looks like some kind of "bipartite category":

  • There are two sorts of objects $A$ and $B$
  • Arrows only go from objects of $A$ to objects of $B$, so they all have form $f : a \to b$ where $a : A$ and $b : B$
  • Composition is only allowed via compatibility relation $R \subseteq B \times A$: if you have $f : a \to b$ and $g : a' \to b'$, then $g \circ f : a \to b'$ exists iff $bRa'$
  • Composition (where allowed) is associative as usual.

(I am being vague if $A$ and $B$ are sets or not, but if that matters, I am happy to restrict them to be sets.)

Is there an established structure like this? If not, is there at least something of which the above is a special case of?

Motivation / Context

I received two comments asking for more context, so here's a brief description of where I'm coming from.

First, suppose you want to describe a process made up of discrete steps. You could model it with a category where the objects are states, and the steps you can take are arrows: the domain is the start state, and the codomain is the end state. This works out nicely because identity morphisms correspond to not taking any steps at all, and composition is just sequencing.

Now, I am in a situation where instead of characterizing steps by their start and end state, I'd like to characterize them as an input interface and an output interface. The only extra structure I want to impose is that there is a way to tell (proof-irrelevantly) if an output interface can be connected to the next input interface. So the $A$ and the $B$ in my question would stand for the possible input and output interfaces, and $R$ is the compatibility relation.

  • 1
    $\begingroup$ Just to clarify, are there identity arrows? I'm guessing not from the second condition $\endgroup$
    – Ben
    Commented Sep 21, 2020 at 3:25
  • $\begingroup$ Identity arrows wouldn't make sense because the domain and codomain of arrows are different. $\endgroup$
    – Cactus
    Commented Sep 21, 2020 at 3:27
  • 2
    $\begingroup$ Out of curiosity, how did this arise? $\endgroup$ Commented Sep 21, 2020 at 3:31
  • 3
    $\begingroup$ If you ignore the absence of identity arrows, then this is a special case of a category: there is at most one arrow (given by $R$) from an object of $B$ to an object of $A$, and no arrows between objects of $A$ or of $B$. $\endgroup$ Commented Sep 21, 2020 at 5:04
  • 1
    $\begingroup$ I don't understand how any compositions exist. For $f : a \to b$ and $g : a' \to b'$ to have a composition (in the usual categorical sense) we need $b = a'$ but you just said that $b$ and $a'$ are objects of two different types. Is there a typecasting operator around you haven't made explicit? Also, I think it is a very bad idea to write down a formalism like this which excludes identity morphisms. Can you explain what the motivation is in more detail (but hopefully not requiring too much Haskell background)? I can't make heads or tails of the reddit thread. $\endgroup$ Commented Sep 21, 2020 at 5:09

1 Answer 1


As Kevin Arlin comments, this setup can be realized by considering

  1. a category $\mathcal H$, with two disjoint full subcategories $\mathcal A,\mathcal B$, such that their union contains all objects of $\mathcal H$.

  2. Both $\mathcal A$ and $\mathcal B$ are discrete.
    Edit: As written in the comments, in order to make this indeed a category, we have to add the compositions of internal morphisms like $a\to b\to a'$, so that they are not discrete in any interesting scenario: either we are really assuming some morphisms in $\mathcal A$ and $\mathcal B$, or we can freely add the missing compositions.

  3. Moreover, $|\hom(b,a)|\le 1$ for each $a\in\mathcal A,\,b\in\mathcal B$.
    Edit: According to above edit, neither this makes sense in the general case if $\mathcal A,\mathcal B$ are not discrete. The closest thing we can assume is that if there's an arrow ending at object $a\in\mathcal A$, then $a$ has a coreflection in $\mathcal B$.

Note that 1. can be rephrased as a category $\mathcal H$ over 'the generic isomorphic pair of objects', that is, a functor $\mathcal H\to \mathcal I$ where $\mathcal I$ is the category with 2 objects $x,y$ and 2 nonidentity arrows $x\to y$ and $y\to x$:
Simply send objects of $\mathcal A$ to $x$ and objects of $\mathcal B$ to $y$.

By the way, it's essentially the same as a Morita context in the bicategory of profunctors.

  • 2
    $\begingroup$ While this is what I said, I think it's not precisely right, since if you go from $a\to b$ and then $b\to a'$, you'll get an induced morphism $a\to a'$. Instead of $\mathcal A$ and $\mathcal B$ being discrete, it seems we need to say that morphisms of $\mathcal A$ and $\mathcal B$ are freely generated from the given morphisms from $\mathcal A$ to $\mathcal B$ and back. $\endgroup$ Commented Sep 21, 2020 at 20:03
  • $\begingroup$ Hmm.. That makes sense. $\endgroup$
    – Berci
    Commented Sep 21, 2020 at 20:06
  • $\begingroup$ I'll hold on waiting for another answer, because it is a bit like saying the answer is "set, with some extra constraints". The ideal answer would be some named concept that can be used in a descirption/documentation both to import intuition and also to say "you can use this for this purpose as-is, or you can read up on the wider theory by starting from this name". $\endgroup$
    – Cactus
    Commented Sep 22, 2020 at 9:00
  • 1
    $\begingroup$ I understand. Kevin's original comment would have been a clearer answer, but with these edits I also feel it less satisfactory. $\endgroup$
    – Berci
    Commented Sep 22, 2020 at 10:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .