Nondecidable exponential of decidable monoid sets
ID: nondecidable-exponential-of-decidable-monoid-sets
For the free monoid on , act on by adding word length and on trivially. Both actions are injective. The equivariant function indicating words of length strictly greater than ending in is nonzero, but . Thus the exponential of monoid sets is not decidable. Strict inequality ensures invariance when the original word is empty.
New to topics? Read the docs here!