The notion of quantaloid is the horizontal categorification of that of quantale: a quantaloid is a quantale with many objects.
A quantaloid is a category enriched in the closed symmetric monoidal category of suplattices. Equivalently, it may be defined as a locally posetal bicategory in which each hom-poset is cocomplete, and which admits right adjoints to composing with an arrow on either side (making it a (bi)closed bicategory).
Taking the view that a quantaloid $Q$ is a closed bicategory, one can study categories enriched in $Q$. This can become particularly interesting if $Q$ is a $*$-quantaloid, i.e., comes equipped with an involution $*: Q \to Q$ which is the identity on 0-cells, reverses the direction of 1-cells, and preserves the direction of 2-cells. In that case one can study $*$-enriched categories over $Q$, i.e., $Q$-categories
for which $d(y, x) = d(x, y)^*$. A famous example, due to R.F.C. Walters, is given below.
Despite the exotic-sounding name (a portmanteau of quantale and groupoid, i.e., a many-object quantale), quantaloids are quite commonplace.
A toy form of this example: take any frame $H$, and considering the bicategory of spans in $H$: this is evidently a quantaloid, $Span(H)$.
Here is a particularly rich source of examples. Let $Q$ be a quantale. Then there is a quantaloid $Q$-$Mat$ of $Q$-valued matrices:
Objects are sets $X$;
Morphisms $X \to Y$ are functions $M: X \times Y \to Q$.
Matrix composition is performed according to the usual rule
where $\cdot$ is the multiplication of $Q$ and the sum is the sup in $Q$. This class of examples easily internalizes in a topos, and in that sense it subsumes the first example, $Rel(E)$, by taking $Q = \Omega$ (as an internal frame, hence a quantale).
Slightly more generally, if $Q$ is a quantal_oid_, there is a quantaloid $Q$-$Mat$ of $Q$-matrices, as follows:
Objects are sets $X$ together with functions $p: X \to Q_0$;
Morphisms $(X, p) \to (Y, q)$ are matrices $M: X \times Y \to Q_1$ that satisfy the typing constraint $M(x, y): p(x) \to q(y)$.
Composition works exactly as before.
The examples in the preceding section carry over straightforwardly:
Next, let $Q$ be a $*$-quantale. The quantaloid $Q$-$Mat$ is as before; this becomes a $*$-quantaloid by defining the transpose of a matrix as
This easily carries over to the case where we start with a $*$-quantaloid $Q$: we similarly obtain a $*$-quantaloid $Q$-$Mat$, by defining transpose as above.
Let $Q$ again be a $*$-quantale; for example, $Q$ could be a frame or it could be a commutative quantale, taking the involution to be the identity.
A $Q$-valued set consists of a set $X$ and a morphism $M: X \to X$ in $Q$-$Mat$ which is
Symmetric: $M^* = M$,
Idempotent: $M \circ M = M$
In the case where $Q = \Omega$, the subobject classifier in a topos with its locale structure, symmetry and idempotence of a relation is equivalent to the a priori weaker condition of symmetry and transitivity. The reason is that $Q$-$Mat = Rel(E)$ is an allegory, where the modular law holds, one of whose consequences is the inequality $M \leq M M^* M$. As a result, we have
which together with transitivity guarantees idempotence.
Thus, symmetric idempotents in $Rel(E)$ are what are known as partial equivalence relations (which differ from equivalence relations by dropping reflexivity), or PERs for short.
To be continued