Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The family of all recursively enumerable classes of finite sets


Author: T. G. McLaughlin
Journal: Trans. Amer. Math. Soc. 155 (1971), 127-136
MSC: Primary 02.70
DOI: https://doi.org/10.1090/S0002-9947-1971-0276084-7
MathSciNet review: 0276084
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that if $ P(x)$ is any first-order arithmetical predicate which enumerates the family Fin of all r.e. classes of finite sets, then $ P(x)$ must reside in a level of the Kleene hierarchy at least as high as $ \prod _3^0 - \Sigma _3^0$. (It is more easily established that some of the predicates $ P(x)$ which enumerate Fin do lie in $ \prod _3^0 - \Sigma _3^0$.)


References [Enhancements On Off] (What's this?)

  • [1] K. I. Appel and T. G. McLaughlin, On properties of regressive sets, Trans. Amer. Math. Soc. 115 (1965), 83-93. MR 37 #6176. MR 0230616 (37:6176)
  • [2] J. C. E. Dekker, Infinite series of isols, Proc. Sympos. Pure Math., vol. 5, Amer. Math. Soc., Providence, R. I., 1962, pp. 77-96. MR 26 #16. MR 0142447 (26:16)
  • [3] J. C. E. Dekker and J. R. Myhill, Some theorems on classes of recursively enumerable sets, Trans. Amer. Math. Soc. 89 (1958), 25-59. MR 20 #3780. MR 0097310 (20:3780)
  • [4] S. C. Kleene, Introduction to metamathematics, Van Nostrand, Princeton, N. J., 1952. MR 14, 525. MR 0051790 (14:525m)
  • [5] M. B. Pour-El and H. Putnam, Recursively enumerable classes and their application to recursive sequences of formal theories, Arch. Math. Logik Grundlagenforsch. 8 (1965), 104-121. MR 34 #7370. MR 0207555 (34:7370)
  • [6] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [7] C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331-345. MR 26 #3598. MR 0146072 (26:3598)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02.70

Retrieve articles in all journals with MSC: 02.70


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1971-0276084-7
Keywords: Recursively enumerable class of finite sets, Kleene hierarchy, $ \Sigma _n^0$-enumerability, $ \Sigma _n^0$-productivity
Article copyright: © Copyright 1971 American Mathematical Society

American Mathematical Society