A note on recursively enumerable classes of partial recursive functions

Abstract

We prove that every recursively enumerable class of partial recursive functions with infinite domains must have a recursive witness array. The result gives a powerful method for proving properties of recursively enumerable classes. We show for example that no finitely generated group of recursive permutations can contain all recursive involutions, and neither can it contain all cycle-free recursive permutations.