Splitting theorems in recursion theory

Annals of Pure and Applied Logic 65 (1):1-106 (1993)
  Copy   BIBTEX


A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory



    Upload a copy of this work     Papers currently archived: 92,323

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Recursion theory for metamathematics.Raymond Merrill Smullyan - 1993 - New York: Oxford University Press.
Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
Splitting theorems and the jump operator.R. G. Downey & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 94 (1-3):45-52.
Ray-Splitting Billiards.R. Blümel, P. M. Koch & L. Sirko - 2001 - Foundations of Physics 31 (2):269-281.
Analytic countably splitting families.Otmar Spinas - 2004 - Journal of Symbolic Logic 69 (1):101-117.
A theory of rules for enumerated classes of functions.Andreas Schlüter - 1995 - Archive for Mathematical Logic 34 (1):47-63.
Recursion theory.Anil Nerode & Richard A. Shore (eds.) - 1985 - Providence, R.I.: American Mathematical Society.
Generalized recursion theory.Jens Erik Fenstad & Peter G. Hinman (eds.) - 1974 - New York,: American Elsevier Pub. Co..
Canonical Forms and Hierarchies in Generalized Recursion Theory.Phokion G. Kolaitis - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion theory. Providence, R.I.: American Mathematical Society. pp. 42--139.
Axiomatic recursion theory and the continuous functionals.Simon Thompson - 1985 - Journal of Symbolic Logic 50 (2):442-450.


Added to PP

28 (#573,323)

6 months
12 (#220,957)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Some properties of r-maximal sets and Q 1,N -reducibility.R. Sh Omanadze - 2015 - Archive for Mathematical Logic 54 (7-8):941-959.
Some orbits for E.Peter Cholak, Rod Downey & Eberhard Herrmann - 2001 - Annals of Pure and Applied Logic 107 (1-3):193-226.

View all 17 citations / Add more citations