## 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

### MSC:

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