#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Question 1.5 - Monoids

edited January 2020

Monoids.

A monoid $$(M,∗,e)$$ is

1. a set $$M$$;

2. a function $$∗:M×M \to M$$; and

3. 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.

• Options
1.

No takers?

Comment Source:No takers?
• Options
2.

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.

Comment Source: 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.