A new notion of simplicity
for recursively enumerable (r.e.) sets is introduced, that of d-simplicity or simplicity
with respect to arrays of differences of r.e. sets (d.r.e. sets). This notion arose from
the method used to generate automorphisms of ℰ∗, the lattice of r.e. sets
modulo finite sets, and is a further step toward finding a complete set of
invariants for the automorphism types of ℰ∗. The d-simple sets are closely
related to the small sets defined by Lachlan as a key part of his decision
procedure for the ∀∃-theory of ℰ∗. Finally, the degrees D of d-simple sets
form a new invariant class of r.e. degrees, since H1⊆ D but D splits L1
(where H1 and L1 are the high and low r.e. degrees respectively). This refutes
conjectures of Martin and Shoenfield which imply that degrees C of any
class of r.e. sets invariant under automorphisms of ℰ can be characterized
by a finite set of equalities or inequalities involving the jump of degrees in
C.
