3
$\begingroup$

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 \cdot_M...\cdot_M a_n, \space a_i\in A$$

  2. (no-noise) No "nontrivial" relations hold in $M$, that is, if $a_1...a_j = a_1^`...a_k^`$, then this is required by the axioms for monoids

Then the autor introduces the notion of $Universal \space Mapping \space Property \space (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: A \rightarrow|M(A)|$ ($|M(A)|$ - is the underlying set of the $M$ monoid), and given any monoid $N$ and any funciton $f: A \rightarrow |N|$ ($|N|$ - is the underlying set of the $N$ monoid), there is a $unique$ monoid homomorphism $\bar f: M(A) \rightarrow N$ such that $|\bar f| \circ i = f$ where $|\bar f| : |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?

$\endgroup$
  • 2
    $\begingroup$ I would probably just ignore it, if you’re able to understand the universal mapping property itself. I’m not sure how good an intuitive explanation these properties are. $\endgroup$ – Kevin Carlson Jan 23 at 14:40
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ About junk: there is the commuting triangle in $Sets$: $|\bar f| \circ i = f, i: A \rightarrow |M(A)|, |\bar f|: |M(A)| \rightarrow |N|, f: A \rightarrow |N|$. If there is junk in $|M(A)|$ I can define multiple $|\bar f|$ (by mapping the junk to different elements in $|N|$) that hold the commuting condition, and hence produce multiple monoid homomorphisms $f: M(A) \rightarrow N$, is that the idea? $\endgroup$ – neshkeev Jan 25 at 14:48
  • $\begingroup$ That's the general idea $\endgroup$ – Bartosz Milewski Jan 26 at 15:48
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "No junk" makes good sense, but I think "no noise" isn't that convincing a way to communicate "no unnecessary relations." Of course, the precise explanation you gave of why there are no unnecessary relations is a great thing to understand. $\endgroup$ – Kevin Carlson Jan 23 at 16:41
  • $\begingroup$ @KevinCarlson : I agree that the specific expression "no noise" isn't super convincing (you'll notice that I didn't even repeat it, contrary to "no junk"). I usually say "no relations" (with the understanding that I mean "nothing extra from what has to be there") $\endgroup$ – Max Jan 23 at 16:47
  • $\begingroup$ Maybe instead of "no noise", something like "no crushing" or "no folding"? $\endgroup$ – Daniel Schepler Jan 23 at 22:05
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "> ... which would not make your choice completely free" I feel like you are using the commuting triangle here, but I don't fully understand how, am I right? Could you please elaborate on it? $\endgroup$ – neshkeev Jan 25 at 19:22
  • $\begingroup$ Maybe I was a little sloppy in my formulation there. The "commuting triangle" expresses that a morphism $\bar{f} : M(A) \to N$ takes the same value as a given function $f : A \to N$. We already know that a morphism is determined by its values on elements of $A$, and trying to answer the converse : "How free am I to pick a value to associate to each elements of $A$, such that I can extend this into a morphism?" You have to pick values that satisfy the relations satisfied by elements of $A$ in $M(A)$. When they don't satisfy any relation (no noise), you are free to pick anything you want $\endgroup$ – Thibaut Benjamin Jan 27 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.