Об одном достаточном условии сильной конструктивизируемости атомных булевых алгебр
Автор: Дзгоев В.Д.
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 2 т.2, 2000 года.
Бесплатный доступ
Настоящая работа посвящена доказательству сильной конструктивизируемости фактор-алгебр конструктивной булевой алгебры относительно идеала при условии, что множество номеров, соответствующих этому идеалу, хорошо расположено в арифметической иерархии. Этот результат был доложен автором на IV Всесоюзной конференции по математической логике в 1976 году в Кишиневе и анонсирован в [1]. Однако полное доказательство до сих пор так и не было опубликовано.
Короткий адрес: https://sciup.org/14318002
IDR: 14318002
Текст научной статьи Об одном достаточном условии сильной конструктивизируемости атомных булевых алгебр
Настоящая работа посвящена доказательству сильной конструктивизируемости фактор-алгебр конструктивной булевой алгебры относительно идеала, при условии, что множество номеров, соответствующих этому идеалу, хорошо расположено в арифметической иерархии. Этот результат был доложен автором на. 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(n> 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, Л2 — разбиение Ап на два бесконечных непересекающихся подмножества. Полагаем ДЦнД = А., ДР^нД = А^.
Зафиксируем функцию / и будем обозначать /(п) через Ап. Обозначим A(D) ^ {An \ n G D}U{0}. Непосредственно проверяется, что семейство АДД замкнуто относительно конечных пересечений и дополнение An G A(D) до А равно некоторому конечному объединению множеств из A(D\
Обозначим посредством B(D) С РД^ семейство множеств, порожденное семейством A(D) с помощью операций О, U, ~l Тогда
93о^(В(£>),П,и,^,0,Л)
является булевой алгеброй. Пусть D — рекурсивно перечислимое дерево и G : ш —Д РШДД — гёделева нумерация всех конечных подмножеств дерева D. Определим отображение гд : ш —> B(D) следующим образом:
vd^ ^ и^8 । 8 е GWV
В [5] доказано, что ДВп, уД — конструктивная булева алгебра.
Покажем теперь, как по конструктивной булевой алгебре (93, z/) построить рекурсивно перечислимое дерево В такое, что (93, п) изоморфно (93 d, vdY Построение по индукции. На шаге п будем строить конечное дерево Вп и ч. р. ф. / такие, что В^у D Вп и функция / определяется на шаге п на элементах дерева Вп.
Шаг 0. Пусть vno = 1. Тогда положим, Bq ^ {0} и /(0) ^ По. На других элементах / на шаге 0 не определяется.
Шаг п + 1. Рассмотрим все концевые вершины дерева Вп, пусть это П1, ...,Пк и пусть /(щ) = 7711, ..., /(nfc) = Шк.
Положим Dn_ir\ ^DnU{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 Пусть В = |Jj Bi — рекурсивно перечислимое дерево такое, что ®р = 93 и для любых n, m Е ш, если m Е В^у, то Р(Л) Е Вп. Пусть {В^ г < ш} — вычислимая последовательность конечных множеств, существование которой доказано в лемме 1.
По индукции строим рекурсивно перечислимое дерево В', которое будет порождать искомую алгебру 21, т. е. 21 ^ ®р'. По индукции будет строиться также частично рекурсивная функция ipYyyY которая будет порождать изоморфизм булевых алгебр и рекурсивно перечислимый предикат А, который совпадает с множеством тупиков дерева В'.
Построение дерева В'.
Шаг 0. В' ^ 0, (^(0, 0) ^ 0, Л(0) ^ 1.
Шаг 2n + 1. Пусть е Е Bn+i — наименьшее число такое, что е Е Вп, метка |~ё~| не стоит на элементах Dn+i, и выполняются следующие два условия.
-
(1) Существует тупик а Е В^х такой, что элементы цепи я[а] не помечены никакими метками и е ^ я [а].
-
(2) Для любого элемента т G -О^-щ, т >- е, не помеченного никакими метками, существует тупик к такой, что т ^ к & е ^ к и элементы тг[А;] не
помечены метками.
Тогда помечаем меткой |~ё~| все числа х G Dn +1, х ^ е.
Пусть По, rii,
..., ns
— тупики дерева
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
Определяем функцию у) так:
<Д2п + 1, mJ ^ Д(щ), (Д2п + 1, L(mJ) = £(Д(щ)),
Д2п + 1, R(mYY = 7?(7?(nJ).
Для t G Dn+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 Dn+i \ х ^q\
Полагаем А^ = 1 для всех у. которые являются тупиками D^n+i и выполнено (-it/ =<1 а & у 4 тп). Для всех х G Ри+1(д) полагаем рДп + 2, ж) = у, где у — образ элемента х при изоморфизме Dn+i(q) на поддерево D™.
Для остальных х G Dn+i определяем у)(2п + 2, ж) ^ рДп + 1, ж). Метку р снимаем со всех элементов Dn+i. Если какое-то условие шага не выполняется, то переходим к следующему шагу, полагая рДтг + 2, ж) ^ рДтг + 1,ж) для х G Dn+i. Построение закончено.
Замечание (1) Если число х G Dn помечено меткой [~ё~| и у 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 и е ^ Snj+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 в дереве Dn+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 плотно в Во1 \Ф- Из леммы 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, ...,ps}, имеется единственное представление минимальной длины 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 Для доказательства нужно воспользоваться критерием автоустойчивости булевых алгебр. >
Список литературы Об одном достаточном условии сильной конструктивизируемости атомных булевых алгебр
- Дзгоев В. Д. О конструктивизируемости булевых алгебр//В кн: IV Всесоюзная конференция по математической логике. Тезисы докладов.-Кишинев, 1976.-С. 42.
- Гончаров С. С. Счетные булевы алгебры и разрешимость.-Новосибирск: Научная книга, 1996.
- Гончаров С. С., Ершов Ю. Л. Конструктивные модели.-Новосибирск: Научная книга, 2000.
- Ершов Ю. Л. Определимость и вычислимость.-Новосибирск: Научная книга, 1996.
- Перетятькин М. Г. Сильно конструктивные модели и нумерации булевой алгебры рекурсивных множеств//Алгебра и логика.-1971.-T. 10, № 5.-C. 535-557.
- Гончаров С. С. Некоторые свойства конструктивизаций булевых алгебр//Сиб. мат. журн.-1976.-Т. 17, № 2.-С. 257-282.
- Remmel J. B. Recursive isomorphism types of recursively presented Boolean algebras//Notices Amer. Math. Soc.-1978, V. 25, № 7, A-706.
- Дзгоев В. Д. Декартовы степени конструктивных моделей//В кн: V Всесоюзная конференция по математической логике. Тезисы докладов.-Новосибирск, 1979.-С. 43-44.
- Дзгоев В. Д. Конструктивизации алгебраических конструкций.-НГУ, Новосибирск: Дисс.... канд. физ.-мат. наук, 1980.