the semigroup of binary relations
It is known that on the set of all functions we can define the operation of composition and that the resulting structure is a semigroup called the full transformation semigroup of . It is also known that we can generalize this operation to the set of all binary operations by defining the compostion of binary relations. It also results in a semigroup , which is however ill-behaved (as opposed to the full transformation semigroup, which is its subsemigroup). I will list some problems (some of which the full transformation semigroup shares).
1. The composition of relations is not commutative.
2. is not regular. The regular elements don't have a short characterization.
3. The idempotents of (we denote the set of all of them by seem difficult to characterize. I don't know their characterizations, but I know some exist. Unfortunately, I don't have access to the papers. But I have made some naive attempts at characterizing the idempotents and this is what I've come up with.
4. We can define a dual operation, which results in an isomorphic semigroup with negation being the isomorphism. However, (seemingly -- I haven't proven this) only in the case of are those operations mutually distributive.
a) Every idempotent must be a transitive relation.
be the set all binary relations on X that are pre-orders on some subset of
(that is if
is outside that subset, it is in the relation with nothing). Let
be the set of all partial transformations of
. Then if
is transitive, then
is an idempotent. (In the case of partial transformations, being transitive is equivalent to being a projection.)
c) This is not enough to characterize
5. The composition doesn't work well enough on pre-orders and equivalences. The compostion of two pre-orders is a preorder iff the composition is commutative. The same is true for equivalences. In particular, we know that every preorder is a partial order on some equivalence classes. Unfortunately the composition of the preorder and the equivalence gives the partial order iff the coposition is commutative.
After this long introduction, my question is: is there a way to generalize the composition of functions to all binary relations in a better behaved way? (And why not? :-))