Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In set theory, I learned that a binary relation is simply a subset of a Cartesian product. Moving on to category theory, it seems that this definition is not enough. Just as a function is no longer its graph, but say an ordered triple of a domain set, a codomain set, and a single-valued subset of their product, it is also useful to have a binary relation be an ordered triple of a domain set, a codomain set, and a subset of their product (e.g. when you are trying to define projections from the graph of the relation to the domain and codomain sets). But whereas there is a well accepted notation $f : X \to Y$ for the former stating that "$f$ is a function with domain $X$ and codomain $Y$", I haven't found any notation of this sort for binary relations. In fact, binary relations do not seem to get any special attention or treatment in standard textbooks, like Mac Lane. So my question is:

(1) Is there a standard notation for stating that "$R$ is a binary relation between $X$ and $Y$? (A reference would be good here, even if the notation is not "standard" or "universally accepted".)

(2) If not, is there a reason for this lack of interest in it?

share|improve this question
    
Maybe you are looking for spans? en.wikipedia.org/wiki/Span_%28category_theory%29 –  Mikola Jul 31 '10 at 6:33
    
Just to be clear: are you looking for a notion of binary relation between two objects in the same category (i.e., a sort of "multiple valued morphism") or between two different categories (i.e., a sort of "multiple valued functor")? –  Pete L. Clark Jul 31 '10 at 6:47
1  
The tag "category theory" is wrong. And, why should there be an extra notation for $R \subseteq X \times Y$? –  Martin Brandenburg Jul 31 '10 at 6:56
2  
What is wrong with $R \hookrightarrow X \times Y$? –  Andrej Bauer Jul 31 '10 at 7:37

3 Answers 3

In categorical literature, the notation $f: X \rightarrow Y$ only means "$f$ is a function from $X$ to $Y$" in the case where the category you are working in is Set, that is the category of sets and functions. In the category of sets and relations, the same notation means $f$ is a relation from $X$ to $Y$. To answer (perhaps more verbosely) you question about interest, there is actually loads of interest in binary relations. With a bit of digging, one sees that they crop up in various guises all over category theory.


AS A (MONOIDAL) CATEGORY

For starters, the category Rel of sets and binary relations is a perfectly good category, and its properties are well understood. Perhaps the reason Rel isn't well covered in the CT classics is because it is primarily of interest as a monoidal category. These are categories that have a notion of "product" that is much weaker than the usual, in that they don't satisfy the usual universal properties, but still form an associative, unital operation one can apply to objects and arrows. While this isn't too far out of the categorical mainstream, you may not necessarily meet them in an introductory course on category theory.

Axiomatically, the category of relations is much more like the category of vector spaces. To see this intuitively, picture a relation from $A$ to $B$ as a matrix $M$ whose columns are indexed by the elements of $A$ and whose rows are indexed by the elements of $B$. Then, let $M_{a,b} = 1$ if $a M b$ and $M_{a,b} = 0$ otherwise. Relational composition is just matrix multiplication, replacing $+$ with OR and $*$ with AND. From this point of view, its easy to see that the cartesian product of relations is is much more closely resembles the tensor product of linear maps than it does the cartesian product of functions.

The category FRel of finite sets and relations (as well as FHilb, the category of finite dimensional Hilbert spaces, and many more) forms a dagger-compact closed category. If you become familiar with this definition and associated literate, it sums up a good chunk of what categories like FRel are like and what they are good for. There are lots of ways to get stuck in to this. These categories are presented in a quite accessible, physics-oriented format in Bob Coecke's paper: "Introducing categories to the practicing physicist". You can get it here:

http://arxiv.org/abs/0808.1032

And Pete Selinger introduces the whole zoo of such categories in "A survey of graphical languages for monoidal categories".

http://www.mscs.dal.ca/~selinger/papers/graphical.pdf


AS SPANS

As @Mikola already mentioned, Spans (which are a generalisation of relations) are often used in the place of binary relations in arbitrary categories. A span is just a pair of arrows $f: K \rightarrow X$, $g : K \rightarrow Y$ from a common domain $K$. In categories with products the connection to relations is especially easy to see. Because of the universal property of products, such a pair of arrows determines a unique third arrow $h : K \rightarrow A \times B$. In the case that $h$ is monic, this is just the same as a subset of $A \times B$, i.e. relations as you normally think of them (c.f. @Andrej).

Spans are a beautiful and elegant way to deal with maps that are "relation-like" in suitably rich categories. In fact, any category with pullbacks has a natural notion of a "category of spans of C", whose objects are objects of C, whose arrows are spans (i.e. generalised relations), and where composition of spans is by a pullback-based construction that is much like how one composes relations.

John Baez has some interesting papers about taking spans of groupoids rather than just spans of sets. In line with the intuition that relations are a bit like matrices over the booleans, he treats spans of groupoids as things that are a bit like matrices over the positive real numbers. The place to start on this is:

http://math.ucr.edu/home/baez/groupoidification/


AS PROFUNCTORS

Another way you can think of a binary relation between sets is as a function $\chi_R$ out of a cartesian product $A \times B$ of sets onto the two element set {$0, 1$}. Then let $a R b$ iff $\chi_R(a,b) = 1$. Such a function can be used to define any relation, and is called the characteristic function of the relation $R$.

We can generalise this in quite a natural way from sets and functions to categories and functors. However, in the category Cat of categories and functors, it turns out the most natural thing to send "characteristic" functors to is the category of Sets. A functor $F : C^{op} \times D \rightarrow Set$ is called a profunctor from the category $C$ to the category $D$. I won't spell out to many details here (for instance, the category $C$ is "op-ed" for a good reason), but suffice it to say that such a map behaves very analogously to a binary relation and comes with natural notions of composition, etc.

These become a very powerful tool when working with internal and higher categories, because certain structures you can put on profunctors let you define the notion of a category inside another category. This is a good example of a structure that is quite deep (and that people are only beginning to fully appreciate!) that essentially generalises the basic notion of a binary relation. When you have built up sufficient courage, the canonical reference for profunctors is Bénabou's "Distributors at Work." For the applications I described, they are detailed in papers by Steve Lack and Paul-Andre Mellies, and probably many others.

share|improve this answer

Sometimes people write $R\colon X$⇸$Y$ or $R\colon X$↬$Y$. The former is frequently used for morphisms in a category (like the category Rel of sets and relations) which are "like relations, bimodules, or profunctors" rather than like functions, homomorphisms or functors. The latter is used in the chapter on allegories in Sketches of an Elephant; I don't know if it's more widely used.

share|improve this answer

As Mike Shulman says, an arrow with a stroke through it (either orthogonally or obliquely) is a common notation for relations. However, I don't see any logic in this choice of symbol: it ought to reflect the symmetry of the situation. I use an arrow with two half arrowheads on it. I am not aware of any TeX symbol font that contains this, but it can be drawn using the following macro:

\def\relto{\mathrel{\leftharpoondown\mkern-18mu\rightharpoonup}}

The following textbook is obligatory reading for categories of relations:

Categories, Allegories by Peter Freyd and André Scedrov, North-Holland Mathematical Library, volume 39, 1990, ISBN 0-444-70368-3 (hardback) and 0-444-70367-5 (paperback).

I forget what symbol they use; my copy of the book is still packed away in a box after I moved from London to Birmingham.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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