How does the Universal Mapping Property encode “no-junk” and “no-noise” in a free monoid?

Question

I am going trough the “Category Theory” book by Steve Awodey.

In the “1.7 Free categories” chapter the author introduces the following algebraic definition of free monoid:

A monoid $M$ is freely generated by a subset $A$ of $M$, if the following conditions hold:

1. (no-junk) Every element $m \in M$ can be written as a product of elements of $A$ $$m = a_1 \cdot_M a_2 \dotsm a_n \,, \quad a_i\in A \,.$$

2. (no-noise) No “nontrivial” relations hold in $M$, that is, if $a_1 \dotsm a_j = a'_1 \dotsm a'_k$, then this is required by the axioms for monoids.

Then the author introduces the notion of Universal Mapping Property (UMP) as a way to encode the conditions above in terms of category theory:

Let $M(A)$ be a monoid on a set $A$. There is a function $i \colon A \rightarrow |M(A)|$ (where $|M(A)|$ is the underlying set of the monoid $M(A)$), and given any monoid $N$ and any function $f \colon A \rightarrow |N|$ (where $|N|$ is the underlying set of the monoid $N$), there is a unique monoid homomorphism $\bar{f} \colon M(A) \rightarrow N$ such that $|\bar{f}| \circ i = f$ where $|\bar{f}| \colon |M(A)| \rightarrow |N|$.

The author then says that

1. the existence part of the UMP captures the vague notion of “no-noise” (because any equation that holds between algebraic combinations of the generators must also hold anywhere they can be mapped to, then thus everywhere);

2. the uniqueness part makes precise the “no-junk” idea (because any extra elements non-combined from the generators would be free to be mapped to different values).

None of the conclusion above seem to be clear to me, could anyone please explain it?

Answer 1

Monoid homomorphism $\bar f$ preserves structure so, in particular, if there are any equalities between products in one monoid $M$, like $a \cdot_M b = c \cdot_M b$, they are automatically transported to the other one, $N$: $\bar f(a) \cdot_N \bar f(b) = \bar f(c) \cdot_N \bar f(b)$. Some equalities, like the unit and associativity laws are satisfied in any monoid. But suppose that there is an additional equality (the "noise"), for instance $2 \cdot 6 = 4 \cdot 3$ in the monoid of natural numbers $(\mathbb{N}, \cdot)$. Such an equality restricts the type of monoids to which $(\mathbb{N}, \cdot)$ can be mapped. They all have to satisfy this additional equality. So the existence of a monoid homomorphism from the free monoid to any monoid with the same generators means that the former has no noise equalities.

Junk is defined as any element that is not generated from the generator set $A$. Let's say, you add $i$ to $\mathbb N$. You can now pick the target monoid to have even more junk, say $j$ and $k$. You can map $i$ to $j$, or you can map $i$ to $k$. Two different mappings that still satisfy the commuting conditions (which you have omitted in your post).

Answer 2

This is actually not only about intuition, there are formal statements behind that here.

For the first conclusion : let $p,q$ be two expressions written in the language of monoids with free variables $\mathbf x_1,...,\mathbf x_n$, and suppose there are distinct $a_1,...,a_n \in A$ such that $p(a_1,...,a_n) = q(a_1,...,a_n)$.

Then given any $n$-tuple $b_1,...,b_n$ in any monoid $N$, you can map $a_i\mapsto b_i$, $A\to |N|$ (and extend it however you want it on the rest of $A$), so if you are guaranteed the existence part of the UMP, you get a monoid morphism $f:M(A)\to N$ that sends $a_i\mapsto b_i$.

In particular a monoid morphism preserves expressions written in the language of monoids, so that $p(b_1,...,b_n) = p(f(a_1),...,f(a_n)) = f(p(a_1,...,a_n)) = f(q(a_1,...,a_n))=q(f(a_1),...,f(a_n)) = q(b_1,...,b_n)$.

So for any tuple $(b_1,...,b_n)$ in any monoid, $p(b_1,...,b_n) =q(b_1,...,b_n)$. This means that this equation $p=q$ is imposed by the monoid axioms (if you see "imposed" as a semantic notion, then there is nothing more to say; if you want a syntactic notion of entailment, then you have to use the completeness theorem to conclude here)

For the second conclusion : It is not quite true that the uniqueness property alone implies the "no-junk" thing. However, if you assume existence, then uniqueness then implies that there is "no junk".

Indeed let $N$ be the submonoid of $M(A)$ consisting of all the things that can be written as (possibly empty) products of elements of $A$. Then there is a map $A\to |N|$ which, by existence, extends to $M(A) \to N$, and sends $a\mapsto a$. Therefore, if you compose this with the inclusion $N\to M(A)$, you get a map $M(A)\to M(A)$ such that $a\mapsto a$. Now we use uniqueness to conclude that this map must be the identity, so that $N\to M(A)$ must be surjective.

But it's an inclusion, in other words $N=M(A)$, so there is "no junk".

To see why uniqueness without existence is not enough to guarantee that there is no junk, you can think of the inclusion $\mathbb{N\to |Z|}$, where you see $\mathbb Z$ as the usual additive monoid.

Then clearly any map $\mathbb Z\to M$ for any monoid $M$ is entirely determined by where it sends $\mathbb N$ (in fact $1$ : it must send it to some invertible element $m$ and then $n$ is sent to $m^n$). Therefore we do have uniqueness, however we don't have existence in general, and there is junk ($-1$ can't be written as a sum of nonnegative integers)

So the intuition for 2. should be that, although uniqueness on its own is not what brings the "no-junk" property, it is the part of the UMP that guarantees it when you also have existence.

Answer 3

I will try to rephrase a bit these properties for you, but it is going to be a bit difficult because these sentence capture already pretty well the ideas behind these properties.

So let me start with the "no-junk", because it is in my opinion the easiest to see. When you have a morphism of monoids $f : M \to N$, the only thing it has to satisfy is that it respects the product $f(mn) = f(m)f(n)$. So now the uniqueness in the UMP says that any two morphisms of monoids $f,g : M(A) \to N$ that coincide on each elements on $A$ have to be equal, or in other words a morphism $f : M(A) \to N$ is completely determined by its values on elements of $A$. Until now this is just rephrasing, but think of it this way : assuming that we know all the values of $f$ on the elements of $A$, what are the other values that are determined by the condition that $f$ is a morphism of monoids. With a bit of playing around (that is up to you to convince yourself), you can see that the values that are determined are the products of the form $a_1,\ldots,a_n$, where $a_i$ are elements of $A$. Saying that these product have to determine entirely $f$ hence means that all elements have to be products of this forms. This is the "no-junk" condition.

Now for the "no-noise" part, you can see it like this : the existence in the UMP stated that to determine $f$ you just have to specify its values on elements on $A$, but you are free to do so in any shape or way you want. Suppose that there is an equation of the form $a_1\ldots a_j = a'_1\ldots a'_k$, then since a morphism has to respect the product, the value of $f$ on $A$ would be constraint by the fact that we need to have $f(a_1)\ldots f(a_j) = f(a'_1)\ldots f(a'_k)$, which would not make your choice completely free. Hence the existence in the UMP implies that there is no such relation, which is exactly the "no-noise" part

EDIT : It turns out that Max replied before me, my reply gives you the intuition, whereas his makes it formal, but they are essentially the same