Set of All Relations is a Monoid

From ProofWiki
Jump to navigation Jump to search


The set of all relations $\Bbb E = \set {\RR: \RR \subseteq S \times S}$ on a set $S$ forms a monoid in which the operation is composition of relations.

The only invertible elements of $\Bbb E$ are permutations.

If $\RR$ is invertible, its inverse is $\RR^{-1}$.



A relation followed by another relation is another relation, from the definition of composition of relations.

As the domain and codomain of two relations are the same, then:

$\forall \RR_1, \RR_2 \subseteq S \times S: \RR_1 \circ \RR_2 \subseteq S \times S$

Therefore composition of relations on a set is closed.



Composition of Relations is Associative.



From Identity Mapping is Left Identity and Identity Mapping is Right Identity we have that:

$\forall \RR \subseteq S \times S: \RR \circ I_S = \RR = I_S \circ \RR$

Hence the identity mapping is the identity element of this set of relations.


It is closed and associative, so it is a semigroup. It has an identity element, so it is a monoid.


Now if $\RR \in \Bbb E$ were to be invertible, it would need to satisfy:

$\RR^{-1} \circ \RR = I_S$


$\RR \circ \RR^{-1} = I_S$

From Inverse Relation is Left and Right Inverse iff Bijection this can only happen if $\RR$ is a bijection on $S$, that is, a permutation, and its inverse is then $\RR^{-1}$.