Пузаренко В. Г.
К вычислимости на специальных моделях

Изучаются свойства дескриптивной теории множеств, которые переносятся с идеалов степеней по перечислимости на допустимые множества. Показано, что для допустимых множеств, соответствующих неглавным идеалам и обладающих свойством минимальности, принцип редукции не выполняется, а свойства существования универсальной функции, отделимости и тотальной продолжимости переносятся с идеалов для специальных классов допустимых множеств. Впервые приводятся примеры допустимых множеств, удовлетворяющих принципу тотальной продолжимости. Кроме того, выделяется широкий подкласс допустимых множеств, для которых отсутствуют разрешимые вычислимые нумерации семейства всех вычислимо перечислимых подмножеств. В основном, обсуждаются минимальные классы допустимых множеств, соответствующие неглавным идеалам степеней по перечислимости.

Puzarenko V. G.
Computability in special models

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.

Полный текст статьи / Full texts:

• PDF file (600 KB)
• PostScript file (1,2 MB)