Спектры степеней определимых отношенийна булевых алгебрах ∗П.М. Семухин
УДК 510.5+512.563
АннотацияВ данной статье изучаются вопросы, связанные со строением спектра множества атомов и идеала безатомных элементов в вычислимой
булевой алгебре. Доказано, что если спектр множества атомов содержит 1-низкую степень, то он содержит вычислимую степень. Также
показано, что в вычислимой булевой алгебре характеристики (1,1,0) свычислимым множеством атомов спектр безатомного идеала состоитиз всех Π02 степеней.

§1. Введение. Изучение строения тьюринговых спектров отношенийна вычислимых моделях занимает одно из центральных мест в теории конструктивных алгебраических систем. Это исследование началось с работы
К. Эша и А. Нероуда [6], в которой они дали синтаксическое описание наследственно вычислимых и наследственно вычислимо перечислимых отношений.
Исследование спектров отношений оказалось не только полезным методом в изучении различных вычислимых представлений данной модели, но ипревратилось в самостоятельное и весьма плодотворное направление, связанное с различными областями теории вычислимости и математической
логики.
Следуя диссертации В. Харизановой [8], будем называть спектром степеней (или просто спектром) отношения R на вычислимой модели A следующее множество Spec(R)={ deg(R0 ) | существует вычислимая модельA0 ∼= A, в которой R0 является образом R}, где deg(R0 ) — степень Тьюринга множества R0 .
Особый интерес представляет изучение спектров отношений на линейных порядках и булевых алгебрах, так как они являются достаточно нетривиальным, но, с другой стороны, хорошо изученным классом моделей.
Недавно С.С. Гончаров, Р. Доуни и Д. Хиршфельд полностью решили
вопрос о мощности спектров вычислимых отношений на булевых алгебрах.
Предложение 1 (С.С. Гончаров, Р. Доуни, Д. Хиршфельд [3]).
Пусть R — вычислимое отношение на вычислимой булевой алгебре B. Тогда R либо определяется бескванторной формулой с константами из B (вэтом случае R наследственно вычислимо), либо Spec(R) бесконечен.
∗ Работа автора поддержена грантами РФФИ “Инварианты в моделях и их алгоритмические свойства” (код 02-01-00593), “Ведущие научные школы” (код НШ-2112.2003.1)
и “Университеты России” (код УР.04.01.013).

1Аналогичный результат имеет место для линейных порядков.
Предложение 2 (Д. Хиршфельд). Пусть R — вычислимое отношение навычислимом линейном порядке L. Тогда R либо наследственно вычислимо,либо Spec(R) бесконечен.
Важную роль играет изучение спектров формульно опредилимых отношений, таких как множество соседних элементов в линейных порядкахили множества атомов, безатомных элементов и т.д. в булевых алгебрах.
Дж. Реммел [10] доказал, что спектр множества атомов в вычислимой булевой алгебре замкнут вверх, а Р. Доуни [7] доказал, что этот спектр всегда
содержит неполную степень.
Данная работа посвящена дальнейшему изучению строения спектра множества атомов, а также идеала безатомных элементов в вычислимой булевой алгебре. Определение основных понятий, относящихся к теории вычислимости, теории конструктивных моделей и теории булевых алгебр можно
найти в книгах Х. Роджерса [5], Р. Соара [11], С.С. Гончарова, Ю.Л. Ершова
[4] и С.С. Гончарова [2] соответственно.
Множество A 6T ∅0 называется 1-низким, если A0 ≡T ∅0 , где A0 —тьюрингов скачок множество A.
Квантор ∀# означает “для всех, за исключением конечного числа”.
При работе с бинарными деревьями будем использовать обозначения изкниги С.С. Гончарова [2].
Пусть B — булева алгебра и x ∈ B, тогда AtB (x) обозначает число атомов B, лежащих под x. Идеал, порожденный идеалом Фреше и безатомным
идеалом, будем обозначать S(A).
При доказательстве того, что две булевы алгебры изоморфны, мы будем
пользоваться критерием Воота, который можно найти в [2].
В §2 мы докажем, что для булевых алгебр определенного вида спектр
идеала безатомных элементов является полным, т.е. содержит все Π02 степени. В §3 будет доказано, что если спектр множества атомов содержит
1-низкую степень, то он содержит вычислимую степень. В частности, отсюда следует, что не существует вычислимой булевой алгебры, у которой
спектр множества атомов содержит все вычислимо перечислимые степени,кроме вычислимой.
§2. Спектр идеала безатомных элементов. Основной результат этойчасти содержится в следующей теореме.
Теорема 1. Пусть B — вычислимая булева алгебра элементарной характеристики (1, 1, 0) такая, что множество атомов B — вычислимо. Тогда для любого Π02 -множества C существует вычислимая булева алгебра
B0 ∼= B такая, что Al(B 0 ) ≡T C.
Доказательство. В работе В.Н. Власова и С.С. Гончарова [1] доказывается, что вычислимая булева алгебра элементарной характеристики
(1,1,0) с вычислимым множеством атомов имеет разрешимое представление. Поэтому будем считать, что булева алгебра B разрешима. Будем использовать следующее определение.
Определение. Пусть {Bi }i∈ω последовательность булевых алгебр такая, что:1) множество {(i, x) | x ∈ Bi } — вычислимо перечислимо,22) функции f0 (i, x, y) = x∨i y, f1 (i, x, y) = x∧i y, f2 (i, x) = Ci (x) — частично
вычислимы, где ∨i , ∧i , Ci — операции, заданные на булевой алгебре Bi ,3) функции g0 (i) = 0Bi и g1 (i) = 1Bi — вычислимы.
Назовем такую последовательность вычислимой.
Рассмотрим множество A = {hx0 , . . . , xk i | xi ∈ Bi , xk = 0Bk или xk =Bk
1 , и xk 6= xk−1 }. Каждому кортежу hx0 , . . . , xX
k i ∈ A сопоставим взаимно
однозначным образом следующий элемент x ∈
Bi :
{0,1}

i∈ω



если i 6 k,
xi ,
B
i
x(i) = 0 , если i > k и xk = 0Bk , Bi
1 , если i > k и xk = 1Bk .

Ясно, что множество A — вычислимо перечислимо. Тогда существует разнозначная вычислимая функция f такая, что ρf = A. С помощью функции
f определим вычислимые функции ∨, ∧ и C так, Xчтобы B = hN, ∨, ∧, Ciбыла вычислимой булевой алгеброй, изоморфной
Bi . Такую буле{0,1}i∈ωву алгебру
X B назовем естественным вычислимым представлением прямой
суммы
Bi .
{0,1}

i∈ω

Докажем одну вспомогательную лемму.

Лемма 1. Пусть A и B счетные булевы алгебры такие, что:a) множество атомов в A и B бесконечно,b) A и B не содержат бесконечных атомных элементов,c) для любого x ∈ A (x ∈ B) либо x ∈ S(A) (x ∈ S(B)), либо C(x) ∈S(A) (C(x) ∈ S(B)).
Тогда A ∼=B∼
= Bω+η .
Доказательство. Пусть
S = {(x, y) | x ∈ A, y ∈ B, x ∈ S(A) ⇐⇒ y ∈ S(B),x ∈ F r(A) ⇐⇒ y ∈ F r(B) и x ∈ S(A) =⇒ AtA (x) = AtB (y)}.
Нетрудно проверить, что S является условием изоморфизма алгебр A и B.
Следовательно, по критерию Воота A изоморфна B. Очевидно, что алгебра
Bω+η удовлетворяет условиям a), b) и c) леммы 1. Таким образом, A и Bизоморфны Bω+η .
Лемма 2. Пусть B — разрешимая булева алгебра элементарной характеристики (1, 1, 0). Тогда существует вычислимая X
последовательность
{Bi }i∈ω вычислимых булевых алгебр такая, что B ∼Bi , ch1 (Bi ) =
=
{0,1}

i∈ω

0, и множества атомов и безатомных элементов Bi равномерно вычислимы по i.
3Доказательство. Так как B разрешима, то идеал Ершова-Тарского
I(B) вычислим. Пусть {ai }i∈ω — вычислимая последовательность, перечисляющая все элементы B. Построим вычислимую последовательность
{bi }i∈ω следующим образом: положим b0 = at , где t — наименьшее число такое, что at W
∈ I(B) и at 6= 0; пусть b0 , . . . , bn уже построены, полоbi , где t — наименьшее число такое, что at ∈ I(B) ижим bn+1 = at \i6nW
bi 6= 0. Положим Bi = bbi . Тогда последовательность {Bi }i∈ω являетat \i6n

ся искомой.

Рассмотрим последовательность {Bi }i∈ω , существование которой утверждается в лемме 2. Так как ch1 (Bi ) = 0, то Bi ∼= A0i × Bi0 , где A0i — атомная
0булева алгебра, Bi — безатомная булева алгебра или 0.
противном
Заметим, что если ∃∞ i Bi0 ∼= Bη , так как в X= 0, то ∃∞ i Bi0 ∼случае ch1 (B) = 0. Положим Bi1 = Bi × Bη . Ясно, что B ∼
Bi1 .
=
{0,1}

i∈ω

Поэтому в дальнейшем будем считать, что Bi ∼= Bη для
= A0i × Bi0 , где Bi0 ∼всех i. Рассмотрим следующие случаи.
Случай 1. ∃∞ i A0i бесконечна.
Случай 1.1. Существует бесконечно много i таких, что в A0i существует
прямое слагаемое типа Bω . Положим Bi1 = BiX
× A∗ , где A∗ — разрешимое
представление Bω . Как нетрудно видеть B ∼Bi1 , значит, в данном
=
{0,1}

i∈ω

случае можно считать, что A0i бесконечна для всех i.
Случай 1.2. Среди i таких, что A0i бесконечна содержится лишь конечное число i таких, что в A0i имеется прямое слагаемое типа Bω . В этом слуA∗ , где A∗чае ∃∞ i A0i ∼= Bω×η . Аналогично случаю 1.1. положим Bi1 = Bi ×X∼— разрешимое представление Bω×η . Как нетрудно видеть B =
Bi1 ,

{0,1}
i∈ω
0
значит, в данном случае можно считать, что Ai бесконечна для всех i.
Случай 2. ∃<∞ i A0i бесконечна. Выделим все A0i такие, что A0i бесконеч-на, в отдельное слагаемое. Оставшаяся часть будет по лемме 1 изоморфна
Bω+η , т.е. B изоморфна прямому произведению Bω+η и вычислимой бесконечной атомной булевой алгебры. Теперь доказательство теоремы 1 будет
следовать из лемм 3 и 4, приводимых ниже.
Лемма 3. Пусть C — произвольное Π02 -множество. Тогда существует
вычислимая булева алгебра B ∼= Bω+η такая, что Al(B) ≡T C.
Доказательство. Если C вычислимое множество, то в качестве Bнужно взять разрешимое представление Bω+η . Далее будем считать, чтоC невычислимо. Так как C — Π02 -множество, то существует вычислимый
предикат R(x, s) такой, чтоx ∈ C ⇐⇒ ∃∞ s R(x, s).
Пусть D — вычислимая безатомная булева алгебра и пусть {Di }i∈ω — сильно вычислимая последовательность конечных подалгебрSD такая, что D0 =Di .
{0, 1}, Di+1 = gr(Di ∪ {ai }), где ai — атом Di+1 и D =i∈ω4Рассмотрим вычислимую последовательность булевых алгебр
{Bi }i∈ω такую, что для любого k B2k = D0 и B2k+1 = D. По шагам будем
строить вычислимую последовательность {Bi0 }i∈ω .
00
Шаг 0. Для всех k положим B2k= B2k , B2k+1= B2k+1 .
Шаг s+1. Для всех k 6 s+1 таких, что R(k, s+1) производим следующие
s+1
s= Di+1 . Для всех остальных
построения: если B2k= Di , то положим B2ks+1sk положим B2k = BS
.
На
этом
шаг
s+1
завершен.
2k0sПоложим B2k=
B2k. Таким образом последовательность {Bi0 }i∈ω поs∈ω
Xстроена. Пусть B естественное вычислимое представление
Bi0 . Име{0,1}i∈ωем следующую эквивалентность

k ∈ C ⇐⇒ xk — безатомный элемент

X

{0,1}

Bi0 ,

i∈ω

где
k

x (i) =(

0

0Bi , если i 6= 2k,
0
1Bi , если i = 2k.

Значит, C 6T Al(B). Далее, x — безатомный элемент

X

{0,1}

Bi0 тогда иi∈ω0только тогда, когда существует i0 такое, что для всех i > i0 x(i) = 0Bi идля всех i 6 i00i — четное =⇒ x(i) = 0Bi или 2i ∈ C.
Значит, Al(B) 6T C. Так как C — невычислимо, то N \ C — бесконечно. Полемме 1 B ∼= Bω+η .
Лемма 4. Пусть {Bi }i∈ω — вычислимая последовательность булевых алгебр таких, что Bi ∼= A0i × Bi0 , где A0i — бесконечная атомная булева ал0 ∼гебра, Bi = Bη , и множества атомов и безатомных элементов Bi рав0номерно вычислимы по i. Тогда для
X любого Π2 -множества C существует
вычислимая булева алгебра B ∼Bi такая, что Al(B) ≡T C.
=
{0,1}

i∈ω

Доказательство. Так как множество атомов Bi равномерно вычислимо по i, то можно построить вычислимую последовательность {ai }i∈ω такую, что ai — атом Bi . Пусть D — вычислимая безатомная булева алгебра
и {Di }i∈ω — сильно вычислимая последовательность конечных подалгебр,определенная в доказательстве леммы 3. Рассмотрим вычислимую последо\вательность
{Ci }i∈ω
X
Xтакую, что C2k = D0 и C2k+1 = (C(ak ))Bk . Очевидно,чтоCi ∼Bi . Пусть R(x, s) — вычислимый предикат, такой
=
{0,1}

что

i∈ω

{0,1}

i∈ω

x ∈ C ⇐⇒ ∃∞ s R(x, s).
По шагам построим вычислимую последовательность {Ci0 }i∈ω .
00
Шаг 0. Для всех k положим C2k= C2k , C2k+1= C2k+1 .

5Шаг s+1. Для всех k 6 s+1 таких, что R(k, s+1) производим следующие
s+1sпостроения: если C2k= Di , то положим C2k= Di+1 . Для всех остальных
s+1sk положим C2k = C2k
.
На
этом
шаг
s+1
завершен.
S s00Положим C2k=
C2k . Так как для любого k C2kявляется либо коs∈ω00∼нечной, либо безатомной булевой алгеброй, то C2k
× C2k+1= Bk . Значит,
X
X
0 ∼
Ci =
Bi . Пусть B — естественное вычислимое представле{0,1}

i∈ω

ние

X

{0,1}
i∈ω
C 0 . Так как{0,1} ii∈ωk ∈ C ⇐⇒ xk — безатомный элемент

X

{0,1}

Ci0 ,

i∈ω

где
k

x (i) =(

0

0Ci , если i 6= 2k,
0
1Ci , если i = 2k,то получаем, что C 6T Al(B). Так какX
x∈
Ci0 — безатомный ⇐⇒ существует i0 такое, что ∀i > i0
{0,1}

i∈ω

0

x(i) = 0Ci и для всех i 6 i0
(i — нечетное =⇒ x(i)— безатомный элемент Bk и
x(i) 6 C(ak ), где k = i−1
2 )&0(i — четное =⇒ x(i) = 0Ci илиi
2 ∈ C).

Значит, Al(B) 6T C.
Таким образом, теорема 1 доказана.
§3. Спектр множества атомов. Теперь докажем несколько теорем освойствах спектра множества атомов в вычислимой булевой алгебре. Прежде всего докажем следующую теорему об изоморфизме.
Теорема 2 (Об изоморфизме). Пусть A — подалгебра булевой алгебры Bтакая, что:1) множество Atom(A), атомов алгебры A, бесконечно,2) если a ∈ Atom(A), то a ∈ F r(B),3) если a ∈ Al(A), то a ∈ S(B),4) B = gr(A ∪ Atom(B)).
Тогда A изоморфна B.

6Доказательство. Пусть x, y ∈ B, будем писать x ∼ y, если x 4 y ∈F r(B). Так как B = gr(A ∪ Atom(B)), то ∀b ∈ B ∃a ∈ A a ∼ b. Легко
заметить, что ∀a ∈ A a ∈ S(A) ⇐⇒ a ∈ S(B). Положим
S = {(a, b) ∈ A × B | a ∈ F r(A) ⇐⇒ b ∈ F r(B), a ∈ S(A) ⇐⇒b ∈ S(B), a ∈ S(A) =⇒ AtA (a) = AtB (b), a ∈/ S(A) =⇒ a ∼ b}.
Рутинная проверка показывает, что S является условием изоморфизма булевых алгебр A и B. Таким образом, по критерию Воота A и B изоморфны.
Теорема доказана.
Теорема 3. Пусть B — вычислимая булева алгебра, содержащая бесконечно много атомов, и F r(B), Al(B) ∈ ∆02 . Тогда существует вычислимая
булева алгебра A ∼= B такая, что F r(A) — вычислимо перечислим.
Доказательство. Так как B — вычислимая булева алгебра, то существует вычислимо перечислимое дерево D и частично вычислимая функция
ϕ такая, что hD, ϕi — дерево, порождающее B. Также существует сильно
вычислимая
S последовательность {Ds }s∈ω конечных поддеревьев D такая,что D =
Ds и Ds+1 = Ds ∪ {L(a), R(a)}, где a — концевая вершина Ds .
s∈ωНазовем вершину x ∈ D конечной, если xb ∩D — конечно, где x
b = {y | y 4x}. Вершину x ∈ D назовем полной, если xb ⊆ D. Очевидно, чтоx — конечная вершина D ⇐⇒ ϕ(x) ∈ F r(B),x — полная вершина D ⇐⇒ ϕ(x) ∈ Al(B).

Значит множества конечных и полных вершин являются ∆02 -множествами. Тогда существуют сильно вычислимые последовательности {Fs }s∈ω
и {Gs }s∈ω конечных множеств, такие что
x — конечная вершина D =⇒ ∀# s x ∈ Fs ,x — не конечная вершина D =⇒ ∀# s x ∈/ Fs ,
x — полная вершина D =⇒ ∀# s x ∈ Gs ,x — не полная вершина D =⇒ ∀# s x ∈/ Gs .
Построим новую сильно вычислимую последовательность {Fs0 }s∈ω конечных множеств, такую что1) Fs0 ⊆ Ds ,2) x — конечная вершина D =⇒ ∀# s x ∈ Fs0 ,3) x — не конечная вершина D =⇒ ∀# s x ∈/ Fs0 ,
4) Fs0 — нижний конус в Ds , т. е. для любых x, y ∈ Ds из того, что y 4 x иx ∈ Fs0 следует, что y ∈ Fs0 ,5) 0 ∈/ Fs0 ,
6) если x ∈ Ds \ Fs0 , то существует y 4 x — концевая вершина Ds такая,что y ∈
/ Fs0 ,
77) если x — полная вершина D, то ∀# s xb ∩ Fs0 = ∅.

Смысл этих условий состоит в том, что последовательность {Fs0 }s∈ω обладает теми же основными свойствами, что и {F ∩ Ds }s∈ω , где F — этомножество всех конечных вершин в D.
Положим F00 = Fs0 ∩ D0 , где s0 — это первый шаг, такой чтоa) Fs0 ∩ D0 — нижний конус в D0 ,b) 0 ∈/ Fs0 ∩ D0 ,c) если x ∈ D0 \ Fs0 , то существует y 4 x — концевая вершина D0 такая,что y ∈
/ Fs0 ,b ∩ Fs0 ∩ D0 = ∅.
d) если x ∈ Gs0 , то xТакое s0 всегда существует. Далее, положим F10 = Fs1 ∩ D1 , где s1 — этопервый шаг после s0 , такой что выполнены условия a), b), c) и d) с заменой
Fs0 , Gs0 и D0 на Fs1 , Gs1 и D1 соответственно. И так далее.
Как нетрудно проверить, {Fs0 }s∈ω обладает свойствами 1) – 7). Для удобства обозначений вместо Fs0 будем в дальнейшем писать просто Fs .
Построение нужной булевой алгебры A будет осуществляться по шагам.
К концу шага s будут построены конечная булева алгебра As , поддерево
e s ⊆ Ds , отображение fs : D
e s −→ As такое, что hD
e s , fs i дерево порожDes = gr({fs (x) | x ∈ De s }), а также множества F rs ,дающее булеву алгебру A
F rs− .
Считаем, что носитель As является начальным сегментом N. Если вописании конструкции встречается выражение “делим атом a ∈ As на дваатома a0 и a1 в As+1 ”, то это означает, что мы строим булеву алгебру As+1такую, что носитель As+1 является начальным сегментом N, As+1 = gr(As ∪{a0 }), a0 ∈/ As и a0 6 a. Тогда a1 = a\a0 . Ясно, что по заданной As и атому
a ∈ As это построение можно осуществить эффективно.
e = gr({f (x) | x ∈ D}). Для каждого m > 0Положим f = lims fs и Aзаведем следующие требования:0Rm: m — не конечная вершина D =⇒ m ∈ dom(f ) и f (m) ∈/ F r(A),1Rm: m — конечная вершина D =⇒ m ∈ dom(f ) и f (m) ∈ F r(A).

Зададим приоритет на требованиях следующим образом:jесли n < m и m 6= S(n), то Rni > Rm
для всех i, j ∈ {0, 1},01если n < m и m = S(n), то Rn0 > RS(n)> Rn1 > RS(n).
Описание конструкции.
Шаг 0. Полагаем A0 = {0, 1}, причем 1 — наибольший, а 0 — наименьший
e 0 = {0}, f0 (0) = 1, F r0 = ∅, F r− = ∅.
элемент A0 , D
0Шаг s+1. Будем говорить, что0(i) Требование Rm
привлекает внимание на шаге s+1, если m ∈ Ds+1 ,e s , H(m) ∈ D
e s, m ∈e s, m ∈m∈/D/ Fs+1 или m ∈ D/ Fs+1 , fs (m) ∈ F rs иeсуществует k 4 S(m) — концевая вершина Ds такая, что fs (k) ∈/ F rs .

81(ii) Требование Rm
привлекает внимание на шаге s+1, если m ∈ Ds+1 ,ee s , m ∈ Fs+1 или m ∈ D
e s , m ∈ Fs+1 , fs (m) ∈m∈/ Ds , H(m) ∈ D/ F rs .

Пусть R — требование с наивысшим приоритетом, которое привлекает внимание на шаге s+1. Говорим, что это требование действует на шагеs+1. В зависимости от вида требования R будем производить следующие
построения:0e s , H(m) ∈ D
e s, m ∈(1) Пусть R = Rmи m ∈ Ds+1 , m ∈/D/ Fs+1 . Рассмотрим
fs (H(m)). Если это атом As , то делим его на два атома a0 и a1 в As+1 ,если fs (H(m)) = a ∨ b, где a — атом As и b ∈ F rs− , то делим a на два
e s+1 = De s ∪ {m, S(m)}, fs+1  D
e s = fs ,атома a0 и a1 в As+1 . Полагаем D−
fs+1 (m) = a0 , fs+1 (S(m)) = fs (H(m))\a0 , F rs+1 = F rs , F rs+1 = F rs− .

0e s, m ∈(2) Пусть R = Rmиm∈D
/ Fs+1 , fs (m) ∈ F rs и существует k 4 S(m)e— концевая вершина Ds такая, что fs (k) ∈/ F rs . Если fs (k) атом As ,то делим его на два атома a0 и a1 в As+1 , если fs (k) = a ∨ b, где a —атом As и b ∈ F rs− , то делим a на два атома a0 и a1 в As+1 . Полагаем
e s+1 = D
e s \ {k | k ≺ m},Dесли H(m) 4 n или n несравнимо с k и m
fs (n),fs+1 (n) = fs (n) ∨ a0 , если n = m
fs (n)\a0 ,если k 4 n 4 S(m),−F rs+1= F rs− \ {b ∈ F rs− | b 6 fs (m)} ∪ {fs (m)}, F rs+1 = F rs .

1
e s , H(m) ∈ D
e s , m ∈ Fs+1 . Рассмотрим
и m ∈ Ds+1 , m ∈/D(3) Пусть R = Rm
fs (H(m)). Если это атом As , то делим его на два атома a0 и a1 в As+1 ,если fs (H(m)) = a ∨ b, где a — атом As и b ∈ F rs− , то делим a на два
e s+1 = De s ∪ {m, S(m)}, fs+1  D
e s = fs ,атома a0 и a1 в As+1 . Полагаем D
fs+1 (m) = a0 , fs+1 (S(m)) = fs (H(m))\a0 , F rs+1 = {x ∈ As+1 | ∃y ∈−F rs x 6 y} ∪ {fs+1 (m)}, F rs+1
= F rs− .
1e s , m ∈ Fs+1 , fs (m) ∈(4) Пусть R = Rm
и m∈D
/ F rs . Полагаем F rs+1 =ee s , fs+1 = fs , F r− =F rs ∪ {x ∈ As | x 6 fs (m)}, As+1 = As , Ds+1 = D
s+1−F rs .

На этом шаг s+1 завершен. Теперь доказательство теоремы будет следовать из лемм, приведенных ниже.
Лемма 5. Для любого s выполнены следующие условия:e s , то fs (k) = a ∨ b, где a — атом As ,1) Если k — концевая вершина D−−a∈/ F rs и (b ∈ F rs или b = 0),

2) F rs — нижний конус в As ,e s \ {0} (fs (n) ∈ F rs & fs (S(n)) ∈ F rs ) =⇒ fs (H(n)) ∈ F rs ,3) ∀n ∈ D4) fs (0) = 1 ∈/ F rs ,e s и все атомы As , лежащие под fs (k)5) Если k — концевая вершина Dпринадлежат F rs , то fs (k) ∈ F rs ,96) F rs− ⊆ F rs .
Доказательство. Доказательство будем вести индукцией по s. Пустьна шаге s все эти условия выполнены. Рассмотрим шаг s+1. Пусть на этомшаге действует требование R. Рассмотрим следующие случаи:0e s , H(m) ∈ D
e s, m ∈(1) R = Rmи m ∈ Ds+1 , m ∈/D/ Fs+1 . Так как m ∈/ Fs+1 ,e s . Покажем, что fs (H(m)) ∈то H(m) ∈/ Fs+1 . По условию H(m) ∈ D/
F rs . Пусть fs (H(m)) ∈ F rs . Если существует k 4 S(H(m)) — концевая
0e s такая, что fs (k) ∈вершина D/ F rs , то требование RH(m)привлекало быesвнимание, что невозможно. Значит, для всех концевых вершин k ∈ Dтаких, что k 4 S(H(m)) выполнено fs (k) ∈ F rs . По индукционному
предположению получаем, что fs (H(H(m))) ∈ F rs , но H(H(m)) ∈/ Fs+1 .
Проводя это рассуждение еще несколько раз получаем, что fs (0) ∈ F rs
— противоречие. Таким образом fs (H(m)) ∈/ F rs . Теперь выполнение
всех условий очевидно.
0e s, m ∈(2) R = Rmи m ∈ D
/ Fs+1 , fs (m) ∈ F rs и существует k 4 S(m)e— концевая вершина Ds такая, что fs (k) ∈/ F rs . Проверим условие 3).
e s такая, что fs (k) ∈Пусть k 4 S(m) — концевая вершина D/ F rs . Тогда
fs (k) = a0 ∨ a1 ∨ b, где a0 , a1 — атомы As+1 , a0 ∨ a1 — атом As , b ∈ F rs−
e s+1 \ {0} и fs+1 (n) ∈ F rs+1 & fs+1 (S(n)) ∈ F rs+1 .
или b = 0. Пусть n ∈ DТогда ясно, что fs (n) ∈ F rs и fs (S(n)) ∈ F rs . По индукционному предположению fs (H(n)) ∈ F rs . Пусть fs+1 (H(n)) ∈/ F rs+1 . Это возможно
лишь в том случае, если fs+1 (H(n)) = fs (H(n)) ∨ a0 либо fs+1 (H(n)) =fs (H(n))\a0 . Если выполнен первый случай, то H(n) = m, что невозe s+1 . Если выполнен второй
можно, так как m — концевая вершина Dслучай, то k 4 H(n). Тогда fs (k) 6 fs (H(n)) ∈ F rs . Отсюда, fs (k) ∈ F rs
— противоречие. Таким образом, fs+1 (H(n)) ∈ F rs+1 .

Проверка остальных условий достаточно очевидна.
1e s , H(m) ∈ D
e s , m ∈ Fs+1 . Проверим условие
(3) R = Rmи m ∈ Ds+1 , m ∈/D3), т.е. чтоe s+1 \ {0} (fs+1 (n) ∈ F rs+1 & fs+1 (S(n)) ∈ F rs+1
∀n ∈ D=⇒ fs+1 (H(n)) ∈ F rs+1 ).

e s fs (n) ∈ F rs ⇐⇒ fs+1 (n) ∈ F rs+1 . Поэтому
Заметим, что ∀n ∈ Deдля n ∈ Ds \ {0} условие 3) выполнено. Пусть n = m. По построению
fs+1 (m) ∈ F rs+1 . Если fs+1 (S(m)) = fs (H(m))\a0 ∈ F rs+1 , то существует y ∈ F rs такой, что fs (H(m))\a0 6 y. Тогда fs (H(m)) 6 y и,следовательно, fs (H(m)) ∈ F rs . Значит, fs+1 (H(m)) ∈ F rs+1 .
Проверим условие 5). Рассмотрим случай, когда k = S(m), так какпроверка остальных случаев тривиальна. Пусть fs+1 (H(m)) = a0 ∨a1 ∨b,
fs+1 (m) = a0 , fs+1 (S(m)) = a1 ∨b, где a0 , a1 — атомы As+1 , a0 ∨a1 — атомAs , b ∈ F rs− или b = 0. Предположим, что все атомы As+1 , лежащие под
fs+1 (S(m)), принадлежат F rs+1 . Тогда a1 ∈ F rs+1 . Значит, существует
y ∈ F rs такой, что a1 6 y. Тогда a = a0 ∨a1 6 y, следовательно, a ∈ F rs .
Кроме того все атомы As+1 , лежащие под b, являются атомами As и
10принадлежат F rs . По индукционному предположению fs+1 (H(m)) ∈F rs , значит, fs+1 (S(m)) ∈ F rs+1 .
Проверка остальных условий очевидна.
1e s , m ∈ Fs+1 , fs (m) ∈(4) R = Rmиm∈D
/ F rs . Рассмотрим только условие
3), так как проверка остальных условий тривиальна.

Нужно доказать, чтоe s+1 \ {0} (fs+1 (n) ∈ F rs+1 & fs+1 (S(n)) ∈ F rs+1
∀n ∈ D=⇒ fs+1 (H(n)) ∈ F rs+1 ).

Рассмотрим случай, когда n = m, так как в остальных случаях доказательство очевидно. По построению fs+1 (m) ∈ F rs+1 . Докажем, что
fs+1 (S(m)) ∈/ F rs+1 . Пусть fs+1 (S(m)) ∈ F rs+1 , тогда fs+1 (S(m)) ∈ F rs .
Покажем, что S(m) ∈ Fs+1 . Действительно, пусть S(m) ∈/ Fs+1 . Тогда
e s такая, что fs (k) ∈существует k 4 m — концевая вершина D/ F rs . Еслиэто не так, то по индукционному предположению получим, что fs (m) ∈F rs — противоречие, так как по условию fs (m) ∈/ F rs . Таким образом
e s , S(m) ∈получили, что S(m) ∈ D/ Fs+1 , fs (S(m)) = fs+1 (S(m)) ∈ F rs
e s такая, чтои существует k 4 m = S(S(m)) — концевая вершина D0
fs (k) ∈/ F rs . Значит, на шаге s+1 требование RS(m) привлекает внима1ние, что невозможно, так как на этом шаге действует требование Rm.
Таким образом доказано, что S(m) ∈ Fs+1 . По условию m ∈ Fs+1 , значит, H(m) ∈ Fs+1 . Тогда fs (H(m)) ∈ F rs , так как если fs (H(m)) ∈/ F rs ,1привлекает внимание на шаге s+1, что невозможто требование RH(m)но. Так как fs (m) 6 fs (H(m)), то fs (m) ∈ F rs — противоречие, так какпо условию fs (m) ∈/ F rs . Таким образом, доказали, что fs+1 (S(m)) ∈/F rs+1 .

Лемма 6. Каждое требование действует лишь конечное число раз.
Доказательство. Рассмотрим n > 0 такое, что n + 1 = S(n) и рас01смотрим требования Rn0 , Rn+1
, Rn1 , Rn+1
. Пусть s0 — шаг, после которогони одно требование с более высоким приоритетом не действует. Тогда суe s . Далее, существует
ществует s1 > s0 такое, что для всех s > s1 n, S(n) ∈ D
s2 > s1 такое, чтоn — конечная вершина D =⇒ ∀s > s2 n ∈ Fs ,n — не конечная вершина D =⇒ ∀s > s2 n ∈/ Fs ,
S(n) — конечная вершина D =⇒ ∀s > s2 S(n) ∈ Fs ,S(n) — не конечная вершина D =⇒ ∀s > s2 S(n) ∈/ Fs .
Рассмотрим шаг s2 +1. Пусть n и S(n) — не конечные вершины D, тогда
n∈/ Fs2 . Если fs2 (n) ∈ F rs2 , то существует k 4 S(n) — концевая вершина
e s2 такая, что fs2 (k) ∈/ F rs2 , так как в противном случае fs2 (H(n)) ∈ F rs2
D0
не привлекает внимание на шаге
и H(n) ∈/ Fs2 . Так как требование RH(n)e s2 будем иметь
s2 +1, то для любой концевой вершины k 4 S(H(n)) дерева D11

/ Fs2 . Продолжая
fs2 (k) ∈ F rs2 . Значит, fs2 (H(H(n)) ∈ F rs2 , но H(H(n)) ∈эти рассуждения получим, что fs2 (0) ∈ F rs2 — противоречие. Значит требование Rn0 привлекает внимание на шаге s2 +1, а тогда оно действует наэтом шаге.
Таким образом fs2 +1 (n) ∈/ F rs2 +1 . Аналогично fs2 +2 (S(n)) ∈/ F rs2 +2 .
01Значит после шага s2 +2 ни одно из требований Rn0 , Rn+1
, Rn1 , Rn+1
не будет
привлекать внимания, а, следовательно, не будет действовать.
Пусть n — не конечная, а S(n) — конечная вершины D. Как и вышеполучаем, что fs2 +1 (n) ∈/ F rs2 +1 . Если fs2 +1 (S(n)) ∈/ F rs2 +1 , то требование1RS(n)будет привлекать внимание на шаге s2 +2, а, значит, будет действоватьна этом шаге. Таким образом, fs2 +2 (S(n)) ∈ F rs2 +2 . Значит, после шага s2 +201
ни одно из требований Rn0 , Rn+1
, Rn1 , Rn+1
не будет привлекать внимания,а, следовательно, не будет действовать.
Случаи, когда n — конечная, а S(n) — не конечная вершины D и когда
n и S(n) — конечные вершины D рассматриваются аналогично.
Лемма 7. Для любого n ∈ D существует предел f (n) = lims fs (n).
Доказательство. Непосредственно следует из предыдущей леммы.
e = gr(f (n) | n ∈ D), тогда ясно, что hD, f i — дерево, порождаПусть ASe Положим F r =e Значит B ∼ющее булеву алгебру A.
F rs . Докажем
= A.
s∈ω

e и F r.
несколько лемм о свойствах Ae то a ∈ F r(A).
Лемма 8. Если a — атом A,e то существует n — концевая
Доказательство. Так как a — атом A,вершина D такая, что f (n) = a. Тогда существует s0 такой, что для всехs > s0 fs (n) = f (n). Рассмотрим элемент fs0 (n) ∈ As0 . Тогда fs0 (n) = a ∨ b,
где a — атом As0 , b ∈ F rs−0 или b = 0. В любом случае b ∈ F r(A). Так как
n — концевая вершина D и fs (n) = fs0 (n) для всех s > s0 , то a является
атомом A. Значит, a ∈ F r(A).

Лемма 9. Если n — полная вершина D, то f (n) ∈ S(A).
Доказательство. Рассмотрим s0 такое,что для всех s > s0 fs (n) =f (n). Рассмотрим s1 > s0 такое, что для всех s > s1 Fs ∩ n
b = ∅. Существует
e s2 ∩ n/ F rs2 . Тогда имеет
b fs2 (m) ∈s2 > s1 такое, что для всех m ∈ Dместо следующая эквивалентность: x 6 f (n) и x — атом A ⇐⇒ x ∈ As2 исуществует b ∈ F rs−2 такое, что x 6 b 6 f (n).
Отсюда видно, что f (n) содержит лишь конечное число атомов A, т.е.
f (n) ∈ S(A).
e то x ∈ S(A).
Лемма 10. Если x — безатомный элемент A,Доказательство. Непосредственно следует из предыдущей леммы.

Лемма 11. Если x ∈ F r, то x ∈ F r(A).
12Доказательство. Пусть x ∈ F r. Рассмотрим s0 такое, что x ∈ F rs0 .
Пусть x = x0 ∨ · · · ∨ xk , где xi атом As0 , для каждого i = 1, . . . , k. Тогда все
xi ∈ F rs0 . Если существует b ∈ F rs−0 такой, что xi 6 b, то xi — атом A. Еслиe s0 такая, что fs0 (ni ) =такого b нет, то существует ni — концевая вершина D−
xi ∨ b, где b ∈ F rs0 или b = 0. Если на каком-то шаге s > s0 действует
0требование Rm, где ni 4 m, то xi окажется лежащим под элементом из−0
F rs , значит, xi ∈ F r(A). Если никакое требование вида Rm, где ni 4 m недействует после шага s0 , то ni — конечная вершина D, а тогда xi ∈ F r(A).
Таким образом, получаем, что x ∈ F r(A).
Лемма 12. Если x — атом A, то x ∈ F r.
Доказательство. Рассмотрим s0 такое, что x — атом As0 . Если существует b ∈ F rs−0 такой, что x 6 b, то x ∈ F rs0 . В противном случае сущеe s0 такая, что fs0 (n) = x ∨ b, где b ∈ F r− илиствует n — концевая вершина Ds0
b = 0. Если существует s1 > s0 такой, что fs1 (n) 6= fs0 (n), то это означает,0что на каком-то шаге, большем s0 , действовало требование Rm, где n 4 m.
00−
В этом случае существует b ∈ F rs1 такое, что x 6 b . Значит, x ∈ F rs1 .
Если для всех s > s0 fs (n) = fs0 (n), то n — концевая вершина D. Значит,существует s1 > s0 такое, что для всех s > s1 n ∈ Fs . Далее, если fs (n) ∈/F rs , то требование Rn1 привлекает внимание на шаге s. Значит, существует
s2 > s1 такой, что fs2 (n) ∈ F rs2 , а тогда x ∈ F rs2 .
Лемма 13. F r(A) вычислимо перечислим.
Доказательство. Так какx ∈ F r(A) ⇐⇒ ∃x1 . . . ∃xkk^xi ∈ F ri=1^x = x1 ∨ · · · ∨ xk

и множество F r вычислимо перечислимо, то F r(A) вычислимо перечислим.
e и Atom(A).
Лемма 14. A порождается AДоказательство. Если x, y ∈ A, то будем писать x ∼ y, если x 4
y ∈ F r(A). Пусть x ∈ A, тогда существует s0 такое, что x ∈ As0 . Легко
e s0 такие, чтозаметить, что существуют n1 , . . . , nk — концевые вершины Dx ∼ fs0 (n1 ) ∨ · · · ∨ fs0 (nk ). Положим Cs0 = {n1 , . . . , nk }.
Пусть на шаге s > s0 мы уже построили Cs . Рассмотрим шаг s+1. Ес10ли на нем действует требование вида Rm
или Rmслучая (1), то положим
0
Cs+1 = Cs . Если действует требование Rm и имеет место случай (2), тоe s из определения случая (2). Полорассмотрим k — концевую вершину D
0
жим Cs = Cs \ m.
b Если k 4 n 4 S(m) для некоторого n ∈ Cs , то положим
00
Cs+1 = Cs ∪ {m}, иначе положим Cs+1W= Cs .
fs (n). Так как в Cs мы добавляем
Понятно, что для всех s > s0 x ∼n∈Csвершины
уровня, то существует C = lims Cs и
W все меньшегоWи меньшего
e то получаем, что A = gr(Ae ∪ Atom(A)).
f (n) ∈ A,
f (n). Так как
x∼
n∈C

n∈C

13

e∼
По теореме 2 об изоморфизме получаем, что A ∼=A= B. По лемме 13
F r(A) вычислимо перечислим. Теорема доказана.
Теорема 4. Пусть B — вычислимая булева алгебра такая, что множество атомов B бесконечно и F r(B) вычислимо перечислим. Тогда существует вычислимая булева алгебра A ∼= B такая, что множество Atom(A)вычислимо.
Доказательство. Рассмотрим сильно вычислимую последовательность
конечных булевых алгебр {Bi }i∈ωS такую, что B0 = {0, 1}, Bi+1 = gr(Bi ∪{ai }), где ai — атом Bi+1 и B =Bi , а также сильно вычислимую последоi∈ωS
F ri .
вательность {F ri }i∈ω такую, что F r0 = ∅, F ri ⊆ F ri+1 и F r(B) =i∈ωПостроение нужной булевой алгебры будем производить по шагам. Нашаге s будет построена конечная подалгебра As булевой алгебры Bs и множество Ats , состоящее из атомов As . Кроме того, любой атом As , не входящий в Ats , является атомом Bs .
Шаг 0. Положим A0 = B0 и At0 = ∅.
Шаг s+1. Пусть Bs+1 = gr(Bs ∪ {as }), где as — атом Bs+1 . Пусть c— атом As такой, что as 6 c. Если c ∈ Ats , то положим As+1 = As , если c ∈/ Ats , то положим As+1 = gr(As ∪ {as }). Положим Ats+1 = {x ∈As+1 | x — атом As+1 и ∃y ∈ F rs+1 ∩ As+1 (x 6 y)}. На этом шаг s+1 завершен.
SS
e = At. Дейe =Ati . Заметим, что Atom(A)Ai и At =Пусть Ai∈ωi∈ωe тогда a — атом As для почти всех s. Еслиствительно, пусть a — атом A,a∈/ At, то a должен быть атомом B, так как иначе мы бы разделили его нанесколько частей. Таким образом, a ∈ F r(B) и, по нашему построению, aбудет перечислен в Ats на некотором шаге s.
e является объединением конечного числа атомов из B,Каждый атом Aтак как At ⊆ F r(B).
Пусть b — атом B. Рассмотрим первый шаг s, такой что b ∈ Bs . Пусть
e Если a ∈b 6 a, где a — атом As . Если a ∈ Ats , то a — атом A.
/ Ats , то a = beи в этом случае a также будет атомом A. Таким образом, каждый атом Be Отсюда следует, что множество атомов Aeлежит под некоторым атомом A.
eбесконечно и Al(A) ⊆ Al(B) ⊆ S(B).
e ∪ Atom(B)). Возьмем b ∈ B и рассмотрим наиПокажем, что B = gr(Aменьший шаг s, такой что b ∈ Bs . Тогда b = b1 ∨ . . . ∨ bk , где b1 , . . . , bk
— атомы Bs . Рассмотрим a = a1 ∨ . . . ∨ ak ∈ As , где ai — это атом As ,такой что bi 6 ai . Нетрудно видеть, что a 4 b ∈ F r(B). Следовательно,e ∪ Atom(B))
B = gr(Ae ∼e выТаким образом, по теореме 2 об изоморфизме A= B. Так как Aчислимо перечислимое множество, то существует разнозначная вычислимаe С помощью функции f определим на N выфункция f такая, что ρf = A.
числимые функции ∨, ∧ и C так, чтобы A = hN, ∨, ∧, Ci была вычислимой
e Так как x ∈ Atom(A) ⇐⇒ f (x) ∈ At ибулевой алгеброй, изоморфной A.
множество At вычислимо перечислимо, то множество Atom(A) вычислимо
перечислимо, а значит и вычислимо.
14Теперь докажем основную теорему о булевых алгебрах с 1-низким множеством атомов.
Теорема 5. Пусть B — вычислимая булева алгебра и множество атомов
B является 1-низким, тогда существует вычислимая булева алгебра A ∼=B такая, что множество Atom(A) вычислимо.
Доказательство. Так как F r(B) является Σ01 -множеством относительно Atom(B), а Al(B) является Π01 -множеством относительно Atom (B), тоиз того, что множество Atom(B) 1-низкое следует, что F r(B) и Al(B) являются ∆02 -множествами. Если B содержит конечное число атомов, то доказывать нечего, если B содержит бесконечное число атомов, то доказательство
теоремы следует из теорем 3 и 4.
После того, как было получено доказательство теоремы 5, П.Е. Алаев
указал на то, что в работе Дж. Найт и М. Стоба [9] содержится доказательство такого утверждения: если булева алгебра B является ∆02 -алгеброй спредикатами, выделяющими множество атомов, идеал Фреше и идеал безатомных элементов, то существует булева алгебра A ∼= B, которая является
вычислимой вместе с предикатом, выделяющим множество атомов. С помощью этого утверждения можно получить еще одно доказательство теоремы
5.
§4. Открытые проблемы. В свете полученных результатов возникли следующие открытые вопросы: является ли спектр идеала безатомных
элементов в вычислимой булевой алгебре характеристики (1,1,0) или (1,0,1)
замкнутым вверх, а также, существует ли вычислимая булева алгебра характеристики (1,1,0) или (1,0,1), у которой идеал безатомных элементов
наследственно невычислим?
В связи с теоремой 5 возник такой вопрос: пусть спектр множества атомов в вычислимой булевой алгебре содержит n-низкую степень, для некоторого n, тогда содержит ли он вычислимую степень?
Ответы на эти вопросы могут дать более глубокое понимание строения
спектров множества атомов и безатомных элементов в вычислимых булевых
алгебрах.
В заключение, автор благодарит своего научного руководителя, С.С. Гончарова, за постановку и обсуждение рассматриваемых в этой статье интересных проблем, а также рецензента за полезные замечания по оформлению
работы.

Список литературы
[1] В.Н. Власов, С.С. Гончаров, О сильной конструктивизируемости булевых алгебр элементарной характеристики (1,1,0), Алгебра и логика, 32,
No. 6, 618–630, 1993.
[2] С.С. Гончаров, Счетные булевы алгебры и разрешимость, Научная книга, Новосибирск, 1996.

15

[3] С.С. Гончаров, Р. Доуни, Д. Хиршфельд, Спектры степеней для отношений на булевых алгебрах, Алгебра и логика, 42, No. 2, 182–193,
2003.
[4] С.С. Гончаров, Ю.Л. Ершов, Конструктивные модели, Научная книга,Новосибирск, 1999.
[5] Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Мир, Москва, 1972.
[6] C.J. Ash and A. Nerode, Intrinsically recursive relations, in J.N. Crossley(ed.), Aspects of Effective Algebra (Clayton, 1979), (Upside Down a Book
Co., Yarra Glen, Australia, 1981), 26-41.
[7] R. Downey, Every recursive Boolean algebra is isomorphic to one withincomplete atoms, Ann. Pure and Appl. Logic, 60(1993), 193-206.
[8] V.S. Harizanov, Degree spectrum of a recursive relation on a recursive
structure, PhD Thesis, University of Wisconsin, Madison, WI (1987).
[9] J. Knight, M. Stob, Computable Boolean algebras, J. Symb. Logic, 65, No.
4, 2000, 1605–1623.
[10] J.B. Remmel, Recursive isomorphism types of recursive Boolean algebras,
J. Symb. Logic 46(1981), 572-594.
[11] R.I. Soare, Recursively Enumerable Sets and Degrees, Perspect. Math.
Logic (Springer-Verlag, Heidelberg, 1987).
Семухин Павел Михайлович,Новосибирский государственный университет,Механико-математический факультет.
The University of Auckland,
Department of Computer Science,
Private Bag 92019,
Auckland, New Zealande-mail: pavel@cs.auckland.ac.nz

16