RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2002, том 41, номер 2, страницы 143–154 (Mi al177)

Эта публикация цитируется в 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


 Англоязычная версия: Algebra and Logic, 2002, 41:2, 81–86

Реферативные базы данных:


© МИАН, 2024