73
$\begingroup$

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?

$\endgroup$
15
  • 9
    $\begingroup$ 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. $\endgroup$
    – Zhen Lin
    Feb 7, 2013 at 8:19
  • 31
    $\begingroup$ 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. $\endgroup$ Feb 7, 2013 at 10:41
  • 7
    $\begingroup$ 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. $\endgroup$ Feb 7, 2013 at 13:31
  • 3
    $\begingroup$ @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. $\endgroup$
    – Qfwfq
    Feb 7, 2013 at 21:44
  • 5
    $\begingroup$ @Qfwfq: $\textbf{Set}$ is to toposes as $\textbf{Rel}$ is to power allegories. $\endgroup$
    – Zhen Lin
    Feb 8, 2013 at 19:07

13 Answers 13

42
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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$.
$\endgroup$
11
$\begingroup$

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.

$\endgroup$
5
  • 11
    $\begingroup$ $\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$.) $\endgroup$
    – Todd Trimble
    Feb 7, 2013 at 12:00
  • $\begingroup$ 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. $\endgroup$ Feb 7, 2013 at 12:52
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 7, 2013 at 13:12
  • $\begingroup$ For finite groups the inverse condition is automatic $\endgroup$ Feb 7, 2013 at 14:33
  • $\begingroup$ Your observation is the content of the 2 page Annals paper by Wedderburn in my answer (who assumed inverses were respected). $\endgroup$ Feb 7, 2013 at 14:41
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

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

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

$\endgroup$
1
  • 1
    $\begingroup$ "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. :) $\endgroup$
    – Qfwfq
    May 2, 2018 at 23:17
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
13
  • 1
    $\begingroup$ 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. $\endgroup$ May 19, 2013 at 0:28
  • 4
    $\begingroup$ @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. $\endgroup$
    – Qfwfq
    May 19, 2013 at 11:33
  • 2
    $\begingroup$ @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. $\endgroup$ May 19, 2013 at 16:12
  • 3
    $\begingroup$ @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. $\endgroup$ May 19, 2013 at 19:26
  • 4
    $\begingroup$ @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. $\endgroup$ May 19, 2013 at 23:53
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 1. Why is not the usul notion of composition od reltions enough do define "commutativity" of digrams in Rel? $\endgroup$
    – Qfwfq
    Aug 23, 2014 at 15:07
  • $\begingroup$ 2. Could you also give some reference to the literature on this topic (if there is any) $\endgroup$
    – Qfwfq
    Aug 23, 2014 at 15:08
  • $\begingroup$ The diagrams are the morphisms and the big diagram with implications has to be true. I spent a long time trying to prove that for commutativity, until I constructed a counter-example. The notion used is very canonic, essentially the morphisms for directed grafs. And it is transitive. You can also read a little about this on mathoverflow.net/questions/98810/… As far as I know there is nothing published of the kind. $\endgroup$
    – Lehs
    Aug 23, 2014 at 15:34
  • $\begingroup$ @Qfwfq: Sorry, I forgot to mark that the answer was to you. $\endgroup$
    – Lehs
    Aug 23, 2014 at 16:11
  • $\begingroup$ @Qfwfq: See math.stackexchange.com/questions/912396/… about commutative diagrams for relations. $\endgroup$
    – Lehs
    Aug 29, 2014 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.