[Math] Why is Set, and not Rel, so ubiquitous in mathematics

Question

The concept of relation in the history of mathematics, either consciously or not, has always been important: think of order relations or equivalence relations.

Why was there the necessity of singling out a particular kind of relations, namely the functional ones? I guess (but I don't have data about this) historically the recognition that "operational" expressions like $x^3$ or $\sum_{i=0}^{\infty} \frac{x^n}{n!}$ could be formalized as functional relations led to devote more attention to functions understood in the modern set theoretical sense (i.e. as a special case of relations). That viewpoint permitted to consider things such as the Dirichlet function $\chi_{\mathbb{Q}}$ (which was previously not even considered to be a true "function"!) as fully legitimate objects, and to not dismiss them as pathological, with great theoretical advantage. The language and notation of functions was preferred even to deal with things that, technically, were relations: think of "multi-valued functions" in complex analysis such as $\sqrt x$ or $\log (x)$.

1) In which instances in modern mathematics are relations used as important generalizations of functions? One example that comes to mind is correspondences in the sense of algebraic geometry.

---

In modern Algebra the concept of homomorphism, a kind of function between algebraic structures, is central; we are used to see expressions like $f(x*y)=f(x)*f(y)$. But it would be equally possible to define a "homomorphic relation" $R$, for example on groups, by the requirement: $(xRz$ & $yRt)$ $\Rightarrow$ $(x*y)R(z*t)$, where $*$ is the group multiplication.

2) Has this kind of "homomorphic relations" been studied (on groups or other algebraic structures)? Why algebra is pervaded with homomorphisms but we never see "homomorphic relations"? Are there something more than just historical reasons?

---

Let Set be the usual category of sets, and Rel be the category of sets-with-relations-as-morphisms.

There is the faithful functor Set $\to$ Rel that simply keeps sets intact and sends a function to its graph. And there is also a faithful functor Rel $\to$ Set mapping $X\to 2^X$ and $R\subseteq X\times Y$ to $R_*:2^X\to 2^Y, A\mapsto R_*(A)=\{ y\in Y\; |\; \exists x \in A : (x,y)\in R \}$.

Despite the trivial foundational fact that set theoretical functions are defined to be a special kind of relations, it seems that in category theory Set has priority on Rel. For example the Yoneda's lemma is stated for Set; and people talk of simplicial sets, not simplicial relations; and the category Rel is just retrieved as "the Kleisli category of the powerset endofunctor on Set" (I just learned this from wikipedia) and it doesn't seem to be so ubiquitous as Set (but this impression might just depend on my ignorance in category theory).

3) Are functions really more central/important than relations in category theory? If so, is it just for historical reasons or there are some more "intrinsic" reasons? E.g. is there an analogous of Yoneda's lemma for Rel?

Answer 1

Regarding question 3, one can make an argument that actually the fundamental object is "Set together with Rel". The bijective-on-objects inclusion of Set into Rel is a categorical structure that can be expressed as an F-category, a proarrow equipment, or a double category. All of these are slightly different ways of talking about a (2-)category that has two classes of morphisms.

It turns out that in the particular case of Set+Rel, either class of morphisms can be recovered from the other. The relations are the jointly monic spans of functions, while the functions are the relations with right adjoints. The same fact holds in much greater generality: from any regular category (whose morphisms are "function-like") we can construct a unitary tabular allegory (whose morphisms are "relation-like"), and conversely. The two are really just the same structure expressed in different ways. Sometimes it's more convenient to use the functions; sometimes it's more convenient to use the relations; and sometimes we want both encapsulated in a single structure.

The importance of this sort of two-kinds-of-morphism structure becomes more pronounced as you go up in categorical dimension. For instance, the analogous thing for categories is the inclusion of Cat (whose morphisms are functors) into Prof (whose morphisms are profunctors). In this case, Prof can be constructed from Cat, but with rather more difficulty than Rel is constructed from Set, while Cat cannot be recovered 2-categorically from Prof (e.g. Morita-equivalent categories are equivalent in Prof, but not in Cat). On the other hand, profunctors seem an essential ingredient for doing "formal category theory", e.g. in the formulation of weighted limits and colimits, so it's valuable to keep both kinds of morphism around.