Salutare! Pentru că tema întâlnirii de diseară sunt monoizii am pregătit câteva puzzle-uri despre acest subiect; iar dacă vi se par interesante le putem discuta când ne vedem.
Definition (monoid). A monoid consists of:
- a set
- a binary operation
· : M × M → M
- an element
e ∈ M
- the binary operation is associative, that is,
x · (y · z) = (x · y) · z, ∀ x, y, z ∈ M
- the element
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
h(x · y) = h(x) * h(y)for all
x, y ∈ M
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 on
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
i(1) = efor some
1 ∈ N
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
(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
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?