On Thu, 20 Aug 2009, Michael Barr wrote:
On Thu, 20 Aug 2009, soloviev@irit.fr wrote:
To the list:
I am actually travelling (in Russia) and I need more or less urgently a reference concerning pullbacks and pushouts in the category of sets and relations - do they always exist etc - I would not adress it to the list if it would be not urgent and I would not have some difficulty with search from here -
Best to all -
Sergei Soloviev
You should check this, but it seems right. Rel is self dual and each object is too. So limits are colimits (of the dual diagram). Rel has arbitrary sums and products--they are disjoint unions. The empty set is initial and terminal. So to have pullbacks you need equalizers. So let A and B be sets and R,S \inc A x B. Let A_0 be the subset of A consisting of all a such that (a,b) \in R iff (a,b) \in S. Then it seems to me that the inclusion function of A_0 into A is the equalizer of R and S.
Sadly, that doesn't work. Let A = {0,1}, B = {0,1}, and let R and S be respectively the identity relation and the relation which relates each member of A to both members of B. Then Michael's proposed equalizer is empty, but the relation from C = {0} to A which relates 0 to both members of A has equal composites with R and S. (The pair (R,S) does have an equalizer in Rel, namely the relation C -+-> A just described, but with a little more ingenuity you can find parallel pairs in Rel having no equalizer.) Peter Johnstone [For admin and other information see: http://www.mta.ca/~cat-dist/ ]