THE CLASS OF REGULAR SETS IS PROPERLY CONTAINED IN THE CLASS OF PRIMITIVE RECURSIVE SETS.
IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Pagination or Media Count:
It was stated in Kleene that every regular set is a primitive recursive set. Since, however, regular sets are certain subsets of a finitely generated free semigroup, while primitive recursive sets are subsets of the natural numbers, the relationship between the two concepts is not obvious. In this paper an appropriate mapping into the natural numbers is introduced, allowing a straightforward proof of titled result. Author
- Theoretical Mathematics