# BM Category Theory 3 & 4 Monoid, Kleisli Category (Monad), Terminal /Initial Object, Product… Free Monoid

3.1 Monoid M (m, m)

Same meaning in Category as in Set: Only  1 object, Associative, Identity

Thin / Thick Category:

• “Thin” with only 1 arrow between 2 objects;
• “Thick” with many arrows between 2 objects.

Arrow : relation between 2 objects. We don’t care what an arrow actually is (may be total / partial order relations like = or $\leq$, or any relation), just treat arrow abstractly.

Note: Category Theory’s “Abstract Nonsense” is like Buddhism “空即色, 色即空” (Form = Emptiness).

Example of Monoid: String Concatenation: identity = Null string.

Strong Typing: function f calls function g, the type of the output of f must match with the type of the input of g.

Weak Typing:   no need to match type. eg. Monoid.

Category induces a Hom-Set: (Set of “Arrows”, aka Homomorphism 同态, which preserves structure after the “Arrow”)

• C (a, b) : a -> b
• C (a,a) for Monoid : a -> a

Morphism between a, b :
$\boxed{a \to (b, \text {string})}$

In brief, embellish the returned output b with string.

In the example of Kleisli Category, using Monoid (single object) with embellishing string => Monad (covered in later videos).

4.1 Monad (one definition) : Kleisli

Set and Category SET:

• Set has elements and function between sets.
• Category SET has NO element, only arrows (morphisms)

Universal Construction: define relations between Objects.

Set is rich with functions, except 1 case: There is no function from a non-empty set to Void (because a function must have an image in the co-domain, but Void has no element as the Image.)

Terminal Object : all other objects (each with UNIQUE arrow) point to it. [Denoted as () or Unit]

$\boxed { \forall a, \exists f :: a \to ()}$

$\boxed { \forall a, f :: a \to (), g :: a \to () \implies f = g }$ (Uniqueness of arrow)

Note: Terminal Object (T.O.) is the largest object. There is no T.O. in Natural numbers.

Initial Object: reverse of Terminal object. Outgoing arrow from Void.

absurd :: Void -> a

Category “Equality”:

• 2 objects are isomorphic (exists an inverse arrow), but we don’t say they are equal;
• Arrows can be equal by associativity :  $f \circ (g \circ h) = (f \circ g) \circ h$

Terminal Object (Similarly, Initial Object) is unique (up to ONLY ONE Isomorphism).

Assume both Ta and Tb are Terminal Objects. Prove Ta = Tb by showing there is only one isomorphism.

Note1: example of 2 isomorphisms between 2 Objects : (0, 1) and (T, F) =>

• 1st isomorphism : (1 ~ T), (0 ~ F)
• 2nd isomorphism: (1 ~ F), (0 ~ T)

Note2: There are outgoing arrows from T.O. => generalising.

4.2 Products

$C^{op}$ : also a Category with all arrows in C reversed.

Products (Cartesian) of 2 objects (a,b): by Universal Construction.

p and q are (good) projections of c.
p’ and q’ are (another) projections of c’.

c is the product of (a, b) if
there is a UNIQUE  isomorphism m,
$\boxed {m :: c' \to c }$
$\boxed {p' = p \circ m}$
$\boxed{q' = q \circ m}$

II 3.2 Free Monoid

Monoid : with a Set of 2 generators (a, b)

• Identity: e*a = a*e = a;
• Associativity

Free Monoid = {e, a, b, ab, ba, aab, abb, ….}, notice it is generated by the set {a, b} and thus not a Monoid (noted as Mon).

We can create a Functor U (aka  Forgetting function) between Monoid and its underlying Set:

$\boxed { U :: Mon \to Set }$