×

A representation of recursively enumerable sets through Horn formulas in higher recursion theory. (English) Zbl 1389.03008

In the late 1950’s, R. Smullyan showed: the r.e. (recursively enumerable) sets are exactly those that are representable in his elementary formal systems. This is a result in ordinary recursion theory in arithmetical setting. The authors of this article extend it to other recursion theories in set-theoretic setting: primitive set recursion, \(\beta\)-recursion, and recursion in admissible structures. First, they give careful definitions of r.e. sets and Horn clause theories (modern reformulation of elementary formal systems) in set-theoretic context. Also, succinct definitions of recursion theories in question are given. The direction of an r.e. set is representable is proved inductively following how that set is constructed. The proof of the other implication uses the fact that local satisfaction relation is definable. In the last section, the authors look at Smullyan’s result from the set-theoretic view-point, utilizing the equivalence of the system of natural numbers and the system of hereditarily finite sets.

MSC:

03C70 Logic on admissible sets
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03D65 Higher-type and set recursion theory
03E45 Inner models, including constructibility, ordinal definability, and core models
03D75 Abstract and axiomatic computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Barwise, Infinitary logic and admissible sets. J. Symb. Logic 34(2), 226–252 (1969) · Zbl 0215.31806 · doi:10.2307/2271099
[2] J. Barwise, Admissible Sets and Structures (Springer, Berlin, 1975) · Zbl 0316.02047
[3] K. Devlin, Constructibility (Springer, Berlin, 1984)
[4] K. Doets, From Logic to Logic Programming (MIT Press, Cambridge, 1994) · Zbl 0834.68007
[5] M. Fitting, Fundamentals of Generalized Recursion Theory (North Holland, Amsterdam, 1981) · Zbl 0597.03028
[6] M. Fitting, Incompletness in the Land of Sets (College Publications, London, 2007) · Zbl 1152.03003
[7] S. Friedman, \(\beta \) {\(\beta\)} -Recursion theory. Trans. Am. Math. Soc. 255, 173–200 (1979)
[8] J. Hamkins, A. Lewis, Infinite time turing machines. J. Symb. Logic 65(2), 567–604 (2000) · Zbl 0963.03064 · doi:10.2307/2586556
[9] W. Hodges, Logical Features of Horn Clauses, in Handbook of Logic in Artificial Intelligence and Logic Programming, ed. by D. Gabbay, C. Hogger, J. Robinson (Clarendon Press, Oxford, 1993), pp. 449–503
[10] R.B. Jensen, C. Karp, Primitive Recursive Set Functions, in In Axiomatic Set Theory: Proc. Symp. Pure Math, ed. by D. Scott (American Mathematical Society, Providence, 1971), pp. 143–167
[11] R.B. Jensen, The fine structure of the constructible hierarchy. Ann. Math. Logic 4, 229–308 (1972) · Zbl 0257.02035 · doi:10.1016/0003-4843(72)90001-0
[12] Jensen, R. B. Subcomplete Forcing and \(L\) L -forcing, Lectures given at the All Summer Scholl in Singapore (2012). Available in http://www.mathematik.hu-berlin.de/ raesch/org/jensen/pdf/Singapore_Lectures_final_version
[13] Koepke, P. \(\alpha \) {\(\alpha\)} -Recursion Theory and Ordinal Computability, preprint. Available in http://www.math.uni-bonn.de/people/koepke/preprints.shtml
[14] P. Koepke, B. Seyffert, Ordinal machines and admissible recursion theory. Ann. Pure Appl. Logic 160(3), 310–318 (2009) · Zbl 1178.03061 · doi:10.1016/j.apal.2009.01.005
[15] K. Kunen, The Fundations of Mathematics (College Publications, London, 2009)
[16] A. Nerode, R. Shore, Logic for Applications, 2nd edn. (Springer, Berlin, 1997) · Zbl 0874.03004
[17] G. Sacks, Higher Recursion Theory (Springer, Berlin, 1993) · Zbl 0716.03043
[18] R. Schindler, M. Zeman, Fine Structure, in In Handbook of Set Theory, ed. by M. Foreman, A. Kanamori (Springer, Berlin, 2010)
[19] R. Smullyan, Theory of Formal Systems, Rev. edn. (Princeton University Press, Princeton, 1961)
[20] R.I. Soare, Recursively Enumerable Sets and Degrees (Springer, Berlin, 1987) · Zbl 0667.03030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.