Completely recursively enumerable sets
A subfamily \(W\subseteq V\) of a numerated set \(\langle V,\alpha\rangle \) is called completely enumerable provided the set of its \(\alpha\)-numbers, \(\alpha^{-1}(W)\), is recursively enumerable (r.e.). For a computable family \(V\) of r.e. sets, a subfamily \(W\subseteq V\) is called a completely enumerable subfamily of \(V\) if it is a completely enumerable subfamily of \(\langle V,\alpha\rangle \), for each computable enumeration \(\alpha\) of \(V\). A family of r.e. sets \(V\) is called an effectively open subfamily of \(W\) if, for some strongly computable sequence \(\{F_i\}\) of finite sets, the following holds: \(\forall A\in W\) \((A\in V\Leftrightarrow\exists i (T_i\subseteq A))\). There are some well-known descriptions of completely enumerable subfamilies of numerated sets with principal enumerations (references can be found in the article under review). To study a more general class of enumerations, the author introduces the notion of a Rice family. A computable family of r.e. sets is called a Rice family provided all of its completely enumerable subfamilies are effectively open. Then the author proves a series of sufficient conditions for families to be Rice and notes that there exist Rice families which fail to possess a principal computable enumeration. He also proves that there are no nondiscrete Rice families of recursive functions.
scientific article; zbMATH DE number 1353825