Degrees of difficulty of generalized r.e. separating classes (Q926177): Difference between revisions

This paper presents results about Medvedev degrees of certain \(\Pi^0_1\) subclasses of \({^\omega\omega}\). For \(P,Q\subseteq{^\omega\omega}\), \(P\leq_MQ\) iff there is a partial recursive functional mapping \(Q\) into \(P\). The Medvedev degrees are the equivalence classes naturally generated. For \(1\leq m< k\), call \(P\) an \((m,k)\)-separating class if there are r.e. sets \(A_0,\dots, A_{k-1}\) no \(m+1\) of which have nonempty intersection and \(P= \{f\in{^\omega k}: f(x)\neq i\) when \(x\in A_i\}\). Let \(S^m_k\) be the collection of Medvedev degrees of \((m,k)\)-separating classes. The paper focuses on the compositions of these collections and how they vary with the indices \(k\) and \(m\). It is shown that each \(S^m_k\) is a densely ordered upper semilattice, but not a lattice, in which any countable partial ordering can be embedded.