Numberings in the Analytical Hierarchy
- PDF / 147,167 Bytes
- 4 Pages / 594 x 792 pts Page_size
- 14 Downloads / 200 Views
Algebra and Logic, Vol. 59, No. 5, November, 2020 (Russian Original Vol. 59, No. 5, September-October, 2020)
COMMUNICATIONS
NUMBERINGS IN THE ANALYTICAL HIERARCHY N. A. Bazhenov,1∗ M. Mustafa,2∗∗ S. S. Ospichev3∗∗∗ , and M. M. Yamaleev4∗∗∗∗
UDC 510:5
Presented by Associate Editor S. S. Goncharov Let S be a countable set. A numbering of S is a surjective map ν from the set of natural numbers ω onto S. A standard tool for comparing complexities of different numberings uses the notion of reducibility between numberings: a numbering ν is reducible to a numbering μ if there is a total computable function f (x) such that ν(x) = μ(f (x)) for all x ∈ ω. Numberings that are reducible to each other are said to be equivalent. Goncharov and Sorbi [1] laid the groundwork for the theory of generalized computable numberings. One of their approaches to generalized computations can be outlined as follows. Let 0 1 Γ be a complexity class (e.g., Σ01 , Σ−1 2 , Σn , or Πn ). Consider a countable family S ⊂ P (ω). A numbering ν of the family S is Γ-computable if the set Gν = {n, x : x ∈ ν(n)} belongs to the class Γ. We say that a family S is Γ-computable if it has a Γ-computable numbering. The Rogers ∗
The study was carried out within the framework of the state assignment to Sobolev Institute of Mathematics SB RAS, project No. 0314-2019-0002. ∗∗ Supported by Nazarbayev University FDCRGP, N090118FD5342. ∗∗∗ Supported by RFBR, project No. 20-01-00300. ∗∗∗∗ Supported by a Funding Program for the Regional Scientific and Educational Mathematical Center of the Volga Federal Region, Agreement No. 075-02-2020-1478. 1
Sobolev Institute of Mathematics. Novosibirsk State University, Novosibirsk, Russia; [email protected]. 2 School of Sciences and Humanities, Nazarbayev University, Nur-Sultan, Kazakhstan; [email protected]. 3 Sobolev Institute of Mathematics. Novosibirsk State University, Novosibirsk, Russia; [email protected]. 4 Kazan (Volga Region) Federal University, Kazan, Russia; [email protected]. Translated from Algebra i Logika, Vol. 59, No. 5, pp. 594-599, September-October, 2020. Russian DOI: 10.33048/alglog.2020.59.506. Original article submitted April 21, 2020; accepted November 27, 2020.
404
c 2020 Springer Science+Business Media, LLC 0002-5232/20/5905-0404
semilattice of a family is a quotient structure of all computable numberings of the family, modulo equivalence of the numberings, ordered by the relation induced by the reducibility of numberings. In a way similar to the classical studies of computable numberings [2], we can define the notion of a Rogers semilattice for a Γ-computable family S. We say that an upper semilattice U is a Rogers Γ-semilattice if there is a Γ-computable family S such that the Rogers semilattice of S is isomorphic to U. The reader is referred to [2-4] for further background on Rogers semilattices. In this paper, we investigate Rogers semilattices in the analytical hierarchy. First results in this area were obtained by Owings in [5]. In Section 1, we give general results, which do
Data Loading...
