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

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.

A decidable $B$ has injective action maps. First prove that evaluation at $1$ distinguishes equivariant functions. Suppose $f(1,a)=g(1,a)$ for every $a$. Fix $m\in M$ and choose $p,q$ with $pmq=p$. For each $a$, equivariance givesThe same equation holds for $g$, so these values agree. Cancel the injective action of $p$ on $B$ to obtain $f(m,a)=g(m,a)$. Hence $f=g$. This proves the hinted contrapositive and, more precisely, injectivity of the trace map $f\mapsto (a\mapsto f(1,a))$.

Now suppose $m\cdot f=m\cdot g$ in the exponential. Evaluating this equality at $(1,m\cdot a)$ givesCancel the action of $m$ on $B$. The trace maps agree, so the preceding argument gives $f=g$. Every action map on $B^A$ is therefore injective. By the introductory criterion, $B^A$ is decidable whenever $B$ is under the specified monoid condition. Neither cancellation in $M$ nor injectivity of its action on $A$ is assumed.

For the free monoid on $x,y$, use the functionThe strict inequality is important. For any prefix $v$, $|vw|>|v|+n$ is equivalent to $|w|>n$. Whenever it holds, $w$ is nonempty and prefixing $v$ does not change its final letter. When it fails, both values are zero. Thuswhich proves equivariance for the diagonal action on $M\times \mathbb{N}$ and the trivial action on $B$. Hence $f$ is an element of the exponential described above. Let $g$ be the constant-zero equivariant function. They differ at $(x,0)$.

But every word $wy$ ends in $y$, sofor every $w,n$. The action of $y$ on $B^A$ is not injective, and $B^A$ is not decidable, even though $B$ is decidable. This is a nondecidable exponential of decidable monoid sets. The monoid condition in part (a) also fails here: $|pmq|=|p|+|m|+|q|$ cannot equal $|p|$ for a nonempty word $m$.