Notational clarification needed about definition and a lemma concerning functor and free monoid

38 Views Asked by At

The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes.

$\color{Green}{Background:}$

$\textbf{(1)}$ $\textbf{(Definition 1:)}$ The $\textbf{Free monoid on the set X of generators}$ is the set $X^*$ of all finite sequences of elements from $X$ (including the "empty" sequence $\Lambda$ of length $0$) with associative multiplication of $\textbf{concatenation}$

$$(x_1\ldots x_m)\cdot ({x_1}^{'}\ldots {x_n}^{'})=(x_1\ldots x_m, {x_1}^{'}\ldots {x_n}^{'})$$

for which $\Lambda$ is clearly the identity: $\Lambda\cdot w=w=w\cdot \Lambda$ for all $w\in X^*.$ Note that an element $x$ yields a string $(x)$ in $X^*$ of length one.

Quite apart from its fundamental role in automatta theory and formal language theory, ($X^{*}, \text{conc,}\Lambda$) is interesting because of the following property:

Given any monoid $M=(S,\cdot, e)$ and any map $f$ from $X$ to $S$ viewed as a set, there is a unique homomorphism $\psi$ from ($X^{*}, \text{conc, }\Lambda$) to ($S,\cdot,e$) which extends $f,$ i.e. such that $\psi((x))=f(x)$ for each $x$ in $X;$ $\psi(w\cdot w')=\psi(w)\cdot\psi(w')$ for all $w, w'$ in $X^{*}=e.$ In fact, it is clear that the one and only homomorphism $\psi$ satisfying these requirements is defined by

$$\psi(\Lambda)=e$$

$$\psi((x_1,\ldots, x_n))=f(x_1)\cdot\ldots\cdot f(x_n).$$

Using $\eta:X\to X^{*}$ to denote the "inclusion of generators" map $x\mapsto (x),$ we may express the situation in the following categorical form:

$\textbf{(2)}$ The monoid $A=(X^{*},\text{conc, }\Lambda)$ [for which $UA=X^{*},$ where $U:\textbf{Mon}\to\textbf{Set}$ is the forgetful functor] is equipped with a map $\color{brown}{\eta:X\to {UA}}$ in such a way that, given any other monoid $M$ and any map $f:X\to {UM},$ there exists a unique $\textit{homomorphism }\psi$ such that

enter image description here

Now, extending our terminology, we are saying that $X\xrightarrow{\eta}{UA}$ is couniversal among diagrams of the form $X\xrightarrow{f}{UM},$ for fixed $X,$ subject to extra condition that the "bridging morphism" be of the form ${U\psi},$ where $\psi$ is a $\textbf{Mon}-$ morphism, rather than being arbitrary. However, the argument of uniqueness up to isomorphism is still an application and we have:

$\textbf{(3)}$ $\textbf{Lemma: A}$ monoid $A$ equipped with a map $\eta:X\to{UA}$ satisfies the condition $\textbf{(2)}$ iff there exists a monoid isomorphism $\psi:A\to(X^{*},\text{conc, }\Lambda)$ such that $\color{blue}{(U\psi\cdot \eta)(x)=(x)}$ for all $x$ in $X.$

$\color{Red}{Questions:}$

The map $\color{brown}{\eta:X\to {UA}}$ in $\textbf{(2)}$ is just a regular map and not a functor. The presence of ${UA}$ is a bit confusing since ${U\psi}:{UA}\dashrightarrow{UM}$ is a functor.

Also, in $\textbf{(3) Lemma,}$ should $\color{blue}{(U\psi\cdot \eta)(x)=(x)}$ be ${(U\psi\cdot \eta)(x)=f(x)}?$ What I mean is the following: we know that $X\xrightarrow{\eta}UA:x\to (x),$ is a map and $UA\xrightarrow{U\psi}UM,$ is a functor. Also $(\psi\cdot\eta)(x)=\psi((x)),$ and $\psi((x))=f(x),$ because both $(U\psi\cdot\eta)(x), f(x)\in UM.$ Hence should $(U\psi\cdot\eta)(x)=f(x),$ and not $(U\psi\cdot\eta)(x)=(x).$ Actually, if it is the former, I am not sure how to justify it. I feel that the existence part of the discussion is not very clear.

1

There are 1 best solutions below

1
On

The map $\color{brown}{\eta:X\to {UA}}$ in $\textbf{(2)}$ is just a regular map and not a functor. The presence of ${UA}$ is a bit confusing since ${U\psi}:{UA}\dashrightarrow{UM}$ is a functor.

Yes, $\eta$ is a function between sets and is not assumed to preserve any monoid structure (if it existed) on $X$.

As for $\psi$ vs $U\psi$, $\psi$ is a monoid homomorphism (what you're calling a functor), while $U\psi$ is the underlying function of a monoid homomorphism. In some contexts it's alright to call the underlying function of a homomorphism a homomorphism but it's important to know that $\psi$ is a morphism in the category of monoids while $U\psi$ is a morphism in the category of sets.

Also, in $\textbf{(3) Lemma,}$ should $\color{blue}{(U\psi\cdot \eta)(x)=(x)}$ be ${(U\psi\cdot \eta)(x)=f(x)}?$

No. Lemma 3 reuses a bunch of letters but gives them different meanings, so be careful to keep track of what's redefined. In particular, $A$ is now just an arbitrary monoid rather than $A=(X^{*},\text{conc, }\Lambda)$, $\eta$ is just an arbitrary function $X \to UA$, and $\psi$ is a monoid homomorphism $A\to(X^{*},\text{conc, }\Lambda)$. If it helps, replace these with some other letters.

$f$ doesn't exist in this context, so we can't use it. In section 2, it was an arbitrary function $X \to UM$, but it isn't mentioned at all in lemma 3. For that matter, $M$ isn't mentioned in lemma 3 either.