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

Алгебра и логика, 2016, том 55, номер 2, страницы 133–155 (Mi al735)

Эта публикация цитируется в 15 статьях

О степенях автоустойчивости относительно сильных конструктивизаций для булевых алгебр

Н. А. Баженовabc

a Ин-т матем. им. С.Л. Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ
b Новосибирский гос. ун-т, ул. Пирогова, 2, г. Новосибирск, 630090, РОССИЯ
c Казанский федерал. ун-т, ул. Кремлёвская, 18, г. Казань, 420008, РОССИЯ

Аннотация: Доказывается, что для любого вычислимого ординала $\alpha$ тьюрингова степень $\mathbf0^{(\alpha)}$ является степенью автоустойчивости некоторой вычислимой булевой алгебры и степенью автоустойчивости относительно сильных конструктивизаций для некоторой разрешимой булевой алгебры. Показывается, что булева алгебра Харрисона не имеет степени автоустойчивости относительно сильных конструктивизаций. Устанавливается, что индексное множество разрешимых булевых алгебр, имеющих степень автоустойчивости относительно сильных конструктивизаций, является $\Pi^1_1$-полным.

Ключевые слова: автоустойчивость, булева алгебра, автоустойчивость относительно сильных конструктивизаций, степень автоустойчивости, степень категоричности, индексное множество.

УДК: 512.563+510.5

Поступило: 07.05.2014
Окончательный вариант: 03.12.2015

DOI: 10.17377/alglog.2016.55.201


 Англоязычная версия: Algebra and Logic, 2016, 55:2, 87–102

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


© МИАН, 2024