Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-25T02:59:52.112Z Has data issue: false hasContentIssue false
  • English
  • Français

On the T-degrees of partial functions

Published online by Cambridge University Press:  12 March 2014

Paolo Casalegno
Paolo Casalegno*
Affiliation:
Dipartimento di F1Losofia, Università di Pisa, 56100 Pisa, Italy
Get access Rights & Permissions [Opens in a new window]

Abstract

Let 〈, ≤ 〉 be the usual structure of the degrees of unsolvability and 〈, ≤ 〉 the structure of the T-degrees of partial functions defined in [7]. We prove that every countable distributive lattice with a least element can be isomorphically embedded as an initial segment of 〈, ≤ 〉: as a corollary, the first order theory of 〈, ≤ 〉 is recursively isomorphic to that of 〈, ≤ 〉. We also show that 〈, ≤ 〉 and 〈, ≤ 〉 are not elementarily equivalent.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 50 , Issue 3 , September 1985 , pp. 580 - 588
Copyright
Copyright © Association for Symbolic Logic 1985

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]Cooper, S. B., Partial degrees and the density problem. I, II, this Journal, vol. 47 (1982), pp. 854–859; vol. 49 (1984), pp. 503-513.Google Scholar
[2]Epstein, R. L., Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer-Verlag, Berlin, 1979.CrossRefGoogle Scholar
[3]Grätzer, G., Lattice theory, Freeman, San Francisco, California, 1971.Google Scholar
[4]Nerode, A. and Shore, R. A., Second order logic and first order theories of reducibility orderings, The Kleene symposium (Barwise, J., Keisler, J and Kunen, K., editors), North-Holland, Amsterdam, 1980, pp. 181–200.CrossRefGoogle Scholar
[5]Sasso, L., Degrees of unsolvability of partial functions, Ph.D. Thesis, University of California, Berkeley, California, 1971.Google Scholar
[6]Sasso, L., A minimal partial degree ≤ 0′, Proceedings of the American Mathematical Society, vol. 38 (1973), pp. 388–392.Google Scholar
[7]Sasso, L., A survey of partial degrees, this Journal, vol. 40 (1975), pp. 130–140.Google Scholar