Let Rel be the category whose objects are sets and whose morphisms are binary relations, with composition defined by $x (S \circ R) z \Leftrightarrow (\exists y : x R y \wedge y S z)$, and identity the equality relation.


If we have relations $R \in Rel(X, X')$ and $S \in Rel(Y, Y')$, we can define a relation $(R \to S) \in Rel(X \to Y, X' \to Y')$ by
\begin{equation}
f (R \to S) g \Leftrightarrow (\forall x \in X, x' \in X' : x R x' \Rightarrow f(x) S g(x')),
\end{equation}
i.e. functions are related iff they map related arguments to related values.


Unfortunately, this does *not* constitute a bifunctor $\to : Rel \times Rel \to Rel$. Indeed, composition is not respected. We have $(R' \to S') \circ (R \to S) \subseteq (R' \circ R) \to (S' \circ S)$, but in general these relations are not equal.


My question is: what *is* this operation $\to$? Is its behaviour documented, and perhaps an instance of a more general structure?



Set of functions is not a bifunctor on Rel
The operation you are describing is a cartesian closed structure, not on the category $Rel$ of sets (as objects) and relations (as morphisms), but rather on a category whose *objects* are relations and whose morphisms are pairs of functions mapping related arguments to related results. This is a bit easier to see/explain if instead of considering (binary) relations, we consider (unary) predicates.


So, let $SubSet$ be the category whose objects are pairs $(A,P\subseteq A)$ of a set together with a predicate on that set, and whose morphisms $(A,P) \to (B,Q)$ are functions $f : A \to B$ mapping arguments in $P$ to results in $Q$:
$$\forall a.\, a \in P \Rightarrow f(a) \in Q$$
There is an obvious functor $\pi : SubSet \to Set$ given by the first projection. Now, the key fact is that **$\pi$ is a strict cartesian closed functor**. This means that for any pair of predicates $P \subseteq A$ and $Q \subseteq B$, there are predicates
\begin{align\*}
P\times Q &\subseteq A \times B \\
Q^P & \subseteq B^A
\end{align\*}
such that $(A\times B,P\times Q)$ and $(B^A,Q^P)$ are respectively the product and exponential in $SubSet$. In particular, $P\times Q$ and $Q^P$ are defined by
\begin{align\*}
(a,b) \in (P\times Q) \quad &\text{iff}\quad a\in P \wedge b\in Q \\
f \in Q^P \quad &\text{iff}\quad \forall a.\,a\in P \Rightarrow f(a)\in Q
\end{align\*}
Essentially the same explanation goes through in the case of binary relations, but in that case we consider a category $Sub(Set\times Set)$ equipped with a projection functor $\pi' : Sub(Set\times Set) \to Set\times Set$. Once again the key point is that $\pi'$ is a strict cartesian closed functor. Note that these projection functors have some other important properties as well (for example, they are bifibrations), but for the construction alluded to in your question this cartesian closed structure suffices.


Finally, if you are interested in reading more about this categorical approach to "logical predicates", you might have a look at Hermida's thesis (as well as some of the followup literature):


* Claudio Hermida, [Fibrations, Logical Predicates and Indeterminates](http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6935), Ph.D.
thesis, University of Edinburgh, November 1993.


