3

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:

  1. http://reperiendi.wordpress.com/2007/09/12/monoids/
Community
  • 1
Andriy Drozdyuk
  • 889
  • 4
    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... – Andriy Drozdyuk Dec 19 '11 at 19:23
  • 3
    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! – Andriy Drozdyuk Dec 19 '11 at 19:56

2 Answers2

8

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.

Paolo Capriotti
  • 476
  • Cool, so to show that something is a monoid we just have to verify associativity (given identity and the definition of the binary operator)? – Andriy Drozdyuk 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
  • 1
    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 02:58
  • I came here wondering why we can regard two functions as equal when the equality of functions is in general undecidable. I see now that as you say, it is sufficient to check that they have the same value on every possible argument. But I am left wondering what the conditions are that lead this special case to be decidable. Perhaps this is something I should ask as a new question... – senderle Feb 26 '21 at 08:44
1

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.

yoyo
  • 9,943
  • So... these functions (your f and g) are not a monoid? I thought all functions were in a monoid... – Andriy Drozdyuk Dec 19 '11 at 19:36
  • 4
    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