MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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|cite|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|cite|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|cite|improve this answer

I'm a few years late to the party, but thought I'd contribute a notation I haven't seen.

Within the computer science community, in particular the formal methods groups, one sees a double-head arrow for the type of relations. That is,

$$ (A \leftrightarrow B) := \text{the type of relations from $A$ to $B$} $$

I first saw this notation in Using Z; I do not know where it originates from, however. Now how does this relate to the categorical setting? Well, just as categories-generalise-functions we have allegories-generalise-relations and I've seen this double-arrow notation used for morphisms in an allegory ---perhaps as a reminder that they behave like relations.

Also, at one point, one of the commenters above asked: why have an extra notation for $R \subseteq X \times Y$? My reply is that notations are for context or perspective.

For example, when I was in school, they taught me about these things called matrices as nifty ways to solve simultaneous equations, then they taught me about these abstract structures called finite dimensional vector spaces, then it was remarked to me that these are essentially the same, in that the associated categories are equivalent. So they taught me seemingly different things but were really one in the same. Indeed a linear transformation and a matrix look nothing alike at first glance.

Another example is the struggle for composition-notation in category theory. Some prefer diagrammatic or forwards composition ⨾, while others prefer to stick to tradition and use backwards composition ∘. They serve the same purpose, but sometimes you'd like to read your formulae with the word then and so use ⨾, other times you want to use the word after and so use ∘.

Going back to where we started, when I think of a relation I think of a boolean-valued function and not of a collection of pairs. Even though they are mathematically equivalent, the perspective I want to communicate depends on the words I choose and likewise the notation employed.

share|cite|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.