Recursive-combinatorial properties of subsets of the natural numbers (Q803118)

Seven families of subsets of \({\mathbb{N}}\) are considered with respect to m-, tt- and \(\ell\)-reducibilities and two theorems are proved on the relations among those families. A recursive function f is called selective if \((\forall x_ 1,...,x_ n)(f(x_ 1,...,x_ n)\in \{x_ 1,...,x_ n\}).\) Let \(A\subseteq {\mathbb{N}}\) and \(\beta\not\equiv 0,1\) be an n-ary Boolean function. A is called \(\beta\)-selective if there is an n-ary selective recursive function f such that \((\forall x_ 1,...,x_ n)(f(x_ 1,...,x_ n)\in A\leftrightarrow \beta (\chi_ A(x_ 1),...,\chi_ A(x_ n))=1).\) The Boolean function \(\beta\not\equiv 0,1\) is called admissible if there is a \(\beta\)-selective set \(A\neq \emptyset,{\mathbb{N}}\). The following theorem is proved. If \(\beta \not\equiv x_ 1\) is an admissible function, then the family of \(\beta\)-selective sets coincides either with the family of recursive sets or with the family of semirecursive sets.