Why is Set, and not Rel, so ubiquitous in mathematics? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T02:22:00Z http://mathoverflow.net/feeds/question/121031 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics Why is Set, and not Rel, so ubiquitous in mathematics? Qfwfq 2013-02-07T00:51:04Z 2013-05-20T06:23:38Z <p>The concept of relation in the history of mathematics, either consciously or not, has always been important: think of order relations or equivalence relations.</p> <p>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)$.</p> <blockquote> <p>1) In which instances in modern mathematics are relations used as important generalizations of functions? One example that comes to mind is <em><a href="http://en.wikipedia.org/wiki/Motive_%28algebraic_geometry%29#First_step%3A_category_of_.28degree_0.29_correspondences.2C_Corr.28k.29" rel="nofollow">correspondences</a></em> in the sense of algebraic geometry.</p> </blockquote> <hr> <p>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$ &amp; $yRt)$ $\Rightarrow$ $(x*y)R(z*t)$, where $*$ is the group multiplication.</p> <blockquote> <p>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?</p> </blockquote> <hr> <p>Let <strong>Set</strong> be the usual category of sets, and <strong>Rel</strong> be the category of sets-with-relations-as-morphisms. </p> <p>There is the faithful functor <strong>Set</strong> $\to$ <strong>Rel</strong> that simply keeps sets intact and sends a function to its graph. And there is also a faithful functor <strong>Rel</strong> $\to$ <strong>Set</strong> mapping $X\to 2^X$ and $R\subseteq X\times Y$ to <code>$R_*:2^X\to 2^Y, A\mapsto R_*(A)=\{ y\in Y\; |\; \exists x \in A : (x,y)\in R \}$</code>.</p> <p>Despite the trivial foundational fact that set theoretical functions are <em>defined</em> to be a special kind of relations, it seems that in category theory <strong>Set</strong> has priority on <strong>Rel</strong>. For example the Yoneda's lemma is stated for <strong>Set</strong>; and people talk of simplicial <em>sets</em>, not simplicial relations; and the category <strong>Rel</strong> is just retrieved as "the Kleisli category of the powerset endofunctor on <strong>Set</strong>" (I just learned this from wikipedia) and it doesn't seem to be so ubiquitous as <strong>Set</strong> (but this impression might just depend on my ignorance in category theory).</p> <blockquote> <p>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 <strong>Rel</strong>? </p> </blockquote> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/121034#121034 Answer by Benjamin Steinberg for Why is Set, and not Rel, so ubiquitous in mathematics? Benjamin Steinberg 2013-02-07T01:12:07Z 2013-02-07T01:39:11Z <p>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. </p> <p>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). </p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/121045#121045 Answer by Sönke Hansen for Why is Set, and not Rel, so ubiquitous in mathematics? Sönke Hansen 2013-02-07T08:00:12Z 2013-02-07T08:00:12Z <p>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 <code>$T^*Y\times T^*X$</code>, where <code>$X$</code> and <code>$Y$</code> 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 <code>$f:Y\to X$</code> is an FIO, <code>$f^*$</code>. Here the relation is the conormal bundle of the graph of $f$ (after one of the fiber variables has been multipled by <code>$(-1)$</code>). In case <code>$f$</code> is a diffeomorphism, the associated symplectomorphism <code>$T^*Y\to T^*X$</code> is the canonical relation of <code>$f^*$</code>. The FIOs which correspond to the identity on <code>$T^*X$</code> are precisely the pseudo-differential operators on <code>$X$</code>. 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.</p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/121051#121051 Answer by Dirk for Why is Set, and not Rel, so ubiquitous in mathematics? Dirk 2013-02-07T10:45:34Z 2013-02-07T10:45:34Z <p>I think monotone operators qualify for question 1:</p> <p>A mapping $T:X\to X^*$ from a Banach space to its dual is said to be <em>monotone</em>, if for all $u,v\in X$ it holds that $$\langle Tu - Tv, u-v\rangle\geq 0.$$</p> <p>This generalizes to relations from $X$ to <code>$X^*$</code> (i.e. subsets of <code>$X\times X^*$</code>): <code>$G\subset X\times X^*$</code> 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.$$</p> <p>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 <code>$$\partial f(x) = \{x^*\in X^*\ :\ \forall y:\ f(y)\geq f(x) + \langle x^*,y-x\rangle\}$$</code> can be viewed either a set-valued mapping <code>$\partial f: X \to 2^{X^*}$</code> or as a multifunction <code>$\partial f:X\rightrightarrows X^*$</code> or, by identifying it with its graph <code>$\mathrm{gph}(\partial f) = \{(x^*,x)\in X\times X^*\ : x^*\in\partial f(x)\}$</code>, as subset of <code>$X\times X^*$</code> (indeed, a monotone one).</p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/121053#121053 Answer by Martin Brandenburg for Why is Set, and not Rel, so ubiquitous in mathematics? Martin Brandenburg 2013-02-07T11:16:41Z 2013-02-07T12:51:38Z <p>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 <a href="http://en.wikipedia.org/wiki/Congruence_relation" rel="nofollow">congruence relation</a> 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.</p> <p>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\}$.</p> <p>Note that $\mathsf{Set}$ has many more convenient properties than $\mathsf{Rel}$. For example, Milius' paper <em>On Colimits in Categories of Relations</em> explains that $\mathsf{Rel}$ has not all colimits of $\omega$-chains.</p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/121068#121068 Answer by Mike Shulman for Why is Set, and not Rel, so ubiquitous in mathematics? Mike Shulman 2013-02-07T13:24:51Z 2013-02-07T13:24:51Z <p>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 <a href="http://ncatlab.org/nlab/show/F-category" rel="nofollow">F-category</a>, a <a href="http://ncatlab.org/nlab/show/2-category+equipped+with+proarrows" rel="nofollow">proarrow equipment</a>, or a <a href="http://ncatlab.org/nlab/show/double+category" rel="nofollow">double category</a>. All of these are slightly different ways of talking about a (2-)category that has two classes of morphisms.</p> <p>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 <a href="http://ncatlab.org/nlab/show/regular+category" rel="nofollow">regular category</a> (whose morphisms are "function-like") we can construct a <a href="http://ncatlab.org/nlab/show/allegory" rel="nofollow">unitary tabular allegory</a> (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.</p> <p>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 <a href="http://ncatlab.org/nlab/show/profunctor" rel="nofollow">profunctors</a>). In this case, Prof can be constructed from Cat, but with rather more difficulty than Rel is constructed from Set, while Cat <em>cannot</em> 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.</p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/121077#121077 Answer by Joël for Why is Set, and not Rel, so ubiquitous in mathematics? Joël 2013-02-07T14:44:53Z 2013-02-07T14:44:53Z <p>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). </p> <p>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.</p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/131099#131099 Answer by Ronnie Brown for Why is Set, and not Rel, so ubiquitous in mathematics? Ronnie Brown 2013-05-18T21:17:08Z 2013-05-18T21:27:34Z <p>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$. </p> <p>Actually a web search on "partial functions" gives quite lot of hits, but I am not sure of anything definitive. </p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/131105#131105 Answer by Wlodzimierz Holsztynski for Why is Set, and not Rel, so ubiquitous in mathematics? Wlodzimierz Holsztynski 2013-05-18T23:05:12Z 2013-05-18T23:24:35Z <p><em>Here are my impressions</em>:</p> <p>Are apples more important than fruits? (Usually we tend to compare apples and oranges :-).</p> <p>We have--in the finite case--a numerical metaphor which indicates a vague answer. The number of functions &nbsp; $A\rightarrow B$ &nbsp; is &nbsp; $|B|^{|A|}$, &nbsp; while the number of the relations in &nbsp; $A\times B$ &nbsp; is:</p> <p>$$2^{|A|\times |B|}\ \ =\ \ \left(2^{|B|}\right)^{|A|}$$</p> <p>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.</p> <p>The notion of a (self)function &nbsp; $A\rightarrow A$ &nbsp; can be compared to other <em>oranges</em> like linear orderings (i.e. permutations), partial orderings and equivalence relations in &nbsp; $A$. &nbsp; Let &nbsp; $a:=|A|$. &nbsp; There are &nbsp; $a^a$ &nbsp; of self-functions, &nbsp; $a!$ &nbsp; of linear orderings, over &nbsp; $2^{\lfloor a/2\rfloor\cdot\lceil a/2\rceil}$ &nbsp; of partial orderings but still under &nbsp; $a!\cdot 2^{a\cdot(a-1)/2}$ &nbsp; (hm, a lot), and there are under &nbsp; $a^a$ &nbsp; of equivalence relations.</p> <p>Functions represent longing for determinism (predictability).</p> <p>Isn't the accent on functions relatively modern? Ancient Greeks didn't talk much about functions.</p> <p>PS. The multitude of partial orders combined with the importance of the notion (they happen to be $T_0$-topologies too :-) is puzzling.</p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/131106#131106 Answer by Wlodzimierz Holsztynski for Why is Set, and not Rel, so ubiquitous in mathematics? Wlodzimierz Holsztynski 2013-05-18T23:34:25Z 2013-05-19T21:03:53Z <p>@Ronnie Brown:</p> <p>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).</p> <p>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.</p> <hr> <p>@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 &nbsp; $B\ \ S$ &nbsp; be the unit closed ball in &nbsp; $R^n$ &nbsp; and its boundary (sphere), so that &nbsp; $S\subseteq B\subseteq R^n$. Consider three "identity" functions, the later two induced by the first one:</p> <p>$$I_B:B\rightarrow B$$ $$i_{SB} : S\rightarrow B$$ $$I_S : S\rightarrow S$$</p> <p>so that &nbsp; $i_{SB} = I_B|S$. In the old times (of mostly <strong>local</strong> 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 &nbsp; $I_S$ &nbsp; and &nbsp; $i_{SB}$ &nbsp; different functions is <em>absurdity</em>. However, let &nbsp; $H_n$ &nbsp; 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 &nbsp; $I_S$ &nbsp; and &nbsp; $i_{SB}$ because the induced homomorphisms are dramatically different: &nbsp; $H_n(I_S) = I_{\mathbb Z}$ &nbsp; is a non-zero identity homomorphism on &nbsp; $\mathbb Z$, &nbsp; while &nbsp; $H_n(i_{SB})$ &nbsp; 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).</p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/131193#131193 Answer by Wlodzimierz Holsztynski for Why is Set, and not Rel, so ubiquitous in mathematics? Wlodzimierz Holsztynski 2013-05-20T06:23:38Z 2013-05-20T06:23:38Z <p>It's hard to edit long multi-part Answers. Sorry for writing another one.</p> <p>@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.</p> <p>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</p> <p>$$\frac{x^2-1}{x+1}$$</p> <p>On one hand, as it is now, &nbsp; $-1$ &nbsp; is forbidden (illegal); and on the other hand this function is--hm--equal to &nbsp; $x-1$. I don't know if there is a uniform policy among all these undergraduate Calculus textbooks.</p> <p>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.</p> <p>Nevertheless, even with the Polish set-theoretical tradition, the definition of a <em>function from</em> $X$ <em>to</em> $Y$ would sound something like: a set &nbsp; $f$ &nbsp; of ordered pairs &nbsp; $(x\ y)\in f$ &nbsp; such that:</p> <ul> <li>$$\forall_{x\in X}\exists_{y\in Y}\quad(x\ y)\in f$$</li> <li>$$\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)$$</li> </ul> <p>This is pretty good, and better then <em>a function is a rule</em> 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, &nbsp; graf &nbsp; would be a perfect name, with <strong><em>f</em></strong> indicating a connection with the notion of a function).</p> <p>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.</p> <p><strong>REMARK</strong> &nbsp;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.</p> <p>@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).</p>