We define a class of so-called ∑-sets as a natural closure of recursively enumerable sets Wn under the relation “∈” and study its properties.

Let N, O and S denote the set of nonnegative integers, the graph of the constant 0 function and the graph of the successor function respectively. For sets $P, Q, R \subseteq N^2$ operations of transposition, composition, and bracketing are defined as follows: $P^\cup = \{\langle x, y\rangle | \langle y, x\rangle \epsilon P\}, PQ = \{\langle x, z\rangle| \exists y\langle x, y\rangle \epsilon P & \langle y, z\rangle \epsilon Q\}$ , and [ P, Q, R] = ∪n ε M(PnQR (...) n). THEOREM. The class of recursively enumerable subsets of N2 is the smallest class of sets with O and S as members and closed under transposition, composition, and bracketing. This result is derived from a characterization by Julia Robinson of the class of general recursive functions of one variable in terms of function composition and "definition by general recursion." A key step in the proof is to show that if a function F is defined by general recursion from functions A, M, P and R then F = [ P∪, A∪ M, R]. The above definitions of the transposition, composition, and bracketing operations on subsets of N2 can be generalized to subsets of X2 for an arbitrary set X. In this abstract setting it is possible to show that the bracket operation can be defined in terms of K, L, transposition, composition, intersection, and reflexive transitive closure where K: X → X and L: X → X are functions for decoding pairs. (shrink)

A splitting A1A2 = 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. (shrink)

We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of (...) class='Hi'>recursively enumerable sets with inclusion. We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions. (shrink)

Chapter 1: Introduction. S = <{We}c<w; C,U,n,0,w> is the substructure formed by restricting the lattice <^P(w); C , U, n,0,w> to the re subsets We of the ...

A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the (...) degrees of r.e. splittings and the degree splittings of a set. We say a setAhas thestrong universal splitting property if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for degA=b∪cthere is an r.e. splittingB, CofAsuch that degB=band degC=c. The goal of this paper is the study of this splitting property.In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP. (shrink)

It will be shown that in the lattice of recursively enumerable sets one can define elementarily with parameters a structure isomorphic to (∑ 0 4 , ∑ 0 3 ), i.e. isomorphic to the lattice of ∑ 0 4 sets together with a unary predicate selecting out exactly the ∑ 0 3 sets.

Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove (...) that there are no deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turning functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that $(W \bigoplus A)'$ is forced to disagree with Φ(-; A'). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a "moderately" deep degree: There is a low nonzero degree whose join with any other low degree is not high. (shrink)

I introduce an effective enumeration of all effective enumerations of classes of r. e. sets and define with this the index set IE of injectively enumerable classes. It is easy to see that this set is ∑5 in the Arithmetical Hierarchy and I describe a proof for the ∑5-hardness of IE.