Talk:Composition of relations

From Wikipedia, the free encyclopedia

It is odd to call the final section 'Further Reading': there are no references there!

It says 'Composition of relations can be seen as a special case of the composition of morphisms in the category of binary relations.' But composition of relations is composition of morphisms in the category of relations, surely.

And I don't think that the sentence 'composition of morphisms in category theory is coined on composition of relations' is true. Do you have a reference for this?

I propose to delete this final section. Any objections? Sam Staton 14:15, 15 January 2007 (UTC)

No objections, so I deleted this section. We can discuss here if that is a problem. Sam Staton 12:00, 1 February 2007 (UTC)

[edit] Arrow notation

Currently the article usese arrow notation R\colon A\to B for binary relations, but I believe it is standard to reserve this for functions from A to B. There is no source for this notation, and it is not mentioned under binary relation. However, in the context of composition it might be best to replace the arrows with a similarly suggestive notation, e.g. f\colon A\multimap B. Any pointers to such a notation in the literature? --Hans Adler (talk) 23:25, 5 January 2008 (UTC)

Isn't this multimap the notation for arrows in a Kleisli category, so that f itself would have type f : A → MB in the underlying category, where M is the functor of the monad? The notation might be confusing for people who know the other meaning. Since typed relations are arrows in the concrete category Rel of relations, I see nothing wrong by itself with using the arrow notation, as long as it is clear that the entity being typed is a relation. An advantage is that this gives a natural way to fix the embedding of a function f : A → B in the world of relations, where a choice must be made between two dual isomorphic views. Alternatively, I have seen the notation R : A ~ B used, but this is not standard.  --Lambiam 09:29, 6 January 2008 (UTC)
I only used \multimap for illustrative purposes, and I would be much more happy with ~. (I didn't think of this.)
I also didn't think of the category Rel (or any category theory at all) in the context of this article. Now that you have suggested it, I have brought the article in line with the binary relation article and added a paragraph on Rel. --Hans Adler (talk) 23:42, 6 January 2008 (UTC)
Note that Rel is the Kleisli category of the powerset monad. I'm not sure how standard the lollypop is for Kleisli categories, though, so I'm not arguing for its use. For relations, Paul Taylor, in his book, uses a symbol like \rightleftharpoons except the two arrows are one. He says (Notation 1.3.4) that he invented the symbol for this purpose. Peter Johnstone, in the Elephant, uses \looparrowright. Others use a right arrow with a vertical line through it. Since there is no universal standard, it seems reasonable to stick with \rightarrow here, and include the explanation that Hans provided. I am not very keen on the tilde because it is so different from the usual arrow notation for morphisms. Sam Staton (talk) 10:20, 7 January 2008 (UTC)