# How does a set of functions form a monoid?

While I now understand what monoids are I am still not sure how a set of functions, under composition defines a monoid.

The main difficulty I am having is understanding how you can define composition. I mean for integers under $+$ it's easy. Define our binary operator to be plus, so:

$x \cdot y = x + y$

and we know what $x+y$ means...

But for functions:

$f \cdot g = f(g)$ <---????

Clearly we can't write $f(g)$ because it then makes no sense to write: $f(g)(x)$

I'm probably completely wrong about something...

References:

-
The correct way to write composition is $f \circ g$, defined as $(f \circ g)(x) = f(g(x))$. –  Srivatsan Dec 19 '11 at 19:20
Yeah, but where does $x$ come from? I mean when we do addition, there is no extra $x$ anywhere... –  drozzy Dec 19 '11 at 19:23
Well, here it is important to dissociate the function from its argument -- we view the function as a separate entity by itself (e.g., the square root function, the logarithm function, and the "addition by $1$" function). But to make sense of what the function "does", the only way is to plug in all possible values for the input and note the output in every case. (This is why I introduced a dummy variable $x$.) Perhaps someone will explain this idea better in an answer. Indeed, since the OP seems to be a programmer, it might be especially nice to motivate it using computer programming. –  Srivatsan Dec 19 '11 at 19:40
I think i was failing to separate the two notions: the function and the what the function does... I think I get it, thanks! –  drozzy Dec 19 '11 at 19:56

Given two functions $f, g : X \rightarrow X$, their composition $f \circ g$ is a new function $X \rightarrow X$. When $f \circ g$ is given an argument $x \in X$, it first applies $g$ to produce an element $g(x)$, and then applies $f$ to that. The result is $f(g(x))$, and this element is defined to be the value of $f \circ g$ in $x$.

Summing up, we get what Srivatsan wrote in a comment:

$$(f \circ g)(x) = f(g(x)).$$

Since we defined an operation that takes two functions $f$ and $g$ and produces a new function $f \circ g$, it makes sense to check if the operation makes the set $X^X$ of functions $X \rightarrow X$ into a monoid.

To do so, we need to prove that composition is associative, i.e.:

$$(f \circ g) \circ h = f \circ (g \circ h)$$

for any choice of $f, g, h$, and also that there exists a special function $i : X \rightarrow X$, such that, for all $f$:

$$f \circ i = i \circ f = f.$$

All of this is extremely easy to verify, just keep in mind that to check if two functions are equal is it sufficient to check that they have the same value on every possible argument.

-
Cool, so to show that something is a monoid we just have to verify associativity (given identity and the definition of the binary operator)? –  drozzy Dec 19 '11 at 19:37
Well.. yes, that's the definition of monoid: associative binary operation with an identity element. –  Paolo Capriotti Dec 19 '11 at 19:38
You have to verify that your set of functions is closed under composition. If your set of functions has only $f(x)=x$ and $g(x)=x+1$, then $g\circ g$ is not in your set. –  Thomas Andrews Dec 19 '11 at 19:59
So the type of functions f and g are both a -> a? –  Kevin Meredith Oct 29 '14 at 2:58

if $f:X\to Y, g:Y\to Z$ are two functions, then the composition $g\circ f:X\to Z$ is defined by first doing $f$, then doing $g$, ie $(g\circ f)(x)=g(f(x))$. for example, if $f:\mathbb{R}\to\mathbb{R}$ is given by $f(x)=x+1$ and $g:\mathbb{R}\to\mathbb{R}$ is given by $g(x)=x^2$ then $(g\circ f)(x)=(x+1)^2$ (and $(f\circ g)(x)=x^2+1$ so that that composition is not commutative when defined). one has the identity function from a set to itself, and composition is associative when defined. so the set of all functions from a set to itself is a monoid.

-
So... these functions (your f and g) are not a monoid? I thought all functions were in a monoid... –  drozzy Dec 19 '11 at 19:36
The set of all functions that map $X\to X$ is a monoid, but it is not true that any subset of the set of all such functions is a monoid. You have to prove that the identity is in that set and that the set is closed under composition. –  Thomas Andrews Dec 19 '11 at 20:03