# Why is Set, and not Rel, so ubiquitous in mathematics?

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?

-
Your first sentences in, hm, interesting. –  Mariano Suárez-Alvarez Feb 7 '13 at 3:25
Before jumping all the way to relations, one might take an intermediate step and ask why mathematics focuses on total functions instead of partial functions. I think the answer to both questions is the same, however. –  Zhen Lin Feb 7 '13 at 8:19
I like to think of the role of functions as "the arrow of time" of mathematics. They make Set not equivalent to its opposite the way Rel is, and this is the root of an enormous amount of duality symmetry-breaking in category theory. –  Eric Wofsey Feb 7 '13 at 10:41
Just a remark: functions, not relations, usually inherit the algebraic structure of the co-domain. The sum and product of relations on $\mathbb{R}$ can be defined too, but looses many algebraic properties. –  Pietro Majer Feb 7 '13 at 13:31
@Qfwfq: $\textbf{Set}$ is to toposes as $\textbf{Rel}$ is to power allegories. –  Zhen Lin Feb 8 '13 at 19:07

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.

-

Concerning your first question, here is an example from (microlocal) analysis and symplectic geometry: Fourier Integral Operators (FIO) correspond to canonical relations which are Lagrangian submanifolds of $T^\ast Y\times T^\ast X$, where $X$ and $Y$ are the source and the target manifold, respectively. Composition of FIOs corresponds to the composition, as relations, of their underlying canonical relations. The solution operator of (the Cauchy problem of) the wave equation is an FIO; here two points in the cotangent bundle are related if they are on the same bicharacteristic (=solution curve of Hamilton's canonical equations). The pull-back by a smooth map $f:Y\to X$ is an FIO, $f^\ast$. Here the relation is the conormal bundle of the graph of $f$ (after one of the fiber variables has been multipled by $(-1)$). In case $f$ is a diffeomorphism, the associated symplectomorphism $T^\ast Y\to T^\ast X$ is the canonical relation of $f^\ast$. The FIOs which correspond to the identity on $T^\ast X$ are precisely the pseudo-differential operators on $X$. When dealing, for example, with wave propagation in manifolds with boundaries, the FIO calculus, of which an essential part is the composition of canonical relations, is very convenient and useful.

-

2) The definition of "homomorphic relation" for groups in the question only refers to the multiplication, but it is more natural also to require compatibility with inverses (because we are not talking about semigroups which happen to be groups, but about groups; although it is well-known that the forgetful functor is fully faithful, i.e. the homomorphisms are the same, this is not the case for the "homomorphic relations"). Then homomorphic relations $R$ on a group correspond 1:1 to normal subgroups $N$ of the group (via $(x,y) \in R \Leftrightarrow x y^{-1} \in N$). More generally, a congruence relation on an algebraic structure is an equivalence relation on the underlying set which is compatible with all the operations. Equivalently, the quotient of the underlying sets becomes an algebraic structure of the same signature such that the projection becomes a homomorphism. The homomorphism theorem holds in this general setting. I hope that this refutes the claim that we never see homomorphic relations.

3) The Yoneda Lemma holds for enriched categories over symmetric monoidal closed categories, and $\mathsf{Rel}$ is a symmetric monoidal closed category, with tensor product $(X,R) \otimes (Y,S) = (X \times Y,R \times S)$, where $R \times S$ abbreviates the relation $\{((x,y),(x',y')) : (x,x') \in R, (y,y') \in S\}$.

Note that $\mathsf{Set}$ has many more convenient properties than $\mathsf{Rel}$. For example, Milius' paper On Colimits in Categories of Relations explains that $\mathsf{Rel}$ has not all colimits of $\omega$-chains.

-
$\mathsf{Rel}$ is not cartesian closed. It is compact closed, and its tensor product becomes cartesian product when restricted to sets and functions, but that tensor product is not cartesian product in $\mathsf{Rel}$. In fact, notice that cartesian product and cartesian coproduct coincide in $\mathsf{Rel}$ (since, e.g., every object is self-dual), and this coproduct is the coproduct $+$ when restricted to $\mathsf{Set}$. (Also, a compact closed category whose tensor is cartesian product is equivalent to the terminal category, since maps $A \to B$ there transform to $A \times B^\ast \to 1$.) –  Todd Trimble Feb 7 '13 at 12:00
Thank you. I've corrected it and added a description of the tensor product. At first sight it is the categorical product, but of course this is not the case. –  Martin Brandenburg Feb 7 '13 at 12:52
Although you have to be a little careful in formulating the enriched Yoneda lemma when the enriching category is not complete, since in that case enriched functor categories do not in general exist. –  Mike Shulman Feb 7 '13 at 13:12
For finite groups the inverse condition is automatic –  Benjamin Steinberg Feb 7 '13 at 14:33
Your observation is the content of the 2 page Annals paper by Wedderburn in my answer (who assumed inverses were respected). –  Benjamin Steinberg Feb 7 '13 at 14:41

Notion 2 was first considered for groups in Wedderburn, J. H. M. Homomorphism of groups. Ann. of Math. (2) 42, (1941). 486–487. But the main results show for groups the notion is not so exciting. In semigroup theory relations satisfying 2 are called relational morphisms. They form the key notion of morphism in finite semigroup theory. They were introduced by Eilenberg and Tilson in Eilenberg's book on finite semigroup theory.

For instance, one can consider which elements of a finite semigroup relate to 1 under all possible relational morphisms to a finite group. The answer is the smallest subsemigroup containing all idempotents and closed under $x\mapsto axb$ whenever aba=a or bab=b. One proof uses that the product of finitely generated subgroups of a free group is closed in the profinite topology (which was conjectured by semigroup theorists interested in this problem and proved by Ribes and Zalesskii using profinite groups acting on profinite trees).

-

I think there is a subquestion, or related (!) question, namely why is there little functional analysis of partial functions? Teaching real analysis to students makes it clear that it is all about partial functions $\mathbb R \to \mathbb R$ , each of which has a domain and range, which we often want to know. Now the solutions of differential equations with a parameter are often regarded as smooth in the parameter, but usually only with fixed domain. For example it is reasonable to suggest that the family of partial functions $f_y: x \mapsto \log(x+y)$ varies continuously with $y$, but of course the domain varies with $y$, so the answer is not so clear, especially if you suggest, why not?, that $f_y$ is, or should be, a smooth function of $y$.

Actually a web search on "partial functions" gives quite lot of hits, but I am not sure of anything definitive.

-

Related to question 1), another example of some non-functional relations widely used in algebraic geometry is "rational functions" between varieties, side they are not defined everywhere, and in a sense may be thought as "multiply defined" (think of the birational map from a variety to its blow-up at some point).

Actually, traditional (e.g. italian) algebraic geometry put the notion of rational functions at the foundation of algebraic geometry. In a development that interestingly parallels the emergence of the concept of function as a fundamental notion in the nineteenth century, but one century later, the modern foundations of algebraic geometry (Weil, Zariski, and most importantly Grothendieck) moved the emphasis from the notion of rational functions to the notion of morphism.

-

I think monotone operators qualify for question 1:

A mapping $T:X\to X^*$ from a Banach space to its dual is said to be monotone, if for all $u,v\in X$ it holds that $$\langle Tu - Tv, u-v\rangle\geq 0.$$

This generalizes to relations from $X$ to $X^*$ (i.e. subsets of $X\times X^*$): $G\subset X\times X^*$ is said to be monotone of for all $(x,u),(y,v)\in G$ it holds that $$\langle x-y,u-v\rangle \geq 0.$$

Relations (or multifunction) like this appear, e.g., as subgradients of convex functions on Banach spaces. If $f: X\to ]-\infty,\infty]$ is convex, its subgradient $$\partial f(x) = \{x^*\in X^*\ :\ \forall y:\ f(y)\geq f(x) + \langle x^*,y-x\rangle\}$$ can be viewed either a set-valued mapping $\partial f: X \to 2^{X^*}$ or as a multifunction $\partial f:X\rightrightarrows X^*$ or, by identifying it with its graph $\mathrm{gph}(\partial f) = \{(x^*,x)\in X\times X^*\ : x^*\in\partial f(x)\}$, as subset of $X\times X^*$ (indeed, a monotone one).

-

Here are my impressions:

Are apples more important than fruits? (Usually we tend to compare apples and oranges :-).

We have--in the finite case--a numerical metaphor which indicates a vague answer. The number of functions   $A\rightarrow B$   is   $|B|^{|A|}$,   while the number of the relations in   $A\times B$   is:

$$2^{|A|\times |B|}\ \ =\ \ \left(2^{|B|}\right)^{|A|}$$

The number of relations is overwhelming. The number of functions is positioned between "too few" and "too many"; and the meaning of a function is more meaningful, it is between "too special" and "too general". The notion of a relation is by comparison "too general" to play intensively a leading role by itself, as such.

The notion of a (self)function   $A\rightarrow A$   can be compared to other oranges like linear orderings (i.e. permutations), partial orderings and equivalence relations in   $A$.   Let   $a:=|A|$.   There are   $a^a$   of self-functions,   $a!$   of linear orderings, over   $2^{\lfloor a/2\rfloor\cdot\lceil a/2\rceil}$   of partial orderings but still under   $a!\cdot 2^{a\cdot(a-1)/2}$   (hm, a lot), and there are under   $a^a$   of equivalence relations.

Functions represent longing for determinism (predictability).

Isn't the accent on functions relatively modern? Ancient Greeks didn't talk much about functions.

PS. The multitude of partial orders combined with the importance of the notion (they happen to be $T_0$-topologies too :-) is puzzling.

-

@Ronnie Brown:

The emphasis on (total) functions comes from the understanding reflected by theory of categories (e.g. by algebraic topology). In the past the distinction between a total function and a partial function was not accented. The functions induced by partial functions are so drastically different from the total case in algebraic topology that there arose the need of a very strong distinction between the partial and the total functions. Also for the more subtle distinction of two functions with the same graph, and the same domain but different codomains (most of the time one is contained in the other in the mathematical practice).

Thus today when we deal with a partial function we just call it a (total) function but with a smaller domain; thus we hardly see partial functions anymore.

@mbsq, Alice in Wonderland payed words to mean what she wanted them to mean. Mathematical community is Alice in Wonderland (except here and there for an old age dementia). Let   $B\ \ S$   be the unit closed ball in   $R^n$   and its boundary (sphere), so that   $S\subseteq B\subseteq R^n$. Consider three "identity" functions, the later two induced by the first one:

$$I_B:B\rightarrow B$$ $$i_{SB} : S\rightarrow B$$ $$I_S : S\rightarrow S$$

so that   $i_{SB} = I_B|S$. In the old times (of mostly local analysis) the "identity" functions were kind of taken for granted and mostly invisible like well behaved children in strict families. There was not much need to talk about them explicitly. In that old spirit you are saying that to call   $I_S$   and   $i_{SB}$   different functions is absurdity. However, let   $H_n$   be the n-th homology functor. The homomorphisms induced by the identity inclusions are no more "identities", i.e. they are not necessarily monomorphisms, they can be in general just arbitrary homomorphisms. Thus they cannot be treated like polite subdued children anymore. In particular we need in our notions and notation an easy distinction between   $I_S$   and   $i_{SB}$ because the induced homomorphisms are dramatically different:   $H_n(I_S) = I_{\mathbb Z}$   is a non-zero identity homomorphism on   $\mathbb Z$,   while   $H_n(i_{SB})$   is the zero homomorphism. When two objects induce so much different effects then it is not an absurdity to call these objects different. These days children are not subdued anymore. Our definitions should reflect the importance of the codomain (as $S$ versus $B$ in the example above).

-
What does it mean for two functions f,g to have the same graph but different codomains? In what way are they distinct functions? Clearly they are not. Set theory says they are the same object. What does is mean for f to "have codomain B"? Doesn't that depend on the presentation or definition and not some intrinsic property of f? I think that the standard category theory treatment where cod(f) is a single well-defined object was an error, although not one of any real mathematical consequence. –  Monroe Eskew May 19 '13 at 0:28
@mbsq: I think the identification of functions with their graphs, which is prevalent in Logic I presume for practical reasons (you just say $f\subseteq g$ to express that "$g$ is an extension of $f$"), doesn't reflect the mathematical practice, in which a function is actually a triple $(f,\mathrm{dom}(f),\mathrm{cod}(f))$. –  Qfwfq May 19 '13 at 11:33
@mbsq: (continued) Codomain is very important in the everyday treatement of functions, otherwise you wouldn't be able to conveniently express "surjectivity": we want to be able to neatly express -say- that an operator between Hilbert spaces has dense range (note that the range may not be a complete inner product space) but is not surjective. –  Qfwfq May 19 '13 at 11:33
@Qfwfq, there was plenty of (objective) evidence during my years. I'll expand my "Answer" above to reflect it somewhat. -o=o- @mbsq, what you call so cheerfully "absurdity" is the mathematical reality at least since Eilenberg + (Mac Lane, Cartan, Steenrod, Grothendieck, ...), while I am old enough to remember the good set-theoretical, pre-category times. –  Wlodzimierz Holsztynski May 19 '13 at 19:26
@msbq: if a function is defined as simply a set of ordered pairs, then indeed your claimed absurdity, “there’s nothing to distinguish them” is one. But if a function is defined as including its domain and codomain, then it’s not an absurdity at all — they’re distinguished by their codomains! Which definition is the right one is clearly a debatable and somewhat subjective question — many people would argue each, and perhaps the right answer is that depending on the field, each can sometimes be more fruitful — but calling this issue an “absurdity” is rather unhelpful. –  Peter LeFanu Lumsdaine May 19 '13 at 23:53

It's hard to edit long multi-part Answers. Sorry for writing another one.

@Qfwfq: It's a common knowledge that for centuries perhaps there was a vague identification of function-formulas and functions. Even in the quite modern times many textbooks say that a function is a rule assigning a value to an argument--something in this spirit. They are shy about domains, and especially about the codomains.

Even as late as fifteen years ago, and perhaps today too, typical exercises from typical Calculus textbooks present students with formulas, and ask them to provide the domain. This implies that the domain is not a part of the definition, that it is something to be deduced. A tricky exercise would be for formula

$$\frac{x^2-1}{x+1}$$

On one hand, as it is now,   $-1$   is forbidden (illegal); and on the other hand this function is--hm--equal to   $x-1$. I don't know if there is a uniform policy among all these undergraduate Calculus textbooks.

After WWI the Cantor set theory certainly found its home in Poland where about each mathematical monograph had a nice introduction on set theory and elements of point-set topology, and they used a clean and consistent set-theoretical language. It had amounted to certain mathematical culture, which was modern in the pre-categorical times. Today this style, at a more advanced stage, is represented for instance by Engelking's monograph on General Topology. In particular, he makes a clear distinction between the Cartesian and diagonal product of functions (the latter being these days a standard notion of the theory of categories). For a contrast, the great Soviet mathematics, powerful and imposing as it was, was not so fond of such niceties. In particular, outstanding mathematician and great writer and teacher Igor Schafarevich would be at peace with calling diagonal product of mappings to be a cartesian product. His lectures were still great of course. Many excellent and useful Soviet mathematical books looked naive and old-fashioned from the point of view of set theoretical notation.

Nevertheless, even with the Polish set-theoretical tradition, the definition of a function from $X$ to $Y$ would sound something like: a set   $f$   of ordered pairs   $(x\ y)\in f$   such that:

• $$\forall_{x\in X}\exists_{y\in Y}\quad(x\ y)\in f$$
• $$\forall_{x\in X}\forall_{y\ y'\in Y}\quad\left(\left(\left(x\ y\right)\ \left(x\ y'\right)\ \in\ f\right)\ \ \Rightarrow\ \ \left(y=y'\right)\right)$$

This is pretty good, and better then a function is a rule but it implicitly creates not one but two notions: a function, and a function from $X$ to $Y$, the former being just a graph (I call them functional graphs or function graphs in general, i.e. a function graph is simply any set which has only ordered pairs for its elements; hm,   graf   would be a perfect name, with f indicating a connection with the notion of a function).

The ultimate explicit treatment of functions as ordered triples consisting of domain, codomain, and the graph, is due to the theory of categories, I would think.

REMARK  It is ironic that in the case of SET alone--in an isolation from other categories via functors--it is not necessary to specify the domain (it is implied by the graph), while we still have to indicate the codomain.

@Qfwfq, I hope that the above rumbling partially answers your question. If you'd like me I may still check a few books in my possesion for specific references and quotes. (BTW, may I address you QfwfQ? Sometimes I like symmetry).

-