I've been reading through Leinster's Basic Category Theory and building up an intuition for natural transformations. When I encountered the definition of a natural isomorphism between functors, I found I couldn't imagine a scenario where two functors were isomorphic but not naturally so.
Luckily, Exercise 1.3.31 (page 39) gives us such an example to work through, and this post is my attempt (with much guidance from Teo Fields Collin) at working through it rigorously.
(We use $\text{Sym}(X)$ to denote permutations, because the group of all permutations of a set $X$ is called the symmetric group of $X$.)
As stated in the prompt, our first task is to give a functorial interpretation of the set of permutations $\text{Sym}(X)$ with respect to source category $\mathscr{B}$ and destination category $\text{Set}$, then do the same for the set of total orders $\text{Ord}(X)$.
What do permutations look like in $\mathscr{B}$? We can reason through this directly from the definition of permutation above. All morphisms in $\mathscr{B}$ are bijections, so the set of permutations for an object $X \in \mathscr{B}$ is simply the collection of its endomorphisms (i.e., the morphisms that start in $X$ and end in $X$).
In defining $\text{Sym}$ as a functor, we might consider the inclusion functor $\mathscr{B} \hookrightarrow \text{Set}$, since $\mathscr{B}$ is a subcategory of $\text{Set}$. That is, we define $\text{Sym}(X) \coloneqq X$ for $X \in \mathscr{B}$, and we define $\text{Sym}(f) \coloneqq f$ for $f \in \mathscr{B}(X, Y)$.
Encoding $\text{Ord}$ as a functor isn't quite as obvious. In terms of sets, an order on $X$ is a binary relation $\leq$ on $X$, which is a subset of $X \times X$—for example, the order $[1, 2, 3]$ would be encoded as $\{(1, 2), (1, 3), (2, 3) \}$. So we can't consider the inclusion of $\mathscr{B}$ into $\text{Set}$.
If we look more carefully at the problem statement, we're essentially given the definition of $\text{Sym}$ and $\text{Ord}$ on objects. $\text{Sym}(X)$ will map $X$ to the set of all bijections $X \to X$, and $\text{Ord}(X)$ will map $X$ to the set of all total orders on $X$. Our job then is to define the mapping of morphisms. We start with $\text{Sym}$.
Let's start by seeing the type signature of this mapping. For each morphism $\mathscr{B} \ni f : X \to Y$, we must map it to a morphism $\text{Set} \ni \text{Sym}(f) : \text{Sym}(X) \to \text{Sym}(Y)$. Note that elements of $\text{Sym}(X)$ have type $X \to X$, so we must lift $f$ to act on permutations of type $X \to X$, instead of objects of type $X$, and produce permutations of type $Y \to Y$, instead of objects of type $Y$. That is, we must produce a function of type $(X \to X) \to (Y \to Y)$, given a function of type $X \to Y$.
Suppose we have a permutation $\sigma : X \to X$. Our goal then is to produce a term of type $Y \to Y$.
Thinking about the case where $X = Y$ provides some insight, because $f$ is now a permutation. How do we apply a permutation $f$ to a set of permutations $\text{Sym}(X)$? We can do so pointwise! That is, for each $\sigma \in \text{Sym}(X)$, we compose $f$ with it to obtain a new permutation $\sigma ; f$.
What about when $X \neq Y$? We still know $f$ is a bijection, so in some sense, $X$ and $Y$ are the same set, but the composition $\sigma ; f$ now has type $X \to Y$. How can we use $\sigma$, which acts on elements of $X$, to obtain a permutation on elements of $Y$, which is "equivalent" with respect to $f$? For example, if we have $X = \{1, 2, 3, 4\}, Y = \{a, b, c, d\}, f = \{(1, a), (2, b), (3, c), (4, d)\}$, and
$$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{pmatrix}, $$