Positive Numberings of the Families of Σ_{n}^{−1} Sets

Z. Talasbaeva

We refer to [1]-[3] for the basic notions of the computability theory and the theory of numberings. Let S be a family of the sets from the class Σ_{n}^{−1}, n ∈ ω, of the hierarchy of Ershov [4].

A numbering α : ω → S is called Σ_{n}^{−1} - computable if

{(x, m)|x ∈ αm} ∈ Σ_{n}^{−1}.

This definition is a slight modification of the notion of Σ_{n}^{0}- computable numbering given in [5]. A numbering α is called positive, [2], if

{(n, m)|αn = αm} ∈ Σ_{1}^{0}.

The conjecture on existence of any positive Σ_{n}^{−1} - computable numbering of the class of the all Σ_{n}^{−1} sets, n ≥ 2, was formulated in [6].This conjecture was proved for second level of the hierarchy of Ershov.(n = 2)

Theorem.,[7].The class Σ_{2}^{−1} has a positive Σ_{2}^{−1}- computable numbering. The following theorem is a more essential result.

Theorem. For every n ≥ 2 the class Σ_{n}^{−1} sets has an infinite number of nonequivalent positive Σ_{n}^{−1}- computable numberings.

References [1]Ershov U.L. Theory of numberings.- Moskow, Science,1977.

[2] Malcev A.I. Algorithms and recursive functions.- Moskow, Science, 1965.

[3] Rogers H. Theory of recursive functions and effective computability.- Moskow, World, 1972.

[4] Ershov U.L. About one hierarchy of sets. Algebra and logic, v.7,1,1968,pp 65-71.

[5] Goncharov S.S., Sorbi A. Factorally-computable numberings and nontrivial semilattics of Rodjers. Algebra and logic, 1997, v.36,6, pp 621-641.

[6] Badaev S.A., Goncharov S.S. Theory of Numbering. Open Problems. In: Procceeding of the Applications, USA, Boulder, June 13-17(to appear).

[7] Talasbaeva Z.T.The positive computability of the classes of hierarchy of Ershov.Almaty, Vestnik, KazSU,(to appear in 2000).

Address: KazSNU, Almaty, Kazakhstan