Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
MathSciNet review: 0276084
Full-text PDF Free Access

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?)


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: http://dx.doi.org/10.1090/S0002-9947-1971-0276084-7
PII: S 0002-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