The family of all recursively enumerable classes of finite sets
HTML articles powered by AMS MathViewer
- by T. G. McLaughlin PDF
- Trans. Amer. Math. Soc. 155 (1971), 127-136 Request permission
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
- K. I. Appel and T. G. McLaughlin, On properties of regressive sets, Trans. Amer. Math. Soc. 115 (1965), 83–93. MR 230616, DOI 10.1090/S0002-9947-1965-0230616-0
- J. C. E. Dekker, Infinite series of isols, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 77–96. MR 0142447
- J. C. E. Dekker and J. Myhill, Some theorems on classes of recursively enumerable sets, Trans. Amer. Math. Soc. 89 (1958), 25–59. MR 97310, DOI 10.1090/S0002-9947-1958-0097310-7
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- Marian Boykan Pour-El and Hilary Putnam, Recursively enumerable classes and their application to recursive sequences of formal theories, Arch. Math. Logik Grundlag. 8 (1965), 104–121 (1965). MR 207555, DOI 10.1007/BF01976264
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331–345. MR 146072, DOI 10.1002/malq.19620080313
Additional Information
- © Copyright 1971 American Mathematical Society
- 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