Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Logic and Foundations
Splitting Theorems In Recursion Theory, Rod G. Downey, Michael Stob
Splitting Theorems In Recursion Theory, Rod G. Downey, Michael Stob
University Faculty Publications and Creative Works
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 (since A1 ≤T A, A2 ≤T A and A ≤T A1 ⊕ A2). Thus splitting theor ems have been used to obtain results about the structure of ε, the structure …
Friedberg Splittings Of Recursively Enumerable Sets, Rod G. Downey, Michael Stob
Friedberg Splittings Of Recursively Enumerable Sets, Rod G. Downey, Michael Stob
University Faculty Publications and Creative Works
A splitting A1{square cup}A2 = A of an r.e. set A is called a Friedberg splitting if for any r.e. set W with W - A not r.e., W - Ai≠0 for i = 1,2. In an earlier paper, the authors investigated Friedberg splittings of maximal sets and showed that they formed an orbit with very interesting degree-theoretical properties. In the present paper we continue our investigations, this time analyzing Friedberg splittings and in particular their orbits and degrees for various classes of r.e. sets.