Exponential of monoid sets ($B^A\cong {\mathrm{Hom}}_M(M\times A,B)$)

For left M-sets, $B^A$ consists of equivariant maps of monoid sets $M\times A\to B$ for the diagonal action on the domain. Its action is $(m\cdot f)(w,a)=f(wm,a)$ and evaluation is $f(1,a)$. The curry of an equivariant $h:C\times A\to B$ is $\hat{h}(c)(w,a)=h(w\cdot c,a)$. This construction can have noninjective action maps even when both $A$ and $B$ are decidable.

For the free monoid on $x,y$, act on $\mathbb{N}$ by adding word length and on $\{0,1\}$ trivially. Both actions are injective. The equivariant function $f(w,n)$ indicating words of length strictly greater than $n$ ending in $x$ is nonzero, but $y\cdot f=0$. Thus the exponential of monoid sets is not decidable. Strict inequality ensures invariance when the original word is empty.

If each $m$ admits $p,q$ with $pmq=p$, then $B^A$ is decidable whenever the left M-set $B$ is. For equivariant $f,g$, equality of all values at $(1,a)$ implies equality at $(m,a)$: apply $p$ and use $f(pm,pa)=pm\cdot f(1,qa)$, then cancel the injective action of $p$ on $B$. Equality after the exponential action of $m$ then gives equal traces by cancelling its action on $B$.