Positive numerations of families with one-valued numerations.

*(English. Russian original)*Zbl 0572.03023
Algebra Logic 22, 345-350 (1983); translation from Algebra Logika 22, No. 5, 481-488 (1983).

A result in the theory of numerations of families of recursively enumerable sets is proved. To state the main result, some definitions are necessary.

A numeration \(\nu\) :\({\mathbb{N}}\to S\) of a family S of r.e. sets is computable if \(\{\) (x,n): \(x\in \nu (n)\}\) is r.e. - equivalently if there is a recursive function g:\({\mathbb{N}}\to {\mathbb{N}}\) for which \(\nu (n)=W_{g(n)}\) for all n. A numeration \(\nu\) is reducible to numeration \(\mu\), \(\nu\leq \mu\), if there is a recursive function f:\({\mathbb{N}}\to {\mathbb{N}}\) for which \(\nu =\mu f\); \(\nu\) is equivalent with \(\mu\) if \(\nu\leq \mu\) and \(\mu\leq \nu\). A computable numeration \(\nu\) is minimal if \(\mu\leq \nu\) implies that \(\nu\leq \mu\) for every computable \(\mu\) ; \(\nu\) is smallest if \(\nu\leq \mu\) for every computable numeration \(\mu\) of the same family S of r.e. sets; \(\nu\) is positive if \(\{\) (n,m): \(\nu (n)=\nu (m)\}\) is r.e.; \(\nu\) is one-valued if \(n\neq m\) implies \(\nu\) (n)\(\neq \nu (m).\)

The main theorem proved now reads: Each family S admitting a one-valued computable numeration has either a smallest one-valued numeration or countably many nonequivalent positive numerations. This result follows from a lemma proved by a priority argument together with a previous result due to the author. The author has a counterexample showing that the main result cannot be improved to read ”nonequivalent one-valued numerations” in place of ”nonequivalent positive numerations”.

A numeration \(\nu\) :\({\mathbb{N}}\to S\) of a family S of r.e. sets is computable if \(\{\) (x,n): \(x\in \nu (n)\}\) is r.e. - equivalently if there is a recursive function g:\({\mathbb{N}}\to {\mathbb{N}}\) for which \(\nu (n)=W_{g(n)}\) for all n. A numeration \(\nu\) is reducible to numeration \(\mu\), \(\nu\leq \mu\), if there is a recursive function f:\({\mathbb{N}}\to {\mathbb{N}}\) for which \(\nu =\mu f\); \(\nu\) is equivalent with \(\mu\) if \(\nu\leq \mu\) and \(\mu\leq \nu\). A computable numeration \(\nu\) is minimal if \(\mu\leq \nu\) implies that \(\nu\leq \mu\) for every computable \(\mu\) ; \(\nu\) is smallest if \(\nu\leq \mu\) for every computable numeration \(\mu\) of the same family S of r.e. sets; \(\nu\) is positive if \(\{\) (n,m): \(\nu (n)=\nu (m)\}\) is r.e.; \(\nu\) is one-valued if \(n\neq m\) implies \(\nu\) (n)\(\neq \nu (m).\)

The main theorem proved now reads: Each family S admitting a one-valued computable numeration has either a smallest one-valued numeration or countably many nonequivalent positive numerations. This result follows from a lemma proved by a priority argument together with a previous result due to the author. The author has a counterexample showing that the main result cannot be improved to read ”nonequivalent one-valued numerations” in place of ”nonequivalent positive numerations”.

Reviewer: P.Clote

##### MSC:

03D45 | Theory of numerations, effectively presented structures |

03D25 | Recursively (computably) enumerable sets and degrees |

03D20 | Recursive functions and relations, subrecursive hierarchies |

PDF
BibTeX
XML
Cite

\textit{S. S. Goncharov}, Algebra Logic 22, 345--350 (1983; Zbl 0572.03023); translation from Algebra Logika 22, No. 5, 481--488 (1983)

**OpenURL**

##### References:

[1] | S. A. Badaev, ”On positive numerations,” Sib. Mat. Zh.,18, No. 3, 483–496 (1977). · Zbl 0358.02047 |

[2] | S. S. Goncharov, ”The problem of the number of nonautoequivalent constructivizations,” Dokl. Akad. Nauk SSSR,25, No. 2, 271–274 (1980). · Zbl 0476.03045 |

[3] | S. S. Goncharov, ”Computable one-valued numerations,” Algebra Logika,19, No. 5, 507–551 (1980). |

[4] | S. S. Goncharov, ”Nonautoequivalent constructivizations,” Tr. IM SO AN SSSR, Novosibirsk,2, (1982). · Zbl 0407.03040 |

[5] | Yu. L. Ershov, Theory of Numerations [in Russian], Nauka, Moscow (1977). |

[6] | I. A. Lavrov, ”Computable numberings,” in: Logic, Foundations of Mathematics, and Computability Theory, pp. 195–206. · Zbl 0386.03023 |

[7] | A. I. Mal’tsev, Algorithms and Recursive Functions [in Russian], Nauka, Moscow (1965). |

[8] | A. I. Mal’tsev, ”Positive and negative numerations,” Dokl. Akad. Nauk SSSR,160, No. 2, 278–280 (1965). |

[9] | S. S. Marchenkov, ”On computable numerations of families of general recursive functions,” Algebra Logika,11, No. 5, 588–607 (1972). |

[10] | H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, (1967). · Zbl 0183.01401 |

[11] | V. L. Selivanov, ”Two theorems on computable numerations,” Algebra Logika,15, No. 4, 470–484 (1976). · Zbl 0358.02050 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.