Completely recursively enumerable sets
type: Item
instance of: scholarly article
title: Completely recursively enumerable sets
zbMATH Open document ID: 0924.03085
published in: Siberian Mathematical Journal
publication date: 1999-10-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 1353825
zbMATH Keywords: numeration
zbMATH Keywords: numbering
zbMATH Keywords: completely enumerable set
zbMATH Keywords: Rice family
author: Yurij Dmitrievich Korol'kov
reviewed by: Andrei S. Morozov
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1353825