Category Theory for Programmers Chapter 13: Free Monoids

Challenges

  1. Show that an isomorphism between monoids that preserves multiplication must automatically preserve unit.

    Let $A$ and $B$ be monoids and $A \cong B$. Then there exists $f:A \to B$ and $f^{-1}:B \to A$ such that $f \circ f^{-1} = \mathrm{Id}_B$ and $f^{-1} \circ f = \mathrm{Id}_A$. And because $f$ and $f^{-1}$ preserve multiplication, we have also that $f(a a’) = f(a) f(a’)$ for all $a, a’ \in A$ and $f^{-1}(b b’) = f^{-1}(b) f^{-1}(b’)$ for all $b,b’ \in B$. Also, because $A$ and $B$ are monoids, there exists $e_A \in A$ such that $a e_A = e_A a = a$ for all $a \in A$ and similarly $e_B \in B$ such that $b e_B = e_B b = b$ for all $b \in B$.

    Let $f(a e_A) = f(a) f(e_A) = f(a)$ for all $a \in A$, then $f(e_A)$ is a candidate for identity in $B$ because for all $b \in B$, we have \(b f(e_A) = f(f^{-1}(b f(e_A)))\) \(= f(f^{-1}(b) f^{-1}(f(e_A)))\) \(= f(f^{-1}(b) e_A)\) \(= f(f^{-1}(b))\) \(= b.\)

    Then we have that $e_B f(e_A) = e_B$ by above and $e_B f(e_A) = f(e_A)$ by definition of $e_B$ and so we have that \(e_B f(e_A) = e_B = f(e_A).\)

    Similarly, we can show \(e_A f^{-1}(e_B) = e_A = f^{-1}(e_B).\) \(\blacksquare\)

  2. Consider homomorphism from ([Integer], [], ++) to $(\mathbb{Z}, 1, \times)$.

    1. What is image of []?

      Since [] is the identity in [Integer], the homomorphism preserves structure and so would be mapped to the identity, $1$.

    2. Assume all singleton lists are mapped to their integers, [x] $\mapsto x$. What’s the image of [1, 2, 3, 4]?

      Because we don’t need to worry about associativity (property of monoids), we can say that [1, 2, 3, 4] = [1] ++ [2] ++ [3] ++ [4]. Then using the assumption above, this maps to $1 \times 2 \times 3 \times 4 = 24$.

    3. How many lists map to $12$?

      The prime factors of $12$ are $2 \times 2 \times 3$ and so we can enumerate all groups of integers that have product 12:

      • $2, 2, 3$
      • $4, 3$
      • $2, 6$
      • $12$
      • $-4, -3$
      • $-2, -6$
      • $-2, -2, 3$
      • $-2, 2, -3$

      Including identities, we could have infinitely many.

  3. What is the free monoid generated by a one-element set?

    $(\mathbb{N}, 0, +)$ where the isomorphism given by the length of the list.