Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-22T14:48:38.507Z Has data issue: false hasContentIssue false
  • English
  • Français

The Role of True Finiteness in the Admissible Recursively Enumerable Degrees

Published online by Cambridge University Press:  15 January 2014

Noam Greenberg
Noam Greenberg*
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556, USA. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of α-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal α is effectively close to ω (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the α-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of α-r.e. degrees for various classes of admissible ordinals α. Together with coding work which shows that for some α, the theory of the α-r.e. degrees is complicated, we get that for every admissible ordinal α, the α-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 11 , Issue 3 , September 2005 , pp. 398 - 410
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Church, Alünzo, The constructive second number class, Bulletin of the American Mathematical Society, vol. 44 (1938), pp. 224–232.Google Scholar
[2] Church, Alonzo and Kleene, Stephen Cole, Formal definitions in the theory of ordinal numbers, Fundamenta Mathematicae, vol. 28 (1937), pp. 11–21.Google Scholar
[3] Downey, Rod and Shore, Richard A., Lattice embeddings below a nonlow2 recursively enumerable degree, Israel Journal of Mathematics, vol. 94 (1996), pp. 221–246.CrossRefGoogle Scholar
[4] Driscoll, Graham C. Jr, Metarecursively enumerable sets and their metadegrees, The Journal of Symbolic Logic, vol. 33 (1968), pp. 389–411.Google Scholar
[5] Friedman, Sy D., The Turing degrees and the metadegrees have isomorphic cones, Patras Logic Symposion (Patras, 1980), Studies in Logic and the Foundation of Mathematics, vol. 109, North-Holland, Amsterdam, 1982, pp. 145–157.CrossRefGoogle Scholar
[6] Gödel, Kurt Friedrich, Consistency-proof for the generalized continuum-hyphothesis, Proceedigs of the National Academy of Sciences, USA, vol. 25 (1939), pp. 220–224.CrossRefGoogle Scholar
[7] Greenberg, Noam, Shore, Richard A., and Slaman, Theodore A., The theory of the metarecursively enumerable degrees, submitted.Google Scholar
[8] Harrington, Leo and Shelah, Saharon, The undecidability of the recursively enumerable degrees, Bulletin of the American Mathematical Society, vol. 6 (1982), no. 1, pp. 79–80.Google Scholar
[9] Kleene, Stephen Cole, On notations for ordinal numbers, The Journal of Symbolic Logic, vol. 3 (1938), pp. 150–155.Google Scholar
[10] Kreisel, G., Set theoretic problems suggested by the notion of potential totality, Infinitistic methods (Proceedings of the Symposium on Foundations on Mathematics, Warsaw, 1959), Pergamon, Oxford, 1961, pp. 103–140.Google Scholar
[11] Kreisel, G. and Sacks, Gerald E., Metarecursive sets I, II (Abstracts), The Journal of Symbolic Logic, vol. 28 (1963), pp. 304–305.Google Scholar
[12] Kreisel, G. and Sacks, Gerald E., Metarecursive sets, The Journal of Symbolic Logic, vol. 30 (1965), pp. 318–338.Google Scholar
[13] Kripke, Saul, Transfinite recursion on admissible ordinals I, II (Abstracts), The Journal of Symbolic Logic, vol. 29 (1964), pp. 161–162.Google Scholar
[14] Lachlan, Alistair H., Embedding nondistributive latticesin the recursively enumerable degrees, Conference in Mathematical Logic - London '70 (Bedford College, London, 1970), Lecture Notes in Mathematics, vol. 255, Springer, Berlin, 1972, pp. 149–177.CrossRefGoogle Scholar
[15] Lachlan, Alistair H., A recursively enumerable degree which will not split over all lesser ones, Annals of Mathematical Logic, vol. 9 (1976), no. 4, pp. 307–365.Google Scholar
[16] Lerman, M., Maximal α-r.e. sets, Transactions of the American Mathematical Society, vol. 188 (1974), pp. 341–386.Google Scholar
[17] Lerman, M., A necessary and sufficient condition for embedding rankedfinite partial lattices into the computably enumerable degrees, Annals of Pure and Applied Logic, vol. 94 (1998), no. 1–3, pp. 143–180, Also, in Conference on Computability Theory (Oberwolfach, 1996).Google Scholar
[18] Lerman, M., Embedings into the computably enumerable degrees, Computability theory and its applications (Boulder, Colorando, 1999), Contemporary Mathematics, vol. 257, American Mathematical Society, Providence, RI, 2000, pp. 191–205.Google Scholar
[19] Lerman, M., A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees, Annals of Pure and Applied Logic, vol. 101 (2000), no. 2–3, pp. 275–297.CrossRefGoogle Scholar
[20] Lerman, M. and Sacks, Gerald E., Some minimal pairs of α-recursively enumerable degrees, Annals of Mathematical Logic, vol. 4 (1972), pp. 415–442.CrossRefGoogle Scholar
[21] Lerman, M. and Simpson, S. G., Maximal sets in α-recursion theory, Israel Journal of Mathematics, vol. 14 (1973), pp. 236–247.CrossRefGoogle Scholar
[22] Maass, Wolfgang, Inadmissibility, tame r.e. sets and the admissible collapse, Annals of Mathematical Logic, vol. 13 (1978), no. 2, pp. 149–170.Google Scholar
[23] Maass, Wolfgang, Recursively enumerable heneric sets, The Journal of Symbolic Logic, vol. 47 (1982), no. 4, pp. 809–823.Google Scholar
[24] Mytilinaios, Michael, Finite injury and Σ1-induction, The Journal of Symbolic Logic, vol. 54 (1989), no. 1,pp. 38–49.Google Scholar
[25] Nies, André, Shore, Richard A., and Slaman, Theodore A., Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society (3), vol. 77 (1998), no. 2, pp. 241–291.Google Scholar
[26] Odell, David, Trace constructions in α-recursion theory, Ph.D. thesis, Cornell University, Ithaca, New York, USA, 1983.Google Scholar
[27] Platek, Richard, Foundations of recursion theory, Ph.D. thesis, Stanford University, Stanford, California, USA, 1965.Google Scholar
[28] Sacks, G. E. and Simpson, S. G., The α-finite method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343–367.Google Scholar
[29] Sacks, Gerald E., Degrees of Unsolvability, Princeton University Press, Princeton, NJ, 1963.Google Scholar
[30] Sacks, Gerald E., Metarecursively enumerable sets and admissible ordinals, Bulletin of the American Mathematical Society, vol. 72 (1966), pp. 59–64.Google Scholar
[31] Sacks, Gerald E., Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990.Google Scholar
[32] Shinoda, Juichi and Slaman, Theodore A., On the theory of the PTIME degrees of the recursive sets, Journal of Computer and System Sciences, vol. 41 (1990), no. 3, pp. 321–366.Google Scholar
[33] Shore, Richard A., On the jump of an α-recursively enumerable set, Transactions of the American Mathematical Society, vol. 217 (1976), pp. 351–363.Google Scholar
[34] Shore, Richard A., The recursively enumerable α-degrees are dense, Annals of Mathematical Logic, vol. 9 (1976), no. 1–2, pp. 123–155.Google Scholar
[35] Shore, Richard A., On the ∀∃-sentences of α-recursion theory, Generalized Recursion Theory, II (Proceedings of the Second Symposium, University Oslo, Oslo, 1977), Studies in Logic and the Foundation of Mathematics, vol. 94, North-Holland, Amsterdam, 1978, pp. 331–353.Google Scholar
[36] Shore, Richard A., On homogeneity and definability in the first-order theory of the Turing degrees, The Journal of Symbolic Logic, vol. 47 (1982), no. 1, pp. 8–16.CrossRefGoogle Scholar
[37] Shore, Richard A., Conjectures and questions from Gerald Sachs's degrees of unsolvability, Archive of Mathematical Logic, vol. 36 (1997), no. 4–5, pp. 233–253, Also, in Sacks Symposium (Cambridge, MA, 1993).Google Scholar
[38] Shore, Richard A., The recursively enumerable degrees, Handbook of Computability Theory, Studies in Logic and the Foundation of Mathematics, vol. 140, North Holland, Amsterdam, 1999, pp. 169–197.CrossRefGoogle Scholar
[39] Slaman, Theodore A., Degree structures, Proceedings of the International Congress of Mathematicians, vol. I, II (Kyoto, 1990), Mathematical Society of Japan, Tokyo, 1991, pp. 303–316.Google Scholar
[40] Slaman, Theodore A. and Woodin, W. Hugh, Σ1-collection and the finite injury priority method, Mathematical logic and applications (Kyoto, 1987), Lecture Notes in Mathematics, vol. 1388, Springer, Berlin, 1989, pp. 178–188.Google Scholar
[41] Sukonick, J., Lower bounds for pairs of metarecursively enumerable degrees, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, 1969.Google Scholar
[42] Takeuti, Gaisi, On the recursive f unctions of ordinal numbers, Journal of the Mathematical Society of Japan, vol. 12 (1960), pp. 119–128.Google Scholar
[43] Takeuti, Gaisi, A formalization of the theory of ordinal numbers, The Journal of Symbolic Logic, vol. 30 (1965), pp. 295–317.Google Scholar