|
Алгебра и логика, 2002, том 41, номер 2, страницы 143–154
(Mi al177)
|
|
|
|
Эта публикация цитируется в 31 научных статьях (всего в 31 статьях)
Фридберговские нумерации семейств $n$-вычислимо перечислимых множеств
С. С. Гончаровa, C. Лемппb, Д. Соломонb a Институт математики им. С. Л. Соболева СО РАН
b University of Wisconsin-Madison
Аннотация:
Устанавливаются некоторые свойства вычислимых нумераций, в частности, фридберговских вычислимых нумераций семейств разностей вычислимо перечислимых (d. c. e. ) множеств:
(1) Существует фридберговская вычислимая нумерация семейства всех разностей вычислимо перечислимых множеств. Кроме того, этот результат, восходящий к известной теореме Фридберга для семейства всех вычислимо перечислимых множеств, верен также и для семейства всех $n$-вычислимо перечислимых множеств для всех $n>2$.
(2) Существует бесконечное семейство разностей вычислимо перечислимых множеств без вычислимых фридберговских нумераций.
(3) Существует бесконечное семейство вычислимо перечислимых множеств с единственной с точностью до эквивалентности вычислимой нумерацией, рассматриваемой как нумерация семейства разностей вычислимо перечислимых множеств.
(4) Существует семейство разностей вычислимо перечислимых множеств с наименьшей относительно сводимости вычислимой нумерацией, которая является фридберговской, но не единственной вычислимой нумерацией относительно сводимости.
Ключевые слова:
вычислимо перечислимые множества, фридберговские нумерации.
Поступило: 22.11.2000
Образец цитирования:
С. С. Гончаров, C. Лемпп, Д. Соломон, “Фридберговские нумерации семейств $n$-вычислимо перечислимых множеств”, Алгебра и логика, 41:2 (2002), 143–154; Algebra and Logic, 41:2 (2002), 81–86
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al177 https://www.mathnet.ru/rus/al/v41/i2/p143
|
Статистика просмотров: |
Страница аннотации: | 476 | PDF полного текста: | 167 | Список литературы: | 62 | Первая страница: | 1 |
|