Lattice embeddings for abstract bounded reducibilities (Q2784495)

The author starts with the definition of a bounded reducibility of subsets of the natural numbers. A relation \(\leq_r\) is a bounded reducibility iff there exists a recursive set \(E\) that contains only indices of total recursive functionals such that for all sets \(A,B\) we have \(A \leq_e B \iff \exists e \in E (A = \Phi_e(B))\). This concept of bounded reducibility comprises most of the resource-bounded reducibilities (including time- or space-bounded reducibilities). NEWLINENEWLINENEWLINEIn the central part of the paper some axioms (conditions) are introduced which give us as a final result the notion of a standard reducibility. These axioms are satisfied for most of reducibilities appearing in the literature. NEWLINENEWLINENEWLINEThen some additional lemmas are proved. As the main theorem the author proves the following statement: For standard reducibilities every countable distributive lattice can be embedded into a proper interval of the structure induced on the recursive sets.