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

Настоящая работа посвящена доказательству сильной конструктивизируемости фактор-алгебр конструктивной булевой алгебры относительно идеала, при условии, что множество номеров, соответствующих этому идеалу, хорошо расположено в арифметической иерархии. Этот результат был доложен автором на. IV Всесоюзной конференции по математической логике в 1976 году в Кишиневе и анонсирован в [1]. Однако полное доказательство до сих пор так и не было опубликовано.

Настоящая работа посвящена доказательству сильной конструктивизируемости фактор-алгебры конструктивной булевой алгебры относительно идеала при условии, что множество номеров, соответствующих этому идеалу, хорошо расположено в арифметической иерархии. Этот результат был доложен автором на IV Всесоюзной конференции по математической логике в 1976 году в Кишиневе и анонсирован в [1]. Однако полное доказательство до сих пор так и не было опубликовано.

Автор сознательно сохранил стиль, терминологию и прочие особенности текста двадцатипятилетней давности, как напоминание о необыкновенной творческой обстановке семинаров Ю. Л. Ершова, на которых автор постигал идеи теории конструктивных моделей.

Необходимые сведения из теории счетных булевых алгебр и теории конструктивных моделей имеются в [2], [3] и [4].

В доказательстве основной теоремы нам понадобится известный и весьма простой факт из теории рекурсии.

Лемма 1. Если множество А является /Х^-множеством арифметической иерархии, то существует вычислимая последовательность {В^ г G ш} конечных множеств такая, что для любого n Е ш существуют ti,!^ Е ш, удовлетворяющие условию: если n Е А, то n Е By, t' >t\, а если п ^ А, то n ^ By для t >12.

• <1    Так как Д2 = Z^ И П^, то существуют рекурсивные предикаты Р и Q такие, что

• ЗД^у^^п^ду) 4—» п ^ А,

(Зж)(\/т/)Р(п, ж, у) А —> n Е А.

Определим функцию / так:

/(п, у) ^ рх^у' < У^Р^, х, у') V ^у' < y)Q(n, х, у'^.

Очевидно, что / — рекурсивная функция. Пусть В_т = {п \ п < тп fc (\/у <  m)P(n, /(n, т), уУр Покажем, что ^В_т^_тЕш — искомая последовательность. Пусть п Е А, тогда существует такое число уо > п, что для у > уо имеем Y^l/ < У) РЛЛ ЛуЛу'^ ^и- следовательно, п Е В_у. Наоборот, пусть п ^ А. Тогда существует ух такое, что ух > п и для у > ух верно

Лу' < у^ЛЛЛоу^у') ^ Л^у ^yW^J^n^Yy'Y

Допустим, что существует у > ух и п G В_у. Тогда по определению В_у имеем Лу <  У)РЛ f(ⁿ> 5Y yY ^что противоречит выбору числа ух- >

Нам понадобится техника деревьев, предложенная М. Г. Перетятькиным (см. [5]). Определим частичный порядок ^ на натуральных числах с помощью следующих рекурсивных функций:

Р[п] ^

п —

L(n) ^ 2n + 1, Р(п) ^ 2п + 2, п'

I

n + 1, если п нечетное, п — 1, если п четное,

а(п, 0) ^ п, ct(n, m + 1) ^ Р(а(п, т)).

Полагаем m ^ n ^ а(т, г) — п = 0. г=0

Понятно, что =(N, =<() — частично упорядоченное множество, которое будем называть полным деревом. Множество D С N будем называть деревом, если выполнены условия:

• (1)    если n Е D, п 4 т, то т Е D,

• (2)    если п G D, то п' G D.

В терминах частичного порядка ^ функции Р, R, L можно понимать следующим образом. Р(п) — непосредственный последователь элемента п, ЬД") — непосредственный левый предшественник элемента п, 7?(п) — непосредственный правый предшественник элемента п, п/ — несравнимый с п элемент, но имеющий с п один и тот же последователь.

Множество тг[п] ^ {ж G S | ж ^ п} назовем цепью, содержащей п. Тупиком дерева назовем п G D такое, что R(n) ^ D. Понятно, что полное дерево тупиков не имеет.

Лемма 2. Пусть D — дерево, тогда D — рекурсивно тогда и только тогда, когда множество тупиков T(D) рекурсивно.

• < 1 Доказательство очевидно. >

Лемма 3. Если D — рекурсивно перечислимое дерево п T(D) — множество тупиков рекурсивно перечислимо, то D — рекурсивно.

• < 1 Перечисляем одновременно D и T^D). Если n G ш принадлежит D, то через конечное число шагов вычислится в D. Если n ^ D, то через конечное число шагов в T^D) вычислится элемент m такой, что m < п и m ^ п.

Покажем, как по дереву D каноническим образом строится булева алгебра, будем ее обозначать 93 d (см. [5]). Пусть А — бесконечное множество. Определим отображение / : ш -Д Р(А) индуктивно. Пусть /(0) = А. Предположим, что /(п) = А_п уже определено, причем А_п бесконечно. Пусть Ai, Л₂ — разбиение А_п на два бесконечных непересекающихся подмножества. Полагаем ДЦнД = А., ДР^нД = А^.

Зафиксируем функцию / и будем обозначать /(п) через А_п. Обозначим A(D) ^ {A_n \ n G D}U{0}. Непосредственно проверяется, что семейство АДД замкнуто относительно конечных пересечений и дополнение A_n G A(D) до А равно некоторому конечному объединению множеств из A(D\

Обозначим посредством B(D) С РД^ семейство множеств, порожденное семейством A(D) с помощью операций О, U, ~l Тогда

93о^(В(£>),П,и,^,0,Л)

является булевой алгеброй. Пусть D — рекурсивно перечислимое дерево и G : ш —Д Р_ШДД — гёделева нумерация всех конечных подмножеств дерева D. Определим отображение гд : ш —> B(D) следующим образом:

vd^ ^ и^⁸ । ^{8 е G}WV

В [5] доказано, что ДВп, уД — конструктивная булева алгебра.

Покажем теперь, как по конструктивной булевой алгебре (93, z/) построить рекурсивно перечислимое дерево В такое, что (93, п) изоморфно (93 d, vdY Построение по индукции. На шаге п будем строить конечное дерево В_п и ч. р. ф. / такие, что В^у D В_п и функция / определяется на шаге п на элементах дерева В_п.

Шаг 0. Пусть v_no = 1. Тогда положим, Bq ^ {0} и /(0) ^ По. На других элементах / на шаге 0 не определяется.

Шаг п + 1. Рассмотрим все концевые вершины дерева В_п, пусть это П1, ...,П_к и пусть /(щ) = 7711, ..., /(n_fc) = Ш_к.

Положим D_n_i_r\ ^D_nU{L(nJ,B(nJ 1 <  г < к к v^ П n(mj ^ 0 & -ш(п) П v^m^ ф 0}. На элементах В_п функция / определяется по-старому и если m Е В_п+ДВ_п, то

/(т) ^ {

/(Р(т)) П п, если L(P(m)) = m, f(P(mY П -in, если P(P(m)) = m.

В силу эффективности построения В = [J Вп — рекурсивно перечисли-п мо и легко проверить, что (93г>,пр) изоморфно (93, z/). Важно заметить для дальнейшего, что атомам булевой алгебры 93 соответствуют тупики дерева В и наоборот, тупики В переходят в атомы булевой алгебры ®р. >

Приступим к доказательству основного утверждения этой статьи.

Теорема 1. Пусть (93, п) — конструктивная булева алгебра и J — идеал Ъ. Если В = n^-1(J) является множеством арифметической иерархии, то существует сильно конструктивизируемая атомная булева алгебра 21 такая, что %) J изоморфна 21/Ф, где Ф — идеал Фреше.

• < 1 Пусть В = |J_j Bi — рекурсивно перечислимое дерево такое, что ®р = 93 и для любых n, m Е ш, если m Е В^у, то Р(Л) Е В_п. Пусть {В^ г < ш} — вычислимая последовательность конечных множеств, существование которой доказано в лемме 1.

По индукции строим рекурсивно перечислимое дерево В', которое будет порождать искомую алгебру 21, т. е. 21 ^ ®р'. По индукции будет строиться также частично рекурсивная функция ipYyyY которая будет порождать изоморфизм булевых алгебр и рекурсивно перечислимый предикат А, который совпадает с множеством тупиков дерева В'.

Построение дерева В'.

Шаг 0. В' ^ 0, (^(0, 0) ^ 0, Л(0) ^ 1.

Шаг 2n + 1. Пусть е Е B_n+i — наименьшее число такое, что е Е В_п, метка |~ё~| не стоит на элементах D_n+i, и выполняются следующие два условия.

• (1)    Существует тупик а Е В^х такой, что элементы цепи я[а] не помечены никакими метками и е ^ я [а].

• (2)    Для любого элемента т G -О^-щ, т >- е, не помеченного никакими метками, существует тупик к такой, что т ^ к & е ^ к и элементы тг[А;] не

помечены метками.

Тогда помечаем меткой |~ё~| все числа х G D_n +1, х ^ е.

Пусть По, rii, ..., n_s — тупики дерева D'_n такие, что H(nJ ^ 1, г <  з. Пусть щ = (Д2п, mJ, г <  з. Тогда полагаем D^n+i ^ D'^ U {_R(nJ,L(nJ | г < s}, ^2п+1 ^ Дп-н и {L(7?(nJ), 7?(7?(nJ) I R G D_n+1 и R(mY не помечено метками (г < s)}.

Определяем функцию у) так:

<Д2п + 1, mJ ^ Д(щ), (Д2п + 1, L(mJ) = £(Д(щ)),

Д2п + 1, R(mYY = 7?(7?(nJ).

Для t G D_n+i{mj, L(mJ, fi(mj | г < s} полагаем Д2п + 1,J = (Д2п, J,

H(L(nJ) = 1 для г < s. Для всех к 4 рДп + 1,е) полагаем А(к) = 1 если

к является тупиком дерева D^^. Переходим к следующему шагу.

Шаг 2п + 2. Пусть р — наименьший из элементов D^i таких, что р по

мечен меткой р , вместе с тем р G В,

TV

Тогда пусть т G D'_2n+1

— наименьший

элемент относительно порядка д! со следующим свойством:

Г m G 7г[Д2п + 1, р)] и существует а — тупик дерева, I DYn+i такой, что а 4 т, Л(а) ^ 1.

(*)

Пусть а — наименьший элемент с таким свойством. Определяем

ОД2 - ОД, Цфе Д™}, где D™ — конечное поддерево полного дерева с вершиной, совпадающей с элементом а, которое изоморфно дереву D(q), где q определяется равенством т = (Д2п + 1, у),

^п+ИД ^ {ж G D_n+i \ х ^q\

Полагаем А^ = 1 для всех у. которые являются тупиками D^n+i ^и выполнено (-it/ =<1 а & у 4 тп). Для всех х G Р_и+1(д) полагаем рДп + 2, ж) = у, где у — образ элемента х при изоморфизме D_n+i(q) на поддерево D™.

Для остальных х G D_n+i определяем у)(2п + 2, ж) ^ рДп + 1, ж). Метку р снимаем со всех элементов D_n+i. Если какое-то условие шага не выполняется, то переходим к следующему шагу, полагая рДтг + 2, ж) ^ рДтг + 1,ж) для х G D_n+i. Построение закончено.

Замечание (1) Если число х G D_n помечено меткой [~ё~| и у X х, то у также помечено меткой Q.

• (2)    Если t Е ш, х ^ у, то tp(2t + 1, ж) X tp(2t + 1, у).

• (3)    Число х Е D помечается меткой тогда и только тогда, когда D'(P(ip(t, ж))) ^ Д Е ВД у 4 ^(^ж)} — конечное множество для t Е ш такого, что у?(£,ж) определено.

• (4)    Число х Е ш является тупиком дерева D' тогда и только тогда, когда Л(ж) = 1.

Для завершения доказательства теоремы 1 потребуется еще несколько вспомогательных фактов.

Лемма 4. Для любого п Е ш метка рй~| ставится не более конечного числа раз.

• <1    Предположим, что метка |~ё~| ставится бесконечное число раз и снимается бесконечное число раз. Рассмотрим возрастающую последовательность £ = {щ г < ш} таких натуральных чисел, что на шаге 2щ + 1 метка Q ставилась, а на шаге 2щ_|_1 + 2 метка Q снималась с элементов дерева. Из построения следует, что е G В_П1 и е ^ S_nj+i, для щ G ф Это противоречит лемме 1, выбору ^B^ \ г < ш}. >

Лемма 5. Для любого х Е ш существует шаг, начиная с которого, если х Е В, то метка [ж~| ставится и не снимается, если хД В, то метка [ж~| снимается и больше не ставится.

• <1    В силу выбора последовательности ^ВД<_Ш для любого х Е ш существует n Е ш такое, что, если х Е В, то х Е В.„. п > щ если хД В, то хД В_п. п > п. Начиная с шага 2п + 1, метка [ж~| либо установится и сниматься не будет, либо вообще не будет ставиться. >

Лемма 6. Для любого х Е D\B существует t Е ш такое, что

• <1    Пусть х Е D\B и существует t Е ш, что <рДх) определено. Предположим, что Ь(Д Е D\B. Пусть п — наименьшее число такое, что Ь(Д Е В_п^-Если на шаге 2n + 1 L(x) не помечено никакой меткой, то Д2п + 1, Ь(дД определено. Пусть число L(x) на шаге 2n + 1 помечено меткой. Так как L(x) ^ В, то по лемме 5 существует шаг к такой, что на этом шаге и далее число Е(Д никаких меток не получит. Тогда на шаге 2к + 2 определится Д2к + 2, Т(ж)). Для Дх) доказательство аналогично. >

Лемма 7. Для любого элемента у Е В', не являющегося тупиком, существуют х Е В и t Е ш такие, что у = <рД ж).

• <1    На каждом шаге n Е ш, если у не становилось тупиком дерева В', то с добавлением у к В'_п, указывалось х Е В такое, что Дп,х) = у. >

Лемма 8. Для любого х Е D\B не являющегося тупиком дерева В, существует to, такое, что при t < to выполняется

• <1    Если х Е D ни разу не получало меток, то утверждение следует из определения шага 2n + 1. Пусть х ^ В, но на х ставились и с х снимались метки. Для любого х Е D, если х ^ В, то либо ЬД) ^ В, либо КД) ^ В. Рассмотрим два случая:

• (г) ЬД) ^ В, КД) Е В,

• (и) ЬД) ^ В, КД) ^ В.

Случай КД) ^ В, ЬД) Е В аналогичен (?) и мы его не рассматриваем.

• (?): В силу леммы 5 и 6 существует шаг Иц после которого на х и ЬД), не ставится никакая метка, р>Д1,х) определено, на КД) поставлена метка и больше не снимется. Предположим, что рД1,х) ^ срДу Ы,х) для некоторого t Е ш. Это означает, что на каком-то шаге 2к, 2к > ni наименьшее т Е D'_n, удовлетворяющее условию (*) шага 2к, равно х. Но так как КД) помечено меткой, то, если х удовлетворяет условию (*), то ЬД) тоже удовлетворяет (*). Следовательно, т ^ ЬД) и рД\, х) = рДх + t, х) для любого t Е ш.

Д): Пусть П2 — шаг, после которого на элементы ж, ЬД), КД) не ставится меток. Тогда в силу условия Y2 шага 2к + 1, для любого п > П2 в дереве D_n+x существуют тупики ко, ку такие, что элементы цепи я[^], г < 1, не помечены метками и ку ^ ЬД), к^ ^ КД). В силу замечания 3 существуют бесконечные цепи яо, Я1 в дереве D' такие, что рД2, ЬД)) € 7Го? рД^ КД)) € Я2- Это гарантирует, что на любом шаге 2к минимальное относительно порядка д! число т G ВД, удовлетворяющее условию (*), не равно х и, следовательно, РД2, аз) = рДз + t,x) для любого t Е х. >

Окончание доказательства теоремы 1. Для любого х Е Во, если х ф J, существует гц Е D\B, Hi С х. С другой стороны, если х С у, то [ж] С Д). Следовательно, X ^ Дх) Е B/J \ х Е D\B} — плотное множество в 21/J. Очевидно, что X порождает Bd/J- Применяя теорему 2.9 главы 1 из [9], получаем, что булева алгебра ®d\J изоморфна алгебре Во,- где Dy —дерево, порожденное множеством D\B.

Пусть Y ^ Ду) Е 93\Ф у Е D' и существуют х Е D и to Е ш такие, что у = рДо,х) и для любого t Е ш выполняется у)(Д,ж) = рД + t,x) либо, если такого to нет, то любое t Е ш, что у = рДх)Д

Покажем, что Y плотно в Во¹ \Ф- Из леммы 6 следует, что для любого у Е D', если у — не тупик, то существуют х Е D и t Е D такие, что у = рД,х). Пусть to — наименьшее число такое, что у)(Д,ж) = рДо + С^ж), t Е ш. Если to = 2п + 1, то рДп + 1,ж) X рДп,х). Если to = 2п + 1, то пусть т — наименьшее относительное порядка ^ число, удовлетворяющее условию (*) шага 2п + 2, <рДо, аз) 4 тп, т = рДп + 1, q).

Из определения шага 2п + 2 имеем, что

Н = ДДп + 1, q)) = ДДп + 2, q))

и

^(Д,ж) ^ Д2п + 2, q).

Следовательно, Y плотно в ®р/\Ф. Из лемм 7 и 8 следует, что Y порождает ®гДФ.

Зададим функцию / следующим образом,

/([U{n!,...,ns}]) ^ [и{<Д£,П1),...,<ДСп8)}], где t — наименьшее число такое, что срД п^ = Д1 + к, тгД к Е ш, г < s, либо, если такое не существует, то произвольное.

Из определения дерева и способа построения по дереву D булевой алгебры Во можно получить, что для любого х Е Во,х = U{pi, ...,p_s}, имеется единственное представление минимальной длины s. Это позволяет легко проверить корректность определения функции /.

Применяя леммы 7 и 8, легко доказать, что / задает биекцию X на Y с сохранением включений. Применяя теорему 2.9 главы 1 из [9], имеем, что булевы алгебры Во'/Ф и Bd/Ф изоморфны. Теорема 1 доказана. >

Теорема 1 позволяет доказать одно достаточное условие сильной конструктивизируемости атомных булевых алгебр.

Теорема 2. Если (В, г) — конструктивная атомная булева алгебра, Ф — идеал Фреше алгебры ®щ^-1(Ф) G Д®, то В — сильно конструктивизируема.

• <1 По теореме 1 существует сильно конструктивизируемая атомная булева алгебра В' такая, что 93'/Ф изоморфна В/Ф. Из предложения 2.6 главы 1 из [9] следует, что В’ изоморфна В. >

С помощью теоремы 1 можно доказать

Следствие 1 [7]. Пусть В —конструктивизируемая булева алгебра. Тогда. существуют сильно конструктивизируемые булевы алгебры Bi и В 2 такие, что Bi = В2, ВДФ = В, Bi Д_г В2. Здесь 21 =_г £ = булевы алгебры рекурсивно изоморфны.

Следствие 2 [5]. Пусть В — атомная булева алгебра. Тогда, если В/Ф — конструктивизируема, то В — сильно конструктивизируема.

• <1 Для доказательства нужно воспользоваться критерием автоустойчивости булевых алгебр. >