Monoids – Bucharest FP #31

monoids.md

Definition (monoid). A monoid consists of:

1. a set M
2. a binary operation · : M × M → M
3. an element e ∈ M

such that

1. the binary operation is associative, that is, x · (y · z) = (x · y) · z, ∀ x, y, z ∈ M
2. the element e is identity: x · e = x = e · x, ∀ x ∈ M.

Definition (monoid homomorphism). A homomorphism between two monoids (M, ·, e) and (N, *, 1) is a function h : M → N such that

1. h(x · y) = h(x) * h(y) for all x, y ∈ M
2. h(e) = 1

Puzzle 1. Why does the definition of homomorphism require the second condition? If we let either y = e or x = e in the first condition, we see that h(e) behaves like the identity:

h(x) = h(x · e) = h(x) * h(e)                              
h(y) = h(e · y) = h(e) * h(y)

Construction (monoid of endomorphisms). For every set M we may construct the monoid of endomorphisms (M → M, ○, id), where ○ denotes function composition and id is the identity function.

Puzzle 2. Show that the monoid of endomorphisms is indeed a monoid.

Definition (sub-monoid). A set N is a sub-monoid of a monoid (M, ·, e) if there exists an injection i : N → M such that

1. i(1) = e for some 1 ∈ N
2. i(x * y) = i(x) · i(y) for some * : N × N → N.

Puzzle 3. Show that if N is a sub-monoid then the existence of i makes (N, *, 1) a monoid and i a monoid homomorphism.

Theorem (Cayley's theorem for monoids). Every monoid (M, ·, e) is a sub-monoid of the monoid of endo-morphisms on M.

Puzzle 4. Prove Cayley's theorem for monoids. Hint: Come up with a function rep :: Monoid m => m -> (m -> m) and show that (i) it is a homomorphism and (ii) it is an injection.

Puzzle 5. Apply Cayles's theorem for lists. This representation gives the difference (or Hughes) lists. Why is this representation more efficient for appending lists than the standard representation?