Set of all Self-Maps under Composition forms Semigroup

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $S^S$ be the set of all mappings from $S$ to itself.

Let the operation $\circ$ represent composition of mappings.


Then the algebraic structure $\struct {S^S, \circ}$ is a semigroup.


Proof

Let $f, g \in S^S$.

As the domain of $g$ and codomain of $f$ are the same, the composition $f \circ g$ is defined.

By the definition of composition, $f \circ g$ is a mapping from the domain of $g$ to the codomain of $f$.

Thus $f \circ g: S \to S$, so $f \circ g \in S^S$.

Since this holds for all $f, g \in S^S$, $\struct {S^S, \circ}$ is closed.

By Composition of Mappings is Associative, $\circ$ is associative.

Since $\struct {S^S, \circ}$ is closed and $\circ$ is associative:

$\struct {S^S, \circ}$ is a semigroup.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Set_of_all_Self-Maps_under_Composition_forms_Semigroup&oldid=595533"