Calculable enumerations and equivalence relations (Q579243): Difference between revisions

Let \(R_ 1\) and \(R_ 2\) be recursively enumerable sets (RES). We say that \(R_ 1\) is \(\simeq\) equivalent to \(R_ 2\) \((R_ 1\simeq R_ 2)\), if \((R_ 1\setminus R_ 2)\cup (R_ 2\setminus R_ 1)\) is finite. Moreover, let \(\nu\) be an enumeration of the family S of RES. An enumerational equivalence for the enumeration \(\nu\) (with respect to \(\simeq)\) is an equivalence relation \(\simeq_{\nu}\), defined as follows: \(\simeq_{\nu}=\{<x,y>|\) x, \(y\in N\), \(\nu_ x\simeq \nu_ y\}.\) Theorem 1 of an earlier paper of the author and \textit{N. G. Khisamiev} [Algebra Logika 24, No.1, 108-118 (1985; Zbl 0601.20051)] characterizes equivalences on N which are enumerational equivalences for computable enumerations (with respect to \(\simeq)\) of families of general recursive functions (GRF). This fact is used in the mentioned paper to construct a torsion-free constructive Abelian group, for which the reduced part is not constructivizable. In Sec. 1 of the present article we characterize equivalence relations on N which are enumerational equivalences for computable enumerations (with respect to \(\simeq)\). In Sec. 2 we consider the problem of single-valued computable enumerations for factor-families of fundamental families of recursively enmerable sets.