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!