Exercise 1.3.31

Let be the category of finite sets with bijections. We'll define two functors . First, define .

Xf : X \rightarrow Y\Sym(f) : \Sym(X) \rightarrow \Sym(Y)\Sym(f)(\sigma) = f \circ \sigma \circ f^{-1}$$.

Now, define .

is the set of total orders on -- for concreteness, let the elements of be relations in the sense of subsets of . Suppose is a bijection. Define by .

Theorem: There is no natural transformation .

Proof: Assume there were such a natural transformation . Let . And let be the swapping permutation and . Then, we have a component and by naturality . But, observe that:</script>

(\alpha_A \circ \Sym(s))(1_A) = \alpha_A(s \circ 1_A \circ s^{-1}) = \alpha_A(1_A)

(\Ord(s) \circ \alpha_A)(1_A) = \Ord(s)(R) = \setbuilder{(s(x), s(y))}{(x,y) \in R}

R$$, a contradiction.

Thus, since and are the same size as sets, there is a bijection between them and we have in for each , but not naturally. That is to say, and are not naturally isomorphic. This is a counterexample to the incorrect "converse" one might be willing to draw from exercise 1.3.26.