Medvedev Degrees of Generalized R.E. separating Classes

Important examples of classes of functions are the classes of sets (elements of ) which separate a given pair of disjoint r.e. sets: . A wider class consists of the classes of functions 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 Sk(A0,…,Ak−1) such that no m+1 sets among A0,…,Ak−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 DNRk is the greatest element of . If 2≤l