|
Степени автоустойчивости простых булевых алгебр
Н. А. Баженовab, М. И. Марчукab a Ин-т матем. им. С. Л. Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ
b Новосибирский гос. ун-т, ул. Пирогова, 1, г. Новосибирск, 630090, РОССИЯ
Аннотация:
Исследуется понятие алгоритмической сложности изоморфизмов между вычислимыми копиями булевых алгебр. Находятся степени автоустойчивости для всех простых булевых алгебр. Показывается, что для любых ординалов $\alpha$ и $\beta$ с условием $0\le\alpha\le\beta\le\omega$ существует разрешимая модель, для которой $\mathbf0^{(\alpha)}$ является степенью автоустойчивости относительно сильных конструктивизаций, а $\mathbf0^{(\beta)}$ – степенью автоустойчивости. Доказывается, что для любого ненулевого ординала $\beta\le\omega$ существует разрешимая модель, у которой нет степени автоустойчивости относительно сильных конструктивизаций, а $\mathbf0^{(\beta)}$ является степенью автоустойчивости.
Ключевые слова:
спектр автоустойчивости, степень автоустойчивости, булева алгебра, автоустойчивость, простая модель, вычислимая модель, вычислимая категоричность, спектр категоричности, степень категоричности, разрешимая модель, автоустойчивость относительно сильных конструктивизаций.
Поступило: 11.10.2016 Окончательный вариант: 25.05.2016
Образец цитирования:
Н. А. Баженов, М. И. Марчук, “Степени автоустойчивости простых булевых алгебр”, Алгебра и логика, 57:2 (2018), 149–174; Algebra and Logic, 57:2 (2018), 98–114
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al841 https://www.mathnet.ru/rus/al/v57/i2/p149
|
Статистика просмотров: |
Страница аннотации: | 220 | PDF полного текста: | 18 | Список литературы: | 27 | Первая страница: | 7 |
|