RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2005 Volume 46, Number 1, Pages 185–208 (Mi smj951)

This article is cited in 22 papers

Computability in special models

V. G. Puzarenko

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We study some properties of descriptive set theory which translate from the ideals of enumerability degrees to admissible sets. We show that the reduction principle fails in the admissible sets corresponding to nonprincipal ideals and possessing the minimality property and that the properties of existence of a universal function, separation, and total extension translate from the ideals to some special classes of admissible sets. We first give some examples of the admissible sets satisfying the total extension principle. In addition, we define a broad subclass of admissible sets admitting no decidable computable numberings of the family of all computably enumerable subsets. We mostly discuss the minimal classes of admissible sets corresponding to the nonprincipal ideals of enumerability degrees.

Keywords: admissible set, ideal, $e$-reducibility, computability, descriptive set theory, Friedberg numbering.

UDC: 510.5

Received: 29.10.2004


 English version:
Siberian Mathematical Journal, 2005, 46:1, 148–165

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025