RUS  ENG
Full version
JOURNALS // Matematicheskie Trudy // Archive

Mat. Tr., 2004 Volume 7, Number 2, Pages 35–71 (Mi mt76)

This article is cited in 19 papers

Computability Principles on Admissible Sets

I. Sh. Kalimullina, V. G. Puzarenkob

a Kazan State University, Faculty of Mechanics and Mathematics
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We study some principles of descriptive set theory which are translated from $e$-ideals to admissible sets. We are mainly interested in the properties of principal $e$-ideals. A construction is suggested of an admissible set corresponding to a principal $e$-ideal. This construction preserves the majority of basic computability-theoretic properties of a given principal $e$-ideal, such as the enumeration and uniformization principles, the existence of a universal function, and the separation principle. For principal ideals, we find the exact relations between the above-listed properties. We also find the exact arithmetical and structural estimates for the complexity of separating degrees. The results are used for clarifying the relationship between the principles on admissible sets.

Key words: computably enumerable set, enumeration reducibility, $e$-degree, ideal of $e$-degrees, principles of descriptive set theory, admissible set, hereditarily finite set.

UDC: 510.5+510.225

Received: 31.10.2003


 English version:
Siberian Advances in Mathematics, 2005, 15:4, 1–33

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024