Exercise 2.4

We check each monoid law in turn:

Closure. If we have two functions \(f, g \in \mathrm{Maps}(X, M)\), then their star product is itself a function from \(X\) to \(M\), i.e. \(f \star g \in \mathrm{Maps}(X, M)\). So closure is satisfied.

Associativity. Let \(f, g, h \in \mathrm{Maps}(X, M)\). Then:

\[\begin{split}(f \star g) \star h &= (x \mapsto f(x) * g(x)) \star h \\ &= x \mapsto (f(x) * g(x)) * h(x) \\ &= x \mapsto f(x) * (g(x) * h(x)) \\ &= f \star (x \mapsto g(x) * h(x)) \\ &= f \star (g \star h)\end{split}\]

This gets a little bit messy, but the key observation is that associativity of the star product follows from associativity of the underlying monoid \((M, *)\). So associativity is satisfied.

Identity. Let \(\iota : X \rightarrow M\) be defined by \(\iota(x) = e_M\), where \(e_M\) denotes the identity element in \(M\). Then, for any \(f \in \mathrm{Maps}(X, M)\), we have that:

\[ \begin{align}\begin{aligned}f \star \iota = x \mapsto f(x) * e_M = x \mapsto f(x) = f\\\iota \star f = x \mapsto e_M * f(x) = x \mapsto f(x) = f\end{aligned}\end{align} \]

That is, \(\iota\) is the identity element of \((\mathrm{Maps}(X, M), \star)\). So identity is satisifed, and this completes the proof.