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

Алгебра и логика, 2003, том 42, номер 2, страницы 182–193 (Mi al24)

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

Спектры степеней для отношений на булевых алгебрах

С. С. Гончаровa, Р. Доуниb, Д. Хиршвельдc

a Институт математики им. С. Л. Соболева СО РАН
b Victoria University of Wellington, School of Mathematics, Statistics and Computer Science
c University of Chicago

Аннотация: Доказывается, что любое вычислимое отношение на вычислимой булевой алгебре $\mathfrak B$ либо определимо бескванторной формулой с константами из $\mathfrak B$ (и в этом случае, очевидно, наследственно вычислимо), либо имеет бесконечный спектр степеней.

Ключевые слова: вычислимая булева алгебра, вычислимое отношение, наследственно вычислимое отношение.

УДК: 510.5+512.563

Поступило: 21.11.2000


 Англоязычная версия: Algebra and Logic, 2003, 42:2, 105–111

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


© МИАН, 2024