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?

Not really answering the question, but: In the foundational theory SEAR (http://ncatlab.org/nlab/show/SEAR), relations are a primitive object, and functions are defined as special relations. From the first four axioms (numbered 0,..,3) one arrives at the fact Rel is a power allegory (http://ncatlab.org/nlab/show/allegory) and the subcategory of sets and functions is a well-pointed topos. There are some remarks at the nLab page on allegories which may be useful. — David Roberts, Feb 07 '13 at 01:34
I don't really understand (3)- what kind of analogue to Yoneda's Lemma would you envision? — Daniel Moskovich, Feb 07 '13 at 04:32
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 07 '13 at 08: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 07 '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 07 '13 at 13:31
@DanielMoskovich: Yoneda's lemma states that there's a fully faithful embedding of a category $\mathcal{C}$ into the category $\mathsf{Cat}(\mathcal{C}^{\mathrm{op}},\mathsf{Set})$ . Perhaps a Yoneda's lemma for Rel Which is about the relationship between $\mathcal{C}$ and $\mathsf{Cat}(\mathcal{C}^{\mathrm{op}},\mathsf{Rel})$ , or maybe something less naif. Also, simplicial sets are objects of $\mathsf{Set}^\Delta$ ; what about $\mathsf{Rel}^\Delta$ ? — Qfwfq, Feb 07 '13 at 16:32
Another question could be: $\mathsf{Set}$ is to a general topos as $\mathsf{Rel}$ is to what structure? — Qfwfq, Feb 07 '13 at 16:38
@Zhen Lin: Partial functions are useful as a web search shows. Also real analysis is nicely expressed in terms of partial functions. Solutions of first order differential equations with a parameter $y$ are often partial functions whose domain varies with $y$ . How to express that this partial function varies continuously, smoothly, etc? Where is the functional analysis of partial functions? The change from monoid to category, group to groupoid, is algebraically the change from a total to a partial algebraic structure, and makes a big difference. The step is not easy, and often not welcomed. — Ronnie Brown, Feb 07 '13 at 17:24
@Ronnie Brown: maybe a modern way to conceptualize partial-function solutions of ODEs and PDEs is just sheaf theory. If the "sheaf of local solutions" of a differential operator is taken as a subsheaf of the sheaf of germs of continuous/smooth/analytic functions, it allows you to express that the solutions vary continuously/smoothy/analytically etc. — Qfwfq, Feb 07 '13 at 21:44
Too short and too partial for an answer: I think that functions are on the technical side whereas relation are on the conceptual side. A function (partial) "is" a partition whereas a relation thought as a bipartite graph is much more complicated.
A related (no pun) question is that partial functions should be used instead of function. — Jérôme JEAN-CHARLES, Feb 08 '13 at 11:15
@Qfwfq: $\textbf{Set}$ is to toposes as $\textbf{Rel}$ is to power allegories. — Zhen Lin, Feb 08 '13 at 19:07
I think the main reason we stick so close to functions is purely historical. Set theory and category theory are natural generalizations of things that already existed - that is, geometry, space and time, as was said above. However, I'd also say that there seems to be a general theme of looking at relation-eqsue objects when one starts working with motives. That is, subsets of $X\times Y$ satisfying some property, rather than functions $X\to Y$ . — Jonathan Beardsley, Aug 28 '14 at 20:00
A question from math.se about homomorphic relations: http://math.stackexchange.com/questions/148715/can-we-extend-the-definition-of-a-homomorphism-to-binary-relations — Michał Masny, Aug 28 '14 at 20:54
Basically the same question on math.se -- though this MO question came first. — Tim Campion, May 02 '18 at 21:05
In probability theory we have the notion of a coupling (or joining), which is to probability-preserving maps as relations are to sets. See for instance the Monge and Kantorovich formulations of the optimal transport problem https://en.wikipedia.org/wiki/Transportation_theory_(mathematics) : the Monge version requires a measure-preserving transport map, whereas the Kantorovich problem merely asks for a transportation plan that need not arise from a map. (But, if there is enough convexity and smoothness present, one can show that the plan must be a map.) — Terry Tao, Mar 29 '24 at 16:11

score 44 · Accepted Answer · answered Feb 07 '13 at 13:24

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.

score 18 · Answer 2 · answered Mar 25 '16 at 18:14

Taking up remarks near the end of the OP, and somewhat in line with Mike Shulman's answer, I'd like to underline the structural interplay between $\mathbf{Set}$ and $\mathbf{Rel}$ to indicate one point of entry into the notion of topos.

The bijective-on-objects inclusion $i: \mathbf{Set} \to \mathbf{Rel}$ has a right adjoint $p: \mathbf{Rel} \to \mathbf{Set}$ .

This means that there is a natural bijective correspondence between relations $iA \nrightarrow B$ and functions $A \to pB$ . Here $pB$ is of course the power set of $B$ .

Quite a lot of fundamental structure comes out of this. For example, the counit of the adjunction is the elementhood relation $\ni_A: ipA \nrightarrow A$ . The unit of the adjunction $A \to piA$ is the singleton function $a \mapsto \{a\}$ . The multiplication of the monad $pi$ with components $\mu_A: pipiA \to piA$ is the function $\bigcup_A:ppA \to pA$ , taking a collection of subsets $\mathcal{A} \in ppA$ to the union $\bigcup \mathcal{A} \in pA$ .

Yes, as the OP quoted Wikipedia:

$\mathbf{Rel}$ is "just" the Kleisli category (of free algebras) of the monad $pi: \mathbf{Set} \to \mathbf{Set}$ .

But turnabout is fair play:

$\mathbf{Set}$ is "just" the Eilenberg-Moore category (of coalgebras) of the comonad $ip: \mathbf{Rel} \to \mathbf{Rel}$ .

I find it hard to play favorites between $\mathbf{Rel}$ and $\mathbf{Set}$ , because of this structural interpenetration between the two. You might prefer $\mathbf{Set}$ because it is complete and cocomplete. On the other hand, you might prefer $\mathbf{Rel}$ because of its self-duality ( $\mathbf{Set}$ breaks the symmetry enjoyed by $\mathbf{Rel}$ ), and because $\mathbf{Rel}$ enjoys a richer structure of honest 2-category (whose 2-cells are inclusions between relations of the same type $A \nrightarrow B$ ). It's probably best to see them welded into a whole, as a certain type of double bicategory as in Mike's answer.

Now let me use these ideas to give a snappy definition of topos. As many readers will know, the notion of regular category $C$ is useful because (among other things) it allows a decent calculus of relations. Thus from a regular category we may form a category of internal relations in $C$ , denoted $\mathbf{Rel}(C)$ . Again there is a bijective-on-objects inclusion $i: C \to \mathbf{Rel}(C)$ .

Definition: A topos is a regular category $C$ such that the inclusion $i$ has a right adjoint $p$ .

score 11 · Answer 3 · edited Jul 17 '14 at 02:34

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 coinciding with the cartesian product in $\mathsf{Set}$ (this is not the cartesian product in $\mathsf{Rel}$ , which coincides with the coproduct in $\mathsf{Set}$ ).

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 07 '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 07 '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 07 '13 at 13:12
Your observation is the content of the 2 page Annals paper by Wedderburn in my answer (who assumed inverses were respected). — Benjamin Steinberg, Feb 07 '13 at 14:41

score 10 · Answer 4 · 2013-06-26T17:45:31.640

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.

Benjamin Steinberg · Answer 5 · 2013-02-07T01:39:11.683

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).

Ronnie Brown · Answer 6 · 2013-05-18T21:27:34.033

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.

score 5 · Answer 7 · answered May 02 '18 at 21:36

(With apologies for reviving an old question which already has many answers) here are two perspectives:

Ponder the fact that

$\mathsf{Set}$ is complete and cocomplete. $\mathsf{Rel}$ is not.

For example, the total relation $1 \to 2$ and the graph of your favorite function $1 \to 2$ fail to have a coequalizer in $\mathsf{Rel}$ ; see here for a proof. See also the Milius paper linked to by Martin Brandenburg above for an example of an $\omega$ -chain which doesn't have a colimit in $\mathsf{Rel}$ .

Thus we "reduce" the question of why $\mathsf{Set}$ is "more fundamental" than $\mathsf{Rel}$ to the question of why limits and colimits are so fundamental to category theory. Loosely, I'd say that limits and colimits are to category theory as universal and existential quantifiers are to logic -- without them, you're simply very limited in the kinds of things it's possible to say at all.
An object $X$ of a category $\mathcal C$ is studied by looking at the set of possible "measurements" $\mathcal C(X,A)$ by objects $A$ , or dually by "probing" via the set of maps in $\mathcal C(B,X)$ . In category theory, we get a lot of juice out of the fact that these two ways of looking at an object $X$ are quite different, and we can play them off one another. But in a self-dual category like $\mathsf{Rel}$ , you can't tell the difference between the object doing the measuring and the object being measured -- it's like there's feedback in the measurement process. Everything is simply too jumbled together to make sense of the data you're recording. To mix metaphors some more, $\mathsf{Set}$ is like a cleaner operating room to work in than $\mathsf{Rel}$ , or an experimental environment where more of the environmental variables are well-controlled.

"With apologies for reviving an old question which already has many answers": I don't think one has to apologize for this, after all its a good aspect of MO that answers to a question can be made more and more varied and deep in time. Plus, someone might just bump onto the question today so it's not at all "old" for him/her. :) — Qfwfq, May 02 '18 at 23:17

score 4 · Answer 8 · answered Feb 07 '13 at 14:44

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.

Włodzimierz Holsztyński · Answer 9 · 2013-05-19T21:03:53.343

4

@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).

edited May 19 '13 at 21:03

answered May 18 '13 at 23:34

Włodzimierz Holsztyński

7,472

1

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 00: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
4

@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
@Wlodzimierz Holsztynski: is the historical reconstruction you hint at based on some objective documents, or is it just a conjecture? – Qfwfq May 19 '13 at 11:36
By a partial function $f : X \to Y$ I mean a triple consisting of $X,Y, Gr(f)$ where $Gr(f)$ is the graph, a functional subset of $X \times Y$ , so that $dom(f), range(f)$ are subsets of $X,Y$ resp. Historically, category arose from algebraic topology, where all functions are total. Ehresmann's approach to category theory arose from analysis, and local-to-global questions, hence his difference in style, and relation to geometry. My definition of "higher dimensional algebra" is the study of algebraic structures with partial operations whose domains are defined by geometric conditions. – Ronnie Brown May 19 '13 at 14:21
To add to the last comment: Ehresmann's interest in analysis led him to grouoids which he applied to foliations, and also developed the notion of differential groupoid, now called Lie groupoid, and also topological groupoid, and fibre bundles. He used in essence pseudo groups, and related them to ordered groupoids. See also my article `Three themes in the work of Charles Ehresmann: Local-to-global; Groupoids; Higher dimensions', [147] on my publication list. By contrast, the notion of groupoid has been notably absent or not much developed in most algebraic topology books. – Ronnie Brown May 19 '13 at 14:57
2

@Qfwfq. Yes you can easily express surjectivity, you just have to specify with respect to what codomain, which in practice is often clear from context. I think my point trumps any formal concern about convenience of language-- The notion that codomain is a part of the identity of a function leads to the absurdity that there are two "distinct" functions that comprise the same set of ordered pairs, yet "have different codomains." But there's nothing to distinguish them! The correct thing to say is the are many ways of talking about the same function. – Monroe Eskew May 19 '13 at 16:12
3

@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. – Włodzimierz Holsztyński May 19 '13 at 19:26
4

@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
@Wlodzimierz: Now here's an example for you. Consider the set-theoretical statement. ${f|f: \omega\to\omega_1 }= \bigcup_{\alpha<\omega_1} {f|f: \omega\to\alpha }$ . This is true in ZFC, but in the category theory conventions it could not be. Now I'm sure there is an elegant way of handling this, as set theory would have a way of handling your homology example by noting the functors are not functions with inputs just these identity functions (qua graphs) but rather some n-tuple of relevant information including the codomains. I suppose this is just a matter of convention. – Monroe Eskew May 20 '13 at 00:26
@mbsq: I'll guess and signal a direction toward an answer (I don't know your formalism): ${f|f:\omega\rightarrow \omega_1} =\bigcup_{\alpha < \omega_1}{i_{\alpha\omega_1}\circ(f:\omega\rightarrow\alpha)}$ . (you and OM are killing me with $\LaTeX$ . Yes, this is all just a matter of convention--said Alice in Wonderland. – Włodzimierz Holsztyński May 20 '13 at 05:18
It took me only a dozen editions to get $\LaTeX$ right above. It still doesn't look pretty but I am not going to beautify it :-) – Włodzimierz Holsztyński May 20 '13 at 05:20
1

I am reminded that Paul Suppes has a book on logic which defined a function in terms of a set of ordered pairs, but also used the term "onto" or "surjective" for a function. He was amazed when I pointed out the difficulty of this, and discussed it at a conference, when others were also suitably amazed! – Ronnie Brown May 23 '13 at 13:37

score 2 · Answer 10 · answered Feb 07 '13 at 10:45

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).

Włodzimierz Holsztyński · Answer 11 · 2013-05-18T23:24:35.833

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.

score 1 · Answer 12 · answered May 20 '13 at 06:23

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).

Lehs · Answer 13 · 2014-08-28T17:04:13.283

Functions reminds about cause and effect while relation are more like interaction and more diffuse and complex. But one reason why relations not is more common as morphisms, could depend on the fact that functions as objects has commutative squares as canonical morphisms, which does not works so good for relations since commutation do not preserve the structure of relations (compare preserving of graph structures). For functions commutation preserve this structure on the function. However, there is a canonical extension of commutation that might be used instead: $\require{AMScd}$ $\begin{CD} A @>u>> B\\ @VrV\quad\;\;\,\displaystyle \looparrowright V @VVsV\\ \bar{A} @>>\bar{u}> \bar{B} \end{CD}$ where the $\looparrowright$ stands for a relation between the four binary relations $r,s,u,\bar{u}$ that equals to commutativity if the relations are functions:

$a \underline{u} b \wedge \bar{a}\bar{\underline{u}} \bar{b} \Rightarrow (a \underline{r}\bar{a} \Rightarrow b \underline{s}\bar{b})$ , for all $a \in A$ , $\bar{a}\in \bar{A}$ , $b \in B$ , $\bar{b} \in \bar{B}$ .

Now it holds that: $\begin{CD} A @>u>> B@>v>>C\\ @VrV\quad\;\;\,\displaystyle \looparrowright V @VsV\quad\;\;\,\,\displaystyle \looparrowright V @VVtV\\ \bar{A} @>>\bar{u}> \bar{B}@>>\bar{v}> \bar{C} \end{CD} \qquad\Rightarrow\qquad \begin{CD} A @>vu>> C\\ @VrV\quad\;\;\,\displaystyle \looparrowright V @VVtV\\ \bar{A} @>>\bar{v}\bar{u}> \bar{C} \end{CD}$ This can for example be used to define categories of mathematical structures as:

$\star$ Monoid structure $M\times M \overset{r}\longrightarrow M$ , where $r$ is the multiplication

$\star$ Topological structur $\mathcal{P}(X)\overset{r}\longrightarrow X$ where $r$ is closeness/nearness: $M\underline{r}x\Leftrightarrow x\in \bar{M}$

$\star$ Metric spaces $\mathbb{R}\times X\overset{r}\longrightarrow X$ where $r$ is $(\xi,x)\underline{r}x'\Leftrightarrow d(x,x')\leq\xi$

The structure categories are richer than the constructs. For example, several structures for the same metric can be defined, giving arise to different morphisms (which trivially transform to the morphisms in the corresponding construct). The main idea is to describe mathematical structures as relations

$F(X) \overset{r}\longrightarrow X^{I}$ for some functor $F$ on Rel, where $\begin{CD} F(X) @>F(f)>> F(Y)\\ @VrV\qquad \;\;\displaystyle \looparrowright V @VVsV\\ X^{I} @>>f^{I}> Y^{I} \end{CD}$ gives the condition on the function $f$ for the diagram to be a morphism. Note that $F(f)$ in general is a relation.

score 1 · Answer 14 · answered Mar 29 '24 at 15:54

One way to approach the concepts of "elements" (or "its") and "distinctions" (or "dits") is to start with the category-theoretic duality between subsets and quotient sets (= partitions = equivalence relations): "The dual notion (obtained by reversing the arrows) of `part' [subobject] is the notion of partition." (Lawvere & Roseburgh, p. 85). That motivates the two dual forms of mathematical logic: the Boolean logic of subsets and the logic of partitions (Ellerman, David. 2014. “An Introduction to Partition Logic.” Logic Journal of the IGPL 22 (1): 94–125. https://doi.org/10.1093/jigpal/jzt036) . If partitions are dual to subsets, then what is the dual concept that corresponds to the notion of elements of a subset? The notion dual to the elements of a subset is the notion of the distinctions or dits of a partition (pairs of elements in distinct blocks of the partition).

The duality between elements ("its") of a subset and distinctions ("dits") of a partition already appears in the very notion of a function between sets in the category $Set$ . The concepts of elements and distinctions provide the natural notions to specify the binary relations, i.e., subsets $R\subseteq X\times Y$ , that define functions $f:X\rightarrow Y$ .

A binary relation $R\subseteq X\times Y$ transmits elements if for each element $x\in X$ , there is an ordered pair $\left( x,y\right) \in R$ for some $y\in Y$ .

A binary relation $R\subseteq X\times Y$ reflects elements if for each element $y\in Y$ , there is an ordered pair $\left( x,y\right) \in R$ for some $x\in X$ .

A binary relation $R\subseteq X\times Y$ transmits distinctions if for any pairs $\left( x,y\right)$ and $\left( x^{\prime},y^{\prime }\right)$ in $R$ , if $x\not =x^{\prime}$ , then $y\not =y^{\prime}$ .

A binary relation $R\subseteq X\times Y$ reflects distinctions if for any pairs $\left( x,y\right)$ and $\left( x^{\prime},y^{\prime}\right)$ in $R$ , if $y\not =y^{\prime}$ , then $x\not =x^{\prime}$ .

The dual role of elements and distinctions can be seen if we translate the usual characterization of the binary relations that define functions into the elements-and-distinctions language. In the usual treatment, a binary relation $R\subseteq X\times Y$ defines a \textit{function} $X\rightarrow Y$ if it is defined everywhere on $X$ and is single-valued. But "being defined everywhere" is the same as transmitting (or "preserving") elements, and being single-valued is the same as reflecting distinctions so the more natural definition is:

a binary relation $R$ is a function if it transmits elements and reflects distinctions.

What about the other two special types of relations, i.e., those which transmit (or preserve) distinctions or reflect elements? The two important special types of functions are the injections and surjections, and they are defined by the other two notions:

a function is injective if it transmits distinctions, and

a function is surjective if it reflects elements.

The origin of the 'reverse-the-arrows' duality is in the definition of the concrete morphisms in $Set^{op}$ , i.e., cofunctions, which is interchange the role of elements and distinctions in the definition of a function. That is, a cofunction is a binary relation the transmits distinctions and reflects elements. Then the notion of functions and cofunctions is abstracted in abstract categories to give the reverse-the-arrows duality.

It all traces back to the two dual logics of subsets and partitions, a duality that at the concrete or granular level is the elements & distinction or its & dits duality--since reversing the roles of elements and distinctions in the ur-category of $Sets$ to go to $Sets^{op}$ just reverses the arrows.

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

14 Answers14

Linked