The family of all recursively enumerable classes of finite sets

McLaughlin, T. G.

doi:10.1090/S0002-9947-1971-0276084-7

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