text:
\section{The main theorem, and connections}

\subsection{Proof of the main theorem}

Recall Corollary~\ref{lcsdefined} that our letter-linking invariants are well-defined on  lower central series subquotients.
Our main result in this paper is the following.

\begin{theorem}\label{main}
The homomorphisms $\Phi : \Q \sy_i \to {\rm Hom}(\gamma_i F_n / \gamma_{i+1} F_n, \Q)$
are surjective.
\end{theorem}

Before proving this, we need a last calculational tool, motivated by the operadic approach to free Lie algebras.
We relate values of our letter-linking invariants under homomorphisms
 induced by set maps of generators.

 \begin{definition}
 Let $F_S$ denote the free group on the generating set $S$.
 Let $f : S \to T$ be a map of generating sets, and let $f_*$ denote the induced homomorphism on free groups as well as the induced
 map on the set of symbols.
 Let $\Sigma_f$ denote the automorphisms of $S$ which commute with $f$.
 \end{definition}

The automorphisms $\Sigma_f$ are  isomorphic to a product of symmetric groups.

\begin{theorem}\label{lifts}
Let $f : S \to T$ be a map of (generating) sets, $w \in UC(n)$ and $\sigma$ a symbol on $S$ of depth $n$.  Then
$$\Phi_{f_* \sigma} (f_* w) = \sum_{p \in \Sigma_f} \Phi_{p \cdot \sigma} (w).$$
\end{theorem}

We use this to understand letter-linking invariants with repeated letters, relating them to those with
unique letters, which are understood through Theorem~\ref{graph-symbol-pairing}.

\begin{proof}[Proof of Theorem~\ref{lifts}]

We first show that
$$\Phi_{f_* \sigma} (f_* w) = \sum_{ \widetilde{\sigma} |  f_*(\widetilde{\sigma}) = f(\sigma)} \Phi_{\widetilde{\sigma}} (w).$$
The sum contains the sum named in the theorem, along with additional terms which we will show vanish.

We prove this equality through analysis of lists, showing inductively that
$\Lambda_{f_* \mu} (f_* w) \cong \bigcup  \Lambda_{\widetilde{\mu}} (w)$ -- that is, that these are in bijective correspondence respecting $f$ --
where the  union is over $\widetilde{\mu}$ such that $f_*(\widetilde{\mu}) = f_*(\mu)$.
For $\mu$ of depth zero, that is lists of occurrences of some generator, this is immediate.
Suppose this equality of lists holds for $\mu_1$ and $\mu_2$ of depth less than $n$.  By Theorem~\ref{definedonlcs} all of the $\Phi_{\widetilde{\mu_1}} (w)$
vanish, so we may choose all $d^{-1} \Lambda_{\widetilde{\mu_1}} (w)$.  Through our inductive bijection, the images of these under $f_*$ gives a choice of
$d^{-1} \Lambda_{f_* \mu_1} (f_* w)$.  Moreover, each intersection of $\Lambda_{f_* \mu_2} (f_*w)$ with this cobounding corresponds to  the intersection of
some $ \Lambda_{\widetilde{\mu_2}} (w)$ with a $d^{-1} \Lambda_{\widetilde{\mu_1}} (w)$.  Through the bijective correspondence of
the product of the set of $\widetilde{\mu_1}$ over $\mu_1$
and the set of $\widetilde{\mu_2}$ over $\mu_2$ with the set of $\widetilde{(\mu_1) \mu_2}$ over $(\mu_1) \mu_2$, we establish
our inductive step that $\Lambda_{f_* (\mu_1) \mu_2 } (f_* w) \cong \bigcup  \Lambda_{\widetilde{(\mu_1) \mu_2}} (w)$ and thus
our first equality.

To deduce the equality of the theorem we see that  terms in the sum
 $\sum_{ \widetilde{\sigma} |  f_*(\widetilde{\sigma}) = f(\sigma)} \Phi_{\widetilde{\sigma}} (w)$  which are not of the
form $p \cdot \sigma$ for $p \in \Sigma_f$ must have some repeated letter.  But  $w \in UC(n)$, so there will be at least one  letter
which occurs in $w$ but not $\widetilde{\sigma}$.  That letter can then be removed from $w$ without changing $\Lambda_{\widetilde{\sigma}}$.
But removing the letter from $w$ is equivalent to replacing the letter by the identity element.  Since $w$ is a commutator the resulting word would
represent the identity element.
\end{proof}

We now extend Theorem~\ref{graph-symbol-pairing} from graphs with unique vertex labels to all distinct-vertex graphs.

\begin{definition}
Let $w \in \gamma_i F_n$, and let $W$ be the span of generators of $F_n$. We set the {\bf Lie image} of $w$,
denoted  $\lambda(w) \in \fL_n \cong \Lie(i) \otimes W$,
to be the image of $w$ in $ \gamma_i F_n / \gamma_{i+1} F_n$, composed with its isomorphism with the $i$th graded component
of the free Lie algebra.
\end{definition}

In particular, $\lambda(w)$ converts a commutator in the generators (which we call a {\bf basic commutator})
to the corresponding Lie bracket.  Theorem~\ref{lifts} leads to the following.

\begin{corollary}\label{last}
$\Phi_G (w) = \langle G, \lambda(w) \rangle$, where $\langle -,  -\rangle$ denotes the configuration pairing.
\end{corollary}

\begin{proof}

By linearity, it suffices to consider basic commutators.
Let $w$ be a basic commutator and $\tilde{w}$ be a basic commutator in unique letters
so that $f_*(\tilde{w}) = w$ for some map of generating sets $S$.  For $\Phi_G (w)$ to be non-zero
there must be a $\widetilde{G}$ with $f_*(\widetilde{G}) = G$.  Theorem~\ref{lifts} then gives a formula for $\Phi_G(w)$.  But
we can apply Theorem~\ref{graph-symbol-pairing} to every term in the right-hand side.  Doing so we obtain terms in the definition
of $\langle G, \lambda(w) \rangle$, which is the extension of the pairing between $\Eil(i)$ and $\Lie(i)$ and Kronecker pairing
on $W$ to
$\Eil(i) \otimes_{\si_n} W^{\otimes i}$ and $\Lie(i) \otimes_{\si_n} W^{\otimes i}$.
The terms in this extension which do not occur in the application of Theorem~\ref{lifts} will not contribute to this sum, as the Kronecker pairing will be zero.
\end{proof}

The proof of our main result is now a matter of assembly.

\begin{proof}[Proof of Theorem~\ref{main}]
 By Proposition~\ref{reductionsurjective}, any symbol $\sigma \in \sy_n = \gs_{n,0}$
 is the reduction of some graph $G$ in $\gs_{0,n}$.
 By Corollary~\ref{last}, the values of $\Phi_\sigma$ on $\gamma_i F_n$ coincide with the configuration pairing
 of $G$ on the $i$-graded summand of $\fL_n$.
 By Theorem~\ref{distinctspan}, configuration pairings with distinct-vertex graphs span the functionals given by all graphs.
 By Corollary~3.3 of \cite{SiWa11} pairing with all such graphs modulo Arnold and antisymmetry is perfect
 on this $i$-graded summand, which is isomorphic to $\gamma_i F_n / \gamma_{i+1} F_n$.
\end{proof}

\subsection{Comparison with Fox derivatives}

There is already a well-known collection of homomorphisms which span the linear dual of the lower-central series Lie algebra for
free groups, namely those
given by  Fox's free differential calculus \cite{Fox53, CFL58}, whose definition we recall below.    These differ from the functionals we
provide in substantial ways.

\begin{itemize}
\item Fox derivatives span homomorphisms to the integers, while letter-linking homomorphisms only span over the rationals.  See  Appendix~\ref{values}.
\item Fox derivatives are defined on the entire free group, while letter-linking homomorphisms are only defined on subgroups.
\item As shown below, Fox derivatives correspond to evaluation of
the linear graph spanning set for the cofree Lie coalgebra $\E_n$, while letter-linking homomorphisms correspond to evaluation of the
distinct-vertex spanning set.
\item Fox derivatives, as developed in part by Chen, Fox and Lyndon \cite{CFL58},
are more immediately compatible with the Chen model of rational homotopy theory while
letter-linking homomorphisms are drawn from the Quillen model.
\item For hand calculations, letter-linking numbers involve fewer calculations, though we conjecture below that Fox derivatives could be modified
to involve similar calculation.
\item For fundamental groups of punctured surfaces, letter-linking invariants immediately
give rise to lower bounds on the complexity of curves which represent elements
of $\gamma_i F_n$.
\end{itemize}

With our eyes towards applications to mapping class groups (first author) and non-simply connected
rational homotopy theory (second author) we believe the first two
properties in which letter-linking homomorphisms are inferior are worth trading for the properties in which
they are superior.

We now make the  connection between Fox derivatives and our model for cofree Lie coalgebras, starting with the definition
of the former.

\begin{definition}
Let $F_n$ be the free group on $n$ generators and let $\alpha: \Z[F_n]\rightarrow \Z$ be the augmentation.
A derivation $D$ is a map $D: \Z[F_n] \rightarrow \Z[F_n]$  such that
\begin{enumerate}
\item $D(u+v)=Du+Dv $
\item $D(uv)=Du\cdot \alpha(v)+ u \cdot Dv$
\end{enumerate}
\end{definition}

\begin{theorem}\cite{Fox53}
Let $x_1,\ldots, x_n$ denote the generators of the free group $F_n$.  There is a unique derivation
\[
\frac{\partial}{\partial x_i} : \Z [F_n] \rightarrow \Z[F_n]
\]
such that $\frac{\partial}{\partial x_i}(x_j)=\delta_{i,j}$,
the Kronecker delta.  We call this the Fox derivative with respect to $x_i$ and denote it by $\partial_{x_i}$.
\end{theorem}

This derivation is then iterated.

\begin{definition}
Let $c = a_1, \ldots, a_k$ be some collection of the generators $x_1,\ldots, x_n$, with repeats  allowed.
 For $v \in \Z [F_n]$ inductively define
\[
\partial_{a_1,\cdots, a_k}(v)=\partial_{a_1}(\partial_{a_2,\cdots ,a_k}(v)).
\]
Define $\partial_c^\circ(v)$ to be $\alpha(\partial_c(v))$.

\end{definition}

In Applendix~\ref{examplecalculation} we give an example of a Fox derivative calculation.  Informally, a
derivative takes every monomial and produces a sum of monomials by ``cutting'' it at each occurrence of a generator, with signs.
For example, $\partial_{a,b}$ will cut along occurrences of $b$ then along occurences of
$a$, and then through augmentation count the resulting monomials with signs.
Effectively, this counts occurrences of an $a$ followed by a $b$.  But for any $a$ followed by  an $a^{-1}$, any subsequent $b$'s
will be counted with both a $+1$ for the  $a$ and a $-1$ for the $a^{-1}$.  Thus we could streamline the calculation by counting only $b$'s between
$a$-$a^{-1}$ pairs -- that is, the count $\Phi_{(a)b}$.

After depth three, Fox derivatives and letter-linking invariants do not coincide, as follows from calculations in
Appendix~\ref{values} and its generalizations.
But we could express Fox derivatives in the same graphical context we use in Section~\ref{examples}  to calculate and
understand our letter-linking invariants.

In \cite{CFL58} the authors produce a collection of $c=a_1\cdots a_k$ so that $\partial_c^\circ$
form a basis for the dual space of each $\gamma_i F_n/ \gamma_{i+1}F_n$.  We produce a new proof of this fact in
order to compare  Fox derivatives with letter-linking invariants, starting with the analogue of Corollary~\ref{last}.

\begin{theorem}
Let $c=a_1, \cdots ,a_k$ and let $G_c$ be the graph $\longgraph{a_1}{a_{2}}{\cdots}{a_{k}}$, and let $w \in \gamma_k F_n$.
Then $\partial^\circ_c w = \langle G_c, \lambda (w) \rangle$.
\end{theorem}

\begin{proof}
Equation (3.3) of \cite{CFL58} states that for $u \in \gamma_i F_n$, $v \in \gamma_j F_n$ with $i + j = k$,
$$\partial^\circ_c([u,v])= \partial^\circ_{c_f} (u) \partial^\circ_{c_l} (v)  - \partial^\circ_{c'_l} (u)  \partial^\circ_{c'_f} (v),$$
where $c_f = a_1, \cdots, a_i$, $c'_f = a_1, \cdots, a_j$, and $c_l$ and $c'_l$ are their complements in $c$.

We compare this equality  with the bracket-cobracket formula
$\langle G_c, \lambda ([u,v]) \rangle = ] G_c [ u \otimes v$, established in Corollary 3.14 of \cite{SiWa11}.
Since $] G_c [ = G_{c_f} \otimes G_{c_l} - G_{c'_l} \otimes G_{c'_f}$,  these formulae agree.
Because these formulae determine the values of the Fox derivatives and graph coalgebra pairings, they establish
the theorem inductively, starting with the weight zero case which is immediate.
\end{proof}

As developed in \cite{CFL58},
the bracket-cobracket reduction formula for Fox derivatives then shows that they yield the coefficients of
the map from the free Lie algebra to its universal enveloping algebra, which is the tensor algebra.
By Remark~1.5 of \cite{Walt20}, the resulting functionals on the free Lie algebra
are represented by the linear graph spanning set, or basis if one
choses a subset of linear graphs such as
Lyndon-Shirsov words.  But  such linear graphs are not generally distinct-vertex graphs.
We show in Appendix~\ref{values} that the spanning set for linear functions we develop,
represented by distinct vertex graphs, is distinct from this classical spanning set.

Both letter-linking invariants and Fox derivatives are roughly order $n^d$ to compute, where $n$ is the length of the word and $d$ is the depth,
as both can be viewed as producing and counting with signs on the order of $n^d$ sub-words.
Based on the argument that $\partial_{a,b} = \Phi_{(a)b}$ above and the examples in Appendix~\ref{examplecalculation}, we
conjecture that with finer analysis the ``from the definition'' calculation of letter-linking invariants is more efficient
than that of Fox derivatives, but that they become comparable to compute once
cancellation in Fox derivative expansion is systematically accounted for.  We suggest such analysis for further work, perhaps after
all of these techniques can be extended  to other groups, as suggested in the next section.

\subsection{Further directions}

We expect our new insight into the lower central series Lie algebra of free groups, first
studied by Magnus eighty years ago \cite{Magn37}, will have impact in a few directions.

In algebra, an immediate question is whether and how letter-linking invariants could be generalized to arbitrary finitely presented groups.
For example,  the fundamental group of the genus-two surface has four generators $a, \ldots d$ and the relation $[a,b]=[c,d]$.  We conjecture
there is a complete collection of letter-linking invariants which now include the linear combination $\Phi_{(a)b} + \Phi_{(c)d}$, but neither count on
its own.   We can see this invariant in the context of the formalism developed in this paper and in \cite{SiWa11} as follows.
The Lie coalgebraic bar complex on the cochains of a space provides the setting for Hopf invariants in higher dimensions \cite{SiWa13}.
In this paper the space in question has been a wedge of circles, whose cochains are equivalent to the first cohomology (that is, this space
is formal), resulting
in the bar complex being equivalent to the cofree Lie coalgebra $\E_n$.    In this setting of a surface, we still have formality, with the cohomology
generated by classes $A,B,C,D$, say Kronecker dual to the homology classes of $a,\ldots,d$, with the relation $AB = -CD$.  In the bar complex,
$\linep{A}{B}$ will not be a cycle, having coboundary $AB$, but $\linep{A}{B} + \linep{C}{D}$ will be a cycle.  It  will reduce to
the proposed invariant $\Phi_{(a)b} + \Phi_{(c)d}$, whose well-definedness seems more delicate, restricted to the first commutator subgroup rather than the
domain of definitions of these counts.
We expect the Lie coalgebraic bar complex to control these letter-linking invariants in general.
To our knowledge, Fox derivative techniques
have not been extended to the lower central series of other groups, so such an extension would break substantial new ground.

If  such bar complexes  produce the dual to the lower central series Lie algebra of a group, they could likely be merged with
the Lie coalgebraic models for rational homotopy in the simply connected setting.  A primary issue to resolve is that the notion of distinct vertices, which is
essential to defining letter-linking invariants, does not have a natural counterpart in higher dimensions.
If such models can be developed, they could then be compared with
new Lie models of Buijs-F\'elix-Murillo-Tanr\'e  \cite{BFMT18}, which are based on the Lawrence-Sullivan cylinder object \cite{LaSu14}.  These
new models are promising but have yielded relatively few calculations.

There are plenty of elementary questions as well.  Even in the free group case, a finer comparison of Fox derivatives as counting
occurrences of sequences of letters and letter-linking invariants would be interesting.  While we know that distinct-vertex
graphs span cofree Lie coalgebras on a set of (co)generators, we have yet to find a basis.  It would be interesting to connect
such a basis, as well as closer
analysis of relations, to the literature on (distinctly) colored trees.  Looking at the examples
in Section~\ref{values}, it seems likely that understanding the values of that basis on free Lie algebras could lead to new bases for the latter.
These examples also point to the question of computing the indices of the functionals arising from letter-linking invariants
within all integer-valued functionals.  One should decompose the free Lie algebra on a generating set
into summands by the number of times each generator occur and compute on those summands, in which case so far we only see factorials arise.


TITLE: Why is this space aspherical?
QUESTION [7 upvotes]: Let $X = Y \cup Z$ be a connected, path-connected Hausdorff space.  Suppose that $Y$, $Z$, and $Y\cap Z$ are all connected, path-connected, and aspherical, and that the homomorphism $\pi_1(Y\cap Z) \to \pi_1(Y)$ induced by inclusion is injective.
Does it follow that $X$ is aspherical?  If so, why?
Edit:  This statement is intuitively true, in the sense that a similar statement holds for homology.  That is, if we know that $H_n(Y) = H_n(Z) = H_n(Y\cap Z) = 0$ for all $n\geq 2$, and the homomorphism $H_1(Y\cap Z) \to H_1(Y)$ is injective, then it follows that $H_n(X)=0$ for all $n \geq 2$.  This is a consequence of the Mayer-Vietoris sequence:
$$
\cdots \to H_3(Y)\oplus H_3(Z) \to H_3(X) \to H_2(Y\cap Z) \to H_2(Y)\oplus H_2(Z) \to H_2(X) \to H_1(Y\cap Z) \xrightarrow{\varphi} H_1(Y) \oplus H_1(Z)
$$
Plugging in $H_n(Y)=H_n(Z) = H_n(Y\cap Z) = 0$ for $n\geq 2$, we get
$$
\cdots \to 0 \to 0 \to H_3(X) \to 0 \to 0 \to H_2(X) \to H_1(Y\cap Z) \xrightarrow{\varphi} H_1(Y) \oplus H_1(Z)
$$
Clearly $H_n(X) = 0$ for $n\geq 3$.  Moreover, since the homomorphism $H_1(Y\cap Z)\to H_1(Y)$ is the first coordinate of $\varphi$, we know that $\varphi$ is injective, and therefore $H_2(X) = 0$ as well.
The problem is that there's no good analog of the Mayer-Vietoris sequence for homotopy groups, and the versions of excision that I'm aware of only work in the case where the two component spaces are $n$-connected.  Here the spaces $Y$ and $Z$ may have nontrivial fundamental groups, and it's not clear to me how to resolve the issue using covering spaces.
By the way, I'm willing to make more topological assumptions about the spaces $X$, $Y$, and $Z$.  For example, they are certainly semi-locally simply connected and locally compact, and they probably have the homotopy type of CW complexes.

REPLY [2 votes]: This question has been asked and answered on MathOverflow. I have replicated the accepted answer by Eric Wofsey below.

This is false in general.  Let $Y=S^1\times S^1$, and let $Z$ be a disk whose boundary is identified with $S^1\times\ast$.  Then $Y\cup Z\simeq S^1\vee S^2$ is not aspherical.  Are there any additional conditions in the situation you care about that fail for this example?


text:
\subsection{Connection to average-case learning complexity}\label{subsec: connection to learning}
In this subsection, we consider learning a convex polytope via halfspace queries in absence of a teacher. We consider both the passive learning setting where learner makes \emph{i.i.d.} queries and the active learning setting with actively chosen queries, and provide sample complexity results accordingly.

\paragraph{Learning convex polytopes via halfspace queries} Consider the hyperplane set $\Hnd$ in $\Rd$ and a target region $r^* \in \regionset$. For any hyperplane $h \in \Hnd$
where $h = \condcurlybracket{\h{}}{\eta_h \cdot \h{}= b_h,\: \h{}\in \mathbb{R}^d}$, the labeling function $\ell_{r^*}$, as defined in \secref{sec:formulation}, specifies its label (halfspace) as $\ell_{r^*}(h) = $ $\mathrm{sgn}\parenb{\eta_h \cdot r^*- b_h}$ .
The problem of learning a region $r^*$ therefore reduces to identifying the corresponding labeling function $\ell_{r^*}$.
The objective here is to learn the region by querying the reference
of the form
    $q_{h}:= \mathbf{1}\curlybracket{\ell_{r^*}(h) = 1}$,
where $h \in \Hnd$ and $\mathbf{1}\curlybracket{\cdot}$ is the indicator function.
Similar to the teaching setting, we assume that $\rgn^*$ is sampled uniformly at random.
In the following, we show sample complexity results, i.e., on the minimal number of halfspace queries required to determine a target region , under the settings of \tt{active} and \tt{passive} learning. Specifically, we come up with a query selection procedure to achieve a tight bound for active learning as shown in \iftoggle{longversion}{\appref{appendix: active learning}}{the supplemental materials}.

\begin{theorem}\label{pairwise teaching bound}
Assume $\rgn$ $\sim$ $\mathcal{U}$ and that the underlying hyperplane arrangement of $\Hnd$ is in $d'$-relaxed general position.
Then, the average-case query complexity for actively learning a convex polytope is $\bigTheta{d'\log n}$,
and the worst-case query complexity is $\bigTheta{n}$.
\end{theorem}

In \emph{passive learning} setting,
the \tt{average} sample complexity is trivially lower bounded by $\bigOmega{n}$ since the learner gets a label uniformly at random. Thus, on average it requires $n$ samples to reconstruct the labels for all the halfspaces corresponding to the enclosing hyperplanes. Since there are $n$ hyperplanes $n$ samplings are sufficient to get all the labels which trivially give a $\cO(n)$ solution. Thus, it is not difficult to see that in the case of passive learning the average sample complexity is $\bigTheta{n}$.
\looseness -1

\begin{wrapfigure}{r}{0.16\textwidth}
\vspace{-10mm}
\centering
	\begin{subfigure}[b]{3pt}
	   \centering
		\includegraphics[width=.8\linewidth]{fig/3general.pdf}
		\vspace{-1mm}
		\caption{general}
		\label{fig:example.3general}
	\end{subfigure}
	\begin{subfigure}[b]{3pt}
	    \centering
		\includegraphics[width=.8\linewidth]{fig/2general.pdf}
		\vspace{-1mm}
		\caption{2-relaxed}
		\label{fig:example.2general}
	\end{subfigure}
	\begin{subfigure}[b]{3pt}
	    \centering
		\includegraphics[width=.8\linewidth]{fig/1general.pdf}
		\vspace{-1mm}
		\caption{1-relaxed}
		\label{fig:example.1general}
	\end{subfigure}
	\vspace{-6mm}
	\caption{relaxed general position}\label{fig:illu-relaxed-general}
\vspace{-8mm}
\end{wrapfigure}

config: arxiv


TITLE: Associator of the "dual" monoidal structure of a Grothendieck--Verdier Category
QUESTION [2 upvotes]: In A duality formalism in the spirit of Grothendieck and Verdier, Boyarchenko and Drinfeld consider a monoidal category $(\mathcal{M}, \otimes, \mathbf{1})$ together with an object $K \in \mathcal{M}$ such that there is an equivalence $D \colon \mathcal{M}^\mathrm{op} \to \mathcal{M}$ where for all $Y \in \mathcal{M}$ the functor $\operatorname{Hom}((-) \otimes Y, K)$ is representable by $DY$.
In this setup they define a new product via $X \odot Y := D^{-1}(DY \otimes DX)$ and claim that this defines a monoidal structure on $\mathcal{M}$. I fail to see what the associator morphism $$D^{-1}(DZ \otimes D(D^{-1}(DY \otimes DX))) \to  D^{-1}( D(D^{-1}(DZ \otimes DY)) \otimes DX)$$ should be. How can one construct such a morphism?
Edit: I was missing a $D$ in the domain and codomain. With the correct domain and codomain, one can get an evident associator using that $D^{-1}D \cong \mathrm{Id}$ (cf. the answer of HeinrichD).

REPLY [2 votes]: Let $F : \mathcal{C} \to \mathcal{D}$ be an equivalence of categories and $(\mathcal{D},\otimes,1)$ be a monoidal structure on $\mathcal{D}$. Then we have an induced monoidal structure on $\mathcal{C}\,$: Choose a quasi-inverse $F^{-1} : \mathcal{D} \to \mathcal{C}$ and isomorphisms $\mathrm{id}_{\mathcal{C}} \cong F^{-1} \circ F$, $\mathrm{id}_{\mathcal{D}} \cong F \circ F^{-1}$ satisfying the triangle identities. For $x,y \in \mathcal{C}$ we define $x \otimes y := F^{-1}(F(x) \otimes F(y))$. Hence, there is an isomorphism $F(x \otimes y) \cong F(x) \otimes F(y)$. We also let $1 := F^{-1}(1)$. The associator is defined by
$$x \otimes (y \otimes z) = F^{-1}(F(x) \otimes F(y \otimes z)) \cong F^{-1}(F(x) \otimes (F(y) \otimes F(z)))$$
$$ \cong F^{-1}((F(x) \otimes F(y)) \otimes F(z)) \cong F^{-1}(F(x \otimes y) \otimes F(z)) = (x \otimes y) \otimes z.$$


TITLE: Homomorphisms vs Functors
QUESTION [13 upvotes]: What really is the difference between a Homomorphism between categories and a Functor? I understand that they are both structure preserving mapping of the objects and arrows between the categories or am i missing something ?

REPLY [8 votes]: If I understand your question and definitions correctly: no, a homomorphism of categories and a functor are not the same thing.
Your definition of "homomorphism of categories" seems to be: given categories $M$ and $N$, a homomorphism $h:M\to N$ is

a mapping from $\mathsf{ob}(M)$ to $\mathsf{ob}(N)$, together with
for every $x,y\in\mathsf{ob}(M)$, a mapping from $\mathrm{Hom}_M(x,y)$ to $\mathrm{Hom}_N(h(x),h(y))$ such that $$h(a\circ b)=h(a)\circ h(b)$$ for all $a,b\in \mathrm{Hom}_M(x,y)$.

A functor is then a homomorphism of categories that satisfies the additional requirement that

$h(\mathrm{id}_x)=\mathrm{id}_{h(x)}$ for all $x\in\mathsf{ob}(M)$.

Thus, being a functor is a strictly stronger property than being a homomorphism of categories. For example, let $M$ be the category with

$\mathsf{ob}(M)=\{x,y\}$
$\mathrm{Hom}_M(x,x)=\{\mathrm{id}_x\},\quad \mathrm{Hom}_M(x,y)=\{a\}, \quad \mathrm{Hom}_M(y,x)=\varnothing,\quad \mathrm{Hom}_M(y,y)=\{\mathrm{id}_y\}$

and let $N$ be the category with

$\mathsf{ob}(N)=\{z\}$
$\mathrm{Hom}_N(z,z)=\{\mathrm{id}_z,c\}$ where $c\circ c=c$.

Then the homomorphism of categories $h:M\to N$ defined by

$h(x)=z,\quad h(y)=z$
$h(\mathrm{id}_x)=c,\quad h(a)=c,\quad h(\mathrm{id}_y)=c$

is not a functor.