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\]
\[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.