Эта публикация цитируется в
31 статьях
Фридберговские нумерации семейств $n$-вычислимо перечислимых множеств
С. С. Гончаровa,
C. Лемппb,
Д. Соломонb a Институт математики им. С. Л. Соболева СО РАН
b University of Wisconsin-Madison
Аннотация:
Устанавливаются некоторые свойства вычислимых нумераций, в частности, фридберговских вычислимых нумераций семейств разностей вычислимо перечислимых (d. c. e. ) множеств:
(1) Существует фридберговская вычислимая нумерация семейства всех разностей вычислимо перечислимых множеств. Кроме того, этот результат, восходящий к известной теореме Фридберга для семейства всех вычислимо перечислимых множеств, верен также и для семейства всех
$n$-вычислимо перечислимых множеств для всех
$n>2$.
(2) Существует бесконечное семейство разностей вычислимо перечислимых множеств без вычислимых фридберговских нумераций.
(3) Существует бесконечное семейство вычислимо перечислимых множеств с единственной с точностью до эквивалентности вычислимой нумерацией, рассматриваемой как нумерация семейства разностей вычислимо перечислимых множеств.
(4) Существует семейство разностей вычислимо перечислимых множеств с наименьшей относительно сводимости вычислимой нумерацией, которая является фридберговской, но не единственной вычислимой нумерацией относительно сводимости.
Ключевые слова:
вычислимо перечислимые множества, фридберговские нумерации.
УДК:
510.10+
510.57 Поступило: 22.11.2000