Anindya wrote:
> from what I can make out, if \$$\phi\$$ is our bijection from \$$N\$$ to \$$M\$$, the naturality condition amounts to saying that for all \$$m\in M\$$ and all \$$y, n\in N\$$ we have \$$\phi(n\circ y\circ F(m)) = G(n)\circ\phi(y)\circ m\$$ – but I'm not sure what that entails!

I think you're on the right track! If we set \$$m=1_M\$$ and \$$y=1_N\$$, we get the equation
$\phi(n) = G(n)\circ \phi(1_N),$
so \$$\phi\$$ is completely determined by where it sends \$$1_N\$$. *It must be an invertible element of \$$M\$$ for \$$\phi\$$ to be a bijection, so* let's call that element \$$u_0\$$. Then we know that \$$\phi(n) = G(n)\circ u_0\$$, and the equation \$$\phi(n\circ y\circ F(m)) = G(n)\circ\phi(y)\circ m\$$ becomes
$G(n\circ y\circ F(m)) \circ u_0= G(n)\circ (G(y)\circ u_0) \circ m.$
This is true for all \$$n,y,m\$$ if and only if for all \$$m\in M\$$ we have
$G(F(m))\circ u_0 = u_0 \circ m$
*or*
$G(F(m)) = u_0 \circ m \circ u_0^{-1}.$
*So this means that \$$F\$$ and \$$G\$$ are bijections (and therefore isomorphisms) and they compose to conjugation by a unit. That does seem like a slightly more general version of being inverses!*

**Edit:** I've just realized that all we can deduce from the fact that \$$\phi(n) = G(n)\circ u_0\$$ is a bijection is that \$$u_0\$$ has a *left* inverse: \$$G\$$ of whatever \$$\phi\$$ sends to \$$1_M\$$. That makes the very last step to \$$u_0 \circ m \circ u_0^{-1}\$$ not work. (I'm too used to working with groups and commutative monoids!) But we *can* say instead that if \$$l_0\$$ is a left inverse to \$$u_0\$$, then
$l_0 \circ G(F(m)) \circ u_0 = m.$

So whatever composite \$$G\circ F\$$ is, it has to sort-of-conjugate to the identity.