It looks like you're new here. If you want to get involved, click one of these buttons!
Monoids.
A monoid \((M,∗,e) \) is
a set \(M \);
a function \(∗:M×M \to M \); and
an element \(e \in M \) called the identity;
subject to two laws:
Unit: the equations \(e∗m=m \) and \(m∗e=m \) hold for any \(m \in M \).
Associative: the equation \((m1∗m2)∗m3=m1∗(m2∗m3) \) holds for any \(m1,m2,m3 \in M \).
--
(a) Show that \((\mathbb{N},+,0) \) forms a monoid.
(b) A string in 0 and 1 is a (possibly) empty sequence of 0s and 1s; examples include 0, 11, 0110, 0101110 and so on. We write the empty string []. Let \(List_{0,1} \) be the set of strings in 0 and 1. Given two strings \(a \) and \(b \), we may concatenate them to form a new string \(ab \). Show that \(List_{0,1} \), together with concatenation and the empty string [], form a monoid.
(c) Explain why (prove that) every monoid can be viewed as a category with a single object.
Comments
No takers?
No takers?a:
Unit holds because \(0 + m = m \) and \(m + 0 = m \),
associativity holds because \((m_1 + m_2) + m_3 = m_1 + (m_2 + m_3) \)
b:
Unit holds because \([] ++ m = m \) and \( m ++ [] = m \)
associativity holds because \((m_1 ++ m_2) ++ m_3 = m_1 ++ (m_2 ++ m_3) \)
c:
A monoid can be viewed as a category with a single object (call it obj)
with the set of morphisms C(obj, obj) = M
the function * gives us the composition rule
and e in M gives us the identity morphism.
The Unit and associative laws of the Moniod correspond to the unit and associative laws of the category.
a: Unit holds because \\(0 + m = m \\) and \\(m + 0 = m \\), associativity holds because \\((m_1 + m_2) + m_3 = m_1 + (m_2 + m_3) \\) b: Unit holds because \\([] ++ m = m \\) and \\( m ++ [] = m \\) associativity holds because \\((m_1 ++ m_2) ++ m_3 = m_1 ++ (m_2 ++ m_3) \\) c: A monoid can be viewed as a category with a single object (call it obj) with the set of morphisms C(obj, obj) = M the function * gives us the composition rule and e in M gives us the identity morphism. The Unit and associative laws of the Moniod correspond to the unit and associative laws of the category.