Weak combinatorial-selective properties of subsets of the natural numbers. (Russian) Zbl 0727.03027

Let be \(A\subseteq {\mathbb{N}}=\{0,1,2,...\}\) and \(\beta\) be some n-ary Boolean function. Say that A is weak \(\beta\)-selective if there exists an n-ary partial recursive function f such that
a) \((\forall x_ 1,...,x_ n)(f(x_ 1,...,x_ n)\downarrow \Rightarrow f(x_ 1,...,x_ n)\in \{x_ 1,...,x_ n\});\)
b) \((\forall x_ 1,...,x_ n)(x_ 1,...,x_ n\in A\Rightarrow f(x_ 1,...,x_ n)\downarrow);\)
c) \((\forall x_ 1,...,x_ n)(f(x_ 1,...,x_ n)\downarrow \Rightarrow (f(x_ 1,...,x_ n)\in A\Leftrightarrow \beta (\chi (x_ 1),...,\chi (x_ n))=1)),\)
where \(\chi\) is the characteristic function of A. It is proved that if \(\beta (x,...,x)=x\) and \(\beta\not\equiv x\), then the class of weak \(\beta\)-selective sets is equal to the class of all r.e. sets or the class of all \(x\vee y\)-selective sets or the class of all xy\(\vee xz\vee yz\)-selective sets. It is also proved that the second class is a strong subset of the last one.
Reviewer: A.N.Degtev


03D40 Word problems, etc. in computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees
Full Text: EuDML