Set of All Relations is a Monoid

From ProofWiki
Jump to: navigation, search

Theorem

The set of all relations $\Bbb E = \left\{{\mathcal R: \mathcal R \subseteq S \times S}\right\}$ 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 $\mathcal R$ is invertible, its inverse is $\mathcal R^{-1}$.


Proof

Closure

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 \mathcal R_1, \mathcal R_2 \subseteq S \times S: \mathcal R_1 \circ \mathcal R_2 \subseteq S \times S$

Therefore composition of relations on a set is closed.

$\Box$


Associativity

Composition of Relations is Associative.

$\Box$


Identity

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

$\forall \mathcal R \subseteq S \times S: \mathcal R \circ I_S = \mathcal R = I_S \circ \mathcal R$

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

$\Box$


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


Inverses

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

  • $\mathcal R^{-1} \circ \mathcal R = I_S$ and
  • $\mathcal R \circ \mathcal R^{-1} = I_S$.

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

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Set_of_All_Relations_is_a_Monoid&oldid=108162"