Degrees of difficulty of generalized r.e. separating classes

Important examples of classes of functions are the classes of sets (elements of ^ω 2) which separate a given pair of disjoint r.e. sets: . A wider class consists of the classes of functions f ∈ ^ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let denote the Medvedev degrees of those such that no m + 1 sets among A ₀,...,A _k-1 have a nonempty intersection. It is shown that each is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions is the greatest element of . If 2 ≤ l < k, then 0 _M is the only degree in which is below a member of . Each is densely ordered and has the splitting property and the same holds for the lattice it generates. The elements of are exactly the joins of elements of for . Supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.