Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 74 / 4 / Solution

The two introductory requests can be settled before the lettered applications. In the functor category $[C,\mathbf{Set}]$, finite limits and finite unions of subobjects are pointwise. The component of the diagonal at $c$ is ordinary equality on $F(c)$. Its only possible complement isThis forms a subfunctor exactly when each $F(u)$ sends unequal elements to unequal elements, equivalently when every $F(u)$ is injective. In that case $D$ and the diagonal are disjoint and their union is $F^2$ at every component. Conversely, a diagonal complement must have these components and be stable under every transition map. Hence $F$ is decidable exactly when every transition map is injective.

Regard a monoid $M$ as a one-object category; a covariant set-valued functor is a left M-set. Give $M\times A$ the diagonal left action $t\cdot (w,a)=(tw,t\cdot a)$. LetRight multiplication on the first coordinate commutes with the diagonal left action, so $m\cdot f$ remains equivariant. The formula obeys $m\cdot (n\cdot f)=(mn)\cdot f$ and $1\cdot f=f$. Evaluation isIt is equivariant because $\mathrm{ev}(m\cdot f,m\cdot a)=f(m,m\cdot a)=m\cdot f(1,a)$.

For an equivariant $h:C\times A\to B$, defineThis is equivariant in $(w,a)$, and $\hat{h}(m\cdot c)=m\cdot \hat{h}(c)$. Evaluation recovers $h$. Conversely, currying the evaluation of a map $C\to E$ recovers that map by its equivariance. This proves the exponential universal property and the natural identificationwith exactly the stated action. In particular, decidability in a set-valued functor category says that a left M-set is decidable if and only if each of its action maps is injective.