What Is the Universal Mapping Property in Free Monoids According to Awodey?

[Math Amateur]

I am reading Steve Awodey's book of category theory.

I am, at the moment, studying the Universal Mapping Property for free monoids \(\displaystyle M(A)\).

The UMP and the start of its proof read as follows:

View attachment 2538

I am uncertain about the definition of \(\displaystyle \ \overline{f} : \ A^* \to N \).

What does Awodey mean when he writes the following:

\(\displaystyle \overline{f}(-) = u_N \)

Does he mean that all of \(\displaystyle M(A) \) maps to \(\displaystyle u_N \)?

Further, how does Awodey get the relationship \(\displaystyle \overline{f} (a) = f(a) \)?

If \(\displaystyle \overline{f}(-) = u_N \) means everything maps to \(\displaystyle u_N \) then :

\(\displaystyle \overline{f}(a) = u_N \)

and

\(\displaystyle f(a) = ?\)Can someone please clarify this situation for me?To give MHB members the context and notation for the above I am providing Awodey Section 1.7 up to the UMP, as follows:

View attachment 2539
View attachment 2540

A further puzzle for me is the following:

On page 18 (see above) Awodey writes:

" ... every monoid N has an underlying set |N, and every monoid homomorphism \(\displaystyle f \ : \ M \to N \) has an underlying function \(\displaystyle |f| \ : \ |M| \to |N| \). It is easy to see that this is a functor, called the "forgetful functor". "

How would one go about proving that |f| is a functor?

By the way, presumably it is "forgetful" because it ignores structure, treating the monoids M and N as sets?Hope someone can help.

Peter

 

[Deveno]

Yes, that is the basic idea of a forgetful functor.

I believe that by $f(-) = u_N$ Awodey is saying the empty word maps to the unit of $N$.

Also $\overline{f}$ maps "(reduced) words" in $A^{\ast}$ to "products (in $N$) of the images (under $f$) of the letters". Since an element of $A$ is just a letter (a word of length one), any such element maps to the image of that element under $f$.

The "letters" in $A^{\ast}$ map to the "generators" of $\overline{f}(M(A))$, in general, there will be non-trivial relations among the elements of $\overline{f}(M(A))$.

I want to remark in passing that the free monoid generated by $A$ (also called the Kleene star of $A$) isn't really unique, just unique up to a unique isomorphism (the same way a polynomial ring in one indeterminate over a field $K$ isn't unique, but in some sense "they're all alike". For example, there is only ONE isomorphism:

$K[x] \to K[y]$

that fixes $K$ and sends $x \to y$).

The situation is this: we are defining a structure by some properties it has: namely, that certain diagrams commute. Well, that's all very fine and dandy, but does anything actually HAVE that property? Awodey is saying yes, and here it is.

The next natural step is to show that if two monoids, $M$ and $M'$, have the UMP, that $M \cong M'$. This shows that the structure so defined is meaningful, in that it essentially defines a "unique" (that is to say, unique up to a unique isomorphism, a common "relaxation" of uniqueness in algebra) structure.

And the up-shot of this, is that it doesn't matter "how" we go about getting our hands on a free monoid generated by $A$, any way we do so gets us to something that "is as good as any other".

The operation of "concatenation" is, by the way, a natural "model" for the idea of composition of arrows in a category: first one thing, then the next.

 

[Math Amateur]

Yes, that is the basic idea of a forgetful functor.

I believe that by $f(-) = u_N$ Awodey is saying the empty word maps to the unit of $N$.

Also $\overline{f}$ maps "(reduced) words" in $A^{\ast}$ to "products (in $N$) of the images (under $f$) of the letters". Since an element of $A$ is just a letter (a word of length one), any such element maps to the image of that element under $f$.

The "letters" in $A^{\ast}$ map to the "generators" of $\overline{f}(M(A))$, in general, there will be non-trivial relations among the elements of $\overline{f}(M(A))$.

I want to remark in passing that the free monoid generated by $A$ (also called the Kleene star of $A$) isn't really unique, just unique up to a unique isomorphism (the same way a polynomial ring in one indeterminate over a field $K$ isn't unique, but in some sense "they're all alike". For example, there is only ONE isomorphism:

$K[x] \to K[y]$

that fixes $K$ and sends $x \to y$).

The situation is this: we are defining a structure by some properties it has: namely, that certain diagrams commute. Well, that's all very fine and dandy, but does anything actually HAVE that property? Awodey is saying yes, and here it is.

The next natural step is to show that if two monoids, $M$ and $M'$, have the UMP, that $M \cong M'$. This shows that the structure so defined is meaningful, in that it essentially defines a "unique" (that is to say, unique up to a unique isomorphism, a common "relaxation" of uniqueness in algebra) structure.

And the up-shot of this, is that it doesn't matter "how" we go about getting our hands on a free monoid generated by $A$, any way we do so gets us to something that "is as good as any other".

The operation of "concatenation" is, by the way, a natural "model" for the idea of composition of arrows in a category: first one thing, then the next.

Thanks Deveno ... working through post now and reflecting on what you have said ...

Thanks again for the help ...

Peter

 

[Math Amateur]

Yes, that is the basic idea of a forgetful functor.

I believe that by $f(-) = u_N$ Awodey is saying the empty word maps to the unit of $N$.

Also $\overline{f}$ maps "(reduced) words" in $A^{\ast}$ to "products (in $N$) of the images (under $f$) of the letters". Since an element of $A$ is just a letter (a word of length one), any such element maps to the image of that element under $f$.

The "letters" in $A^{\ast}$ map to the "generators" of $\overline{f}(M(A))$, in general, there will be non-trivial relations among the elements of $\overline{f}(M(A))$.

I want to remark in passing that the free monoid generated by $A$ (also called the Kleene star of $A$) isn't really unique, just unique up to a unique isomorphism (the same way a polynomial ring in one indeterminate over a field $K$ isn't unique, but in some sense "they're all alike". For example, there is only ONE isomorphism:

$K[x] \to K[y]$

that fixes $K$ and sends $x \to y$).

The situation is this: we are defining a structure by some properties it has: namely, that certain diagrams commute. Well, that's all very fine and dandy, but does anything actually HAVE that property? Awodey is saying yes, and here it is.

The next natural step is to show that if two monoids, $M$ and $M'$, have the UMP, that $M \cong M'$. This shows that the structure so defined is meaningful, in that it essentially defines a "unique" (that is to say, unique up to a unique isomorphism, a common "relaxation" of uniqueness in algebra) structure.

And the up-shot of this, is that it doesn't matter "how" we go about getting our hands on a free monoid generated by $A$, any way we do so gets us to something that "is as good as any other".

The operation of "concatenation" is, by the way, a natural "model" for the idea of composition of arrows in a category: first one thing, then the next.

Just a further three questions on Awodey's proof of the UMP for free monoids:

Notation - I am assuming that |M(A)| = A*. Is that correct?

To prove the UMP for free monoids we need to demonstrate the existence of a unique monoid homomorphism \(\displaystyle \overline{f} : \ M(A) \to N \) such that \(\displaystyle | \overline{f} | \circ i = f \) ... ...

BUT Awodey shows \(\displaystyle g = \overline{f} \) ... how is this equivalent to showing that \(\displaystyle | \overline{f} | \circ i = f \) ... ... ?

Further, it seems to me that the expression \(\displaystyle | \overline{f} | \circ i = f \) is a little incoherent since i and f are functions (as they should be, but according to Awodey's notation \(\displaystyle | \overline{f} | \) is a set ... appearing in a composition of functions ... ... ?

Can someone please clarify these issues for me?

Peter

***EDIT*** It has just occurred to me that showing \(\displaystyle g = \overline{f} \) is Awodey demonstrating the uniqueness of \(\displaystyle \overline{f} \)!

... ... am I correct ...?

BUT then where does Awodey show \(\displaystyle | \overline{f} | \circ i = f \) ... maybe this is obvious since \(\displaystyle \overline{f} (a) = f(a) \) for all \(\displaystyle a \in A \)?

Peter

 

[Math Amateur]

Just a further three questions on Awodey's proof of the UMP for free monoids:

Notation - I am assuming that |M(A)| = A*. Is that correct?

To prove the UMP for free monoids we need to demonstrate the existence of a unique monoid homomorphism \(\displaystyle \overline{f} : \ M(A) \to N \) such that \(\displaystyle | \overline{f} | \circ i = f \) ... ...

BUT Awodey shows \(\displaystyle g = \overline{f} \) ... how is this equivalent to showing that \(\displaystyle | \overline{f} | \circ i = f \) ... ... ?

Further, it seems to me that the expression \(\displaystyle | \overline{f} | \circ i = f \) is a little incoherent since i and f are functions (as they should be, but according to Awodey's notation \(\displaystyle | \overline{f} | \) is a set ... appearing in a composition of functions ... ... ?

Can someone please clarify these issues for me?

Peter

***EDIT*** It has just occurred to me that showing \(\displaystyle g = \overline{f} \) is Awodey demonstrating the uniqueness of \(\displaystyle \overline{f} \)!

... ... am I correct ...?

BUT then where does Awodey show \(\displaystyle | \overline{f} | \circ i = f \) ... maybe this is obvious since \(\displaystyle \overline{f} (a) = f(a) \) for all \(\displaystyle a \in A \)?

Peter

I have just realized I (for some reason ... moving too fast ... not being careful enough) have confused and conflated the UMP and Proposition 1.9 ... so I have marked the thread as "Solved"

Peter

 

[Deveno]

To answer your question, I believe that by $|\overline{f}|$ Awodey means the underlying function of the monoidal homomorphism $\overline{f}$. In the normal treatment of free monoids (or groups, or modules), this distinction is often not even made, so that the two are just referred to by the same symbol.

Basically, we are talking about a version of an "evaluation" map here: we take letters (the free generators in the free monoid) and map them to a set of monoid generators, and then, for any word in the letters, form the same "word" as a product in the monoid, and carry out the multiplication (which will wind up being some element of the monoid).

The map $i$ is called "inclusion of generators" $i:A \to M(A)$ and encodes the idea that $M(A)$ is generated by $A$. Categorically, all we require is that this be an injective function, but it is often (somewhat inaccurately) denoted simply by $1_A$.

These functions should be "transparent" all we are really doing is "changing names around".

To give an explicit example:

Suppose $A = \{a,b,c\}$, our target monoid is $\Bbb N$ (under addition) and we have a function:

$f(a) = 3$
$f(b) = 4$
$f(c) = 7$.

Then the monoid homomorphism we are saying exists takes words in the "alphabet" $A$, to sums involving 3,4 and 7, for example:

$abac \mapsto 17$.

If you wanted to, you COULD regard $|\overline{f}|$ as a set, namely:

$|\overline{f}| = \{(x,y) \in |M(A)| \times |N|: y = |\overline{f}|(x)\}$.

which is what we mean when we write:

$|M(A)| \stackrel{|\overline{f}|}{\to} |N|$ or even:

$x \stackrel{|\overline{f}|}{\mapsto} y$

You've seen these types of sets displayed pictorally before, we call them graphs.

 

[Math Amateur]

To answer your question, I believe that by $|\overline{f}|$ Awodey means the underlying function of the monoidal homomorphism $\overline{f}$. In the normal treatment of free monoids (or groups, or modules), this distinction is often not even made, so that the two are just referred to by the same symbol.

Basically, we are talking about a version of an "evaluation" map here: we take letters (the free generators in the free monoid) and map them to a set of monoid generators, and then, for any word in the letters, form the same "word" as a product in the monoid, and carry out the multiplication (which will wind up being some element of the monoid).

The map $i$ is called "inclusion of generators" $i:A \to M(A)$ and encodes the idea that $M(A)$ is generated by $A$. Categorically, all we require is that this be an injective function, but it is often (somewhat inaccurately) denoted simply by $1_A$.

These functions should be "transparent" all we are really doing is "changing names around".

To give an explicit example:

Suppose $A = \{a,b,c\}$, our target monoid is $\Bbb N$ (under addition) and we have a function:

$f(a) = 3$
$f(b) = 4$
$f(c) = 7$.

Then the monoid homomorphism we are saying exists takes words in the "alphabet" $A$, to sums involving 3,4 and 7, for example:

$abac \mapsto 17$.

If you wanted to, you COULD regard $|\overline{f}|$ as a set, namely:

$|\overline{f}| = \{(x,y) \in |M(A)| \times |N|: y = |\overline{f}|(x)\}$.

which is what we mean when we write:

$|M(A)| \stackrel{|\overline{f}|}{\to} |N|$ or even:

$x \stackrel{|\overline{f}|}{\mapsto} y$

You've seen these types of sets displayed pictorally before, we call them graphs.

Thanks Deveno ... most helpful ... especially the example ... great to have examples, wish the texts would have more of them!

Just a question regarding \(\displaystyle |\overline{f}| \). You write:

" ... I believe that by $|\overline{f}|$ Awodey means the underlying function of the monoidal homomorphism $\overline{f}$. ... ... "

Can you explain the exact nature of the underlying function ... it is the homomorphism treated as a map between sets ... BUT ... how does this work ... the homomorphism is defined in terms of the operations in the monoids ... so how do we deal with trying to move it to sets with no operation ... how do we drop the operations and still have a mapping related to the homomorphism?

I am struggling a bit to express my question ... apologies ...

Hope you can clarify the exact nature of the underlying function for me ...A second issue/question is the following:

You write:

" ... ... Basically, we are talking about a version of an "evaluation" map here: we take letters (the free generators in the free monoid) and map them to a set of monoid generators, ... ... "

Now this reads as if you are saying that the free letters are not (necessarily) the same as the generators ... but aren't the free letters exactly the generators?

Hope you can help with this issue/question as well?

Note that I am finding Awodey's text quite a challenge and in particular finding universal mapping properties a bit mysterious (at least the motivation for them) - e.g. what are they for? why are we stating and proving them? how do they help? and in particular (big mystery to me!) - why are we dealing with maps onto any monoid, group, ring, module ... what do we learn from this ...

Hope you can help ...Peter

PS I may move from Awodey to do some reading of the text:

Conceptual Mathematics: A First Introduction to Categories by F. William Lawvere and Stephen H. Scanuel

which is reputed to be simpler and reputed to contain better motivational introductions to various concepts .. do you know the text?

 

[Deveno]

A homomorphism is not DEFINED in terms of the operation-preserving properties that it has. I know this may seem confusing, because often one says:

"Let $f:A \to B$ be a homomorphism, so that $f(a\ast a') = f(a)\ast f(a')$..."

but that is just leveraging a property that $f$ has, what $f$ actually is (as a map) is determined by something like:

"Let $f$ be the map defined by $f(a) =\dots$

For example, the map that takes $k \to 2k$ is a monoid homomorphism $\Bbb N \to \Bbb N$ (the "doubling map"). Even if we "forget" any notion we have about addition, the map that sends:

$0 \to 0$
$1 \to 2$
$2 \to 4$
$3 \to 6\dots$

is still a well-defined function. Note we could have chosen to define $f$ "recursively":

$f(0) = 0$

$f(s(k)) = s(s(f(k)))$ (where $s$ is the successor function; that is, for every "step" we increment the input, we increment the output 2 steps).

When we "forget" a homomorphism has its operation-preserving property, we don't "change" anything to the way we compute $f(a)$ from $a$, we just don't "do anything (sums/products) with it" because there's nothing to DO (the operations don't even "exist").

As you might suspect, there are lots of "forgetful functors":

$\mathbf{Vect}_K \to \mathbf{AbGrp}$ which forgets scalar multiplication
$\mathbf{Ring} \to \mathbf{Mon}$, which forgets the addition
$\mathbf{AbGrp} \to \mathbf{Grp}$, which forgets commutativity
$\mathbf{Top} \to \mathbf{Set}$, which forgets the neighborhoods (topology).

*************

As to why we consider ANY map $A \to N$, it has to do with how we define binary operations. A binary operation on a set $S$ is a map:

$\ast: S \times S \to S$.

Now one can define such a operation by specifying triples $(a,b,c)$ where $c = a \ast b$. One way of doing this, is to create a TABLE (called a Cayley table, after the mathematician who first investigated some of these things). But often it is easier to do so by specifying some RULES. For example, suppose we start with the monoid $\Bbb N$. Define an equivalence $\sim$ on $\Bbb N$ by:

$k \sim m \iff \exists t \in \Bbb N: |k - m| = 6t$

Rather than explicitly calculating the equivalence classes $[k]$ and then creating a table (which would have 36 entries) to define "$+_{\sim}$", we can do this instead:

$[k]+_{\sim}[m] \equiv [k+m]$

which allows us to evaluate the sum in the monoid we already have (the natural numbers), and then lookup the equivalence class.

The monoid $\Bbb N$ is free on the generator 1, that is, the natural numbers are:

0, the "empty number"
1, the generator
2 = 1+1
3 = 1+1+1...

there is a natural (monoid) isomorphism between "natural numbers" and "tally marks" (concatenations of the single letter "|"). There is reason to believe this isomorphism is hard-wired into our brains as "counting" (virtually all human languages contain words for numbers, for example).

OK, now in this special case (a free monoid on one generator), what, exactly, is a function $f:\{1\} \to N$?

Basically, it's the same as "picking an element $n \in N$" (namely, whatever $f(1)$ is). So what the UMP is saying is this particular case, is that ANY monoid homomorphism $\phi:\Bbb N \to N$ is UNIQUELY determined by $\phi(1)$. In particular, any (homomorphic) image of $\Bbb N$ is generated by a single element.

Similar arguments hold for a set of any cardinality. In particular, if the map $A \to N$ is injective, and $|A|$ is finite, say $m$, we can say $N$ has (no more than) $m$ generators, that is any element in $N$ is realizable as a product of images of the mapping from $A$.

If the map $A \to N$ is NOT injective, all that means is that we have "fewer generators for $N$" then there are elements in $A$.

I am not familiar with the book you mention, but I do know that Lawvere is one of the leaders in the field.

 

[Math Amateur]

A homomorphism is not DEFINED in terms of the operation-preserving properties that it has. I know this may seem confusing, because often one says:

"Let $f:A \to B$ be a homomorphism, so that $f(a\ast a') = f(a)\ast f(a')$..."

but that is just leveraging a property that $f$ has, what $f$ actually is (as a map) is determined by something like:

"Let $f$ be the map defined by $f(a) =\dots$

For example, the map that takes $k \to 2k$ is a monoid homomorphism $\Bbb N \to \Bbb N$ (the "doubling map"). Even if we "forget" any notion we have about addition, the map that sends:

$0 \to 0$
$1 \to 2$
$2 \to 4$
$3 \to 6\dots$

is still a well-defined function. Note we could have chosen to define $f$ "recursively":

$f(0) = 0$

$f(s(k)) = s(s(f(k)))$ (where $s$ is the successor function; that is, for every "step" we increment the input, we increment the output 2 steps).

When we "forget" a homomorphism has its operation-preserving property, we don't "change" anything to the way we compute $f(a)$ from $a$, we just don't "do anything (sums/products) with it" because there's nothing to DO (the operations don't even "exist").

As you might suspect, there are lots of "forgetful functors":

$\mathbf{Vect}_K \to \mathbf{AbGrp}$ which forgets scalar multiplication
$\mathbf{Ring} \to \mathbf{Mon}$, which forgets the addition
$\mathbf{AbGrp} \to \mathbf{Grp}$, which forgets commutativity
$\mathbf{Top} \to \mathbf{Set}$, which forgets the neighborhoods (topology).

*************

As to why we consider ANY map $A \to N$, it has to do with how we define binary operations. A binary operation on a set $S$ is a map:

$\ast: S \times S \to S$.

Now one can define such a operation by specifying triples $(a,b,c)$ where $c = a \ast b$. One way of doing this, is to create a TABLE (called a Cayley table, after the mathematician who first investigated some of these things). But often it is easier to do so by specifying some RULES. For example, suppose we start with the monoid $\Bbb N$. Define an equivalence $\sim$ on $\Bbb N$ by:

$k \sim m \iff \exists t \in \Bbb N: |k - m| = 6t$

Rather than explicitly calculating the equivalence classes $[k]$ and then creating a table (which would have 36 entries) to define "$+_{\sim}$", we can do this instead:

$[k]+_{\sim}[m] \equiv [k+m]$

which allows us to evaluate the sum in the monoid we already have (the natural numbers), and then lookup the equivalence class.

The monoid $\Bbb N$ is free on the generator 1, that is, the natural numbers are:

0, the "empty number"
1, the generator
2 = 1+1
3 = 1+1+1...

there is a natural (monoid) isomorphism between "natural numbers" and "tally marks" (concatenations of the single letter "|"). There is reason to believe this isomorphism is hard-wired into our brains as "counting" (virtually all human languages contain words for numbers, for example).

OK, now in this special case (a free monoid on one generator), what, exactly, is a function $f:\{1\} \to N$?

Basically, it's the same as "picking an element $n \in N$" (namely, whatever $f(1)$ is). So what the UMP is saying is this particular case, is that ANY monoid homomorphism $\phi:\Bbb N \to N$ is UNIQUELY determined by $\phi(1)$. In particular, any (homomorphic) image of $\Bbb N$ is generated by a single element.

Similar arguments hold for a set of any cardinality. In particular, if the map $A \to N$ is injective, and $|A|$ is finite, say $m$, we can say $N$ has (no more than) $m$ generators, that is any element in $N$ is realizable as a product of images of the mapping from $A$.

If the map $A \to N$ is NOT injective, all that means is that we have "fewer generators for $N$" then there are elements in $A$.

I am not familiar with the book you mention, but I do know that Lawvere is one of the leaders in the field.

Thanks Deveno ... I am finding this post EXTREMELY informative and helpful ... the post really clarifies some of the mysteries of category theory ... ... I wish the various texts could be as clear and helpful ...

Still reflecting on your post ...

Peter