Алгебра и логика, 40, N 2 (2001), 174-191
УДК 510.53+510.67+512.563
РЕКУРСИВНЫЕ
ОДНОРОДНЫЕ
Б У Л Е В Ы АЛГЕБРЫ*)
С, Ю- П О Д З О Р О В
Проблема характеризации рекурсивных однородных булевых алгебр поставлена С. С. Гончаровым на Международной конференции по теории рекурсии и теории сложности, проходившей в Казани летом 1997 г. В на стоящей статье получены одно необходимое и одно достаточное условия рекурсивное™ однородной булевой алгебры в терминах инвариантов Мо розова. Эти инварианты, впервые рассмотренные А.С.Морозовым в [1], характеризуют счетные однородные булевы алгебры с точностью до изо морфизма; им же дано описание разрешимых однородных булевых алгебр. Случай рекурсивных однородных булевых алгебр более сложен, чем случай разрешимых. Как будет видно из результатов этой работы, множе ство, характеризующее рекурсивную однородную булеву алгебру с беско нечной первой характеристикой, может даже не быть арифметическим (в разрешимом случае оно всегда лежит в классе П^ арифметической иерар хии), однако оно является гиперарифметическим и, более того, вычисли мым с оракулом для 0 ^ ' . Оценка сложности таких множеств дана автором в терминах иерархии Фейнера [2], упорядочивающей некоторый подкласс всех 0^^-вычислимых множеств. Эта иерархия является более тонкой, чем гиперарифметическая, однако ее, по-видимому, недостаточно для исчер пывающего описания всех рекурсивных однородных булевых алгебр. *) Работа выполнена при финансовой поддержке Российского фонда фундаменталь ных исследований, проект N 99-01-00485, и Федеральной целевой программы "Интегра ция".
©
Сибирский фонд алгебры и логики, 2001
Рекурсивные однородные булевы алгебры
175
В § 3 настоящей статьи используется техника работы с нормальными сегментами, впервые примененная Одинцовым и Селивановым [3] для опи сания арифметических булевых алгебр и развитая автором в [4]. Основные результаты, относящиеся к булевым алгебрам (в частности, из [1—3]), мож но найти в книге [5]. Будем придерживаться определений и обозначений, принятых в этой книге.
§ 1. Предварительные сведения Цель настоящей работы состоит в описании рекурсивных однород ных булевых алгебр в терминах инвариантов Морозова. Поэтому эти ин варианты для случая однородных булевых алгебр с конечной первой ха рактеристикой не рассматриваются — все такие алгебры разрешимы [1]. Под булевой алгеброй, если не оговорено противное, будем понимать счетную однородную булеву алгебру с бесконечной первой характеристи кой (определение элементарных характеристик булевых алгебр см. в [5, §2.2]). Типом однородности булевой алгебры 95 (см. [5, §2.3]) называется пара th(») = («,P>, гдер = (ро,Pi,P2i • • •) ~~ счетная последовательность элементов множества {0,2}, причем рп = 2 тогда и только тогда, когда ch(x) = (та,оо,0) для некоторого ж G 95, а а е {1,2,3} и 1) а = 1, если chi(x) < оо или chi(C(ar)) < со для любого х 6 95; 2) a = 2, если существует х G 95 такой, что chi(a;) = chi(C(x))
= ос,
но для булевых алгебр х и С(х) выполняется первый случай; 3) a = 3, если для любого х 6 95 такого, что chj(x) = оо, найдется у < ж, для которого chi(y) = оо и chi(a; \ у) = оо. Согласно [5, §2.3], булева алгебра определяется своим типом одно родности с точностью до изоморфизма. Отметим, что булева алгебра с типом однородности (1,р) рекурсивна тогда и только тогда, когда рекурсивна булева алгебра с типом однородно-
С, Ю. Подзоров
176
сти (2,р). Действительно, если th(21) = (1,р), a t h ( » ) = <2,р), то » = 21x21 и 21 = Ь для некоторого b Е 25. Инвариантом Морозова булевой алгебры 25 с типом однородности (<х,р) называется множество М(») = { n G N : p n = 0}, Ранее было доказано (см. [1], а также [5, §3.4]), что *В разрешима тогда и только тогда, когда М(*В) входит в класс Щ арифметической иерархии. Как уже отмечалось, в случае рекурсивных булевых алгебр столь простой характеризации получить не удается. Дальнейшие результаты связаны с понятием иерархии Фейнера (см. [2; 5, §3.1]). Пусть а € Z, 6 € N. Будем говорить, что всюду определен ная функция / : N —> N, вычислимая с оракулом для 0 ^ ) , принадлежит классу Ф(а,Ь), если существует некоторый алгоритм с оракулом для
0&\
вычисляющий функцию / и такой, что при вычислении значения f(n) со гласно этому алгоритму вопрос "{m,q) Е 0 ^ ) ? " не задается оракулу при тп > а + Ьп. Из определения следует, что $(ai,b) С Ф(а2,Ь) для а\ < а 2 и что ^ ( a b ^ i ) С Ф(а2,&2) дая bi < ^2 и произвольных ai, аг- Можно показать, что все эти включения строгие, за исключением случая Ф(ах, 0) = Ф(^2> 0) при a i , a 2 ^ 0 (подробнее см. [5, §3.1]). Введем еще несколько обозначений. Пусть Ф(+оо,Ь)= и * ( а > * ) >
Ф(-оо,Ь)=Р|Ф(а,Ь).
Говорят, что множество I C N принадлежит классу Ф(а, Ь), если характе ристическая функция множества X принадлежит этому классу. Заметим, что множество X вычислимо, если X Е Ф(а, 0) для а ^ 0, и является арифметическим, если X Е Ф(а,0) для a E Z. Для классов арифметической иерархии будем полагать Е° = П^ = = Eg = Ilg при п < 0, пусть, как обычно, Д£ = Е° Г) П°. Справедливо следующее
Рекурсивные однородные булевы алгебры
177
П Р Е Д Л О Ж Е Н И Е 1. Множество X С N принадлежит
классу
Ф(а,Ь) тогда и только тогда, когда существуют две вычислимые функ ции f и g из множества натуральных чисел в множество
предложений
языка рекурсивной арифметики, для которых 1) /(п) является И^+^^-предложением,
д(п) является
П°+Ьп+1-
предложением; 2) если п е X, то N (= f(n) и N |= д(п), если п £ X, то N ^ /(тг) и
NtMn). ДОКАЗАТЕЛЬСТВО. Без ограничения общности можно считать, что а + Ьп ^ 0 для всех п. Действительно, при а < 0 и Ь = 0 утверждение очевидно. Если же а < 0 и Ь > 0, то рассмотрим fc € N, для которого а + Ьк ^ 0, и множество Хь — {п : п + к £ X}. Пусть мы доказали пред ложение для этого множества. Если X £ Ф(а,6), то существуют функции f(n) и д(п) с заданными свойствами, определенные для всех п ^ к; до определив их при n < fc, получим требуемое. Наоборот, если существуют две такие функции, то Xk £ Ф(а + 6&,fe) и, следовательно, X £ Ф(а,Ь). Пусть fug
{
— две функции, удовлетворяющие условиям 1 и 2. Пусть
N, если N И/(«)»
0
в противном случае
I N, если N (= #(п), и J3n = < I 0
в противном случае.
Тогда п £ X в том и только том случае, если п £ Ап и п £ JB„. Согласно сильной теореме об иерархии [6, § 14.5, теор. VIII], по п можно эффективно найти числа с и d, для которых A n = Wf "
и Вп = W^
. Тогда
по тг можно эффективно сконструировать машину Тьюринга с оракулом для 0( а + Ь п ), вычисляющую характеристическую функцию для Ап. Теперь ясно, как построить машину Тьюринга с оракулом для 0 ^ ) , вычисляющую Хх' по п строится машина Тьюринга, вычисляющая хАп 0(а+Ьп)^ В
не£
с
°РакУлом Для
заменяют вопрос о принадлежности оракулу числа т на
вопрос о принадлежности оракулу числа {а + Ьп, га) и подают число п на вход машины. Пусть, наоборот, X функция хх
£ Ф(а,Ь) и, кроме того, характеристическая
вычисляется машиной Тьюринга с оракулом для &(ш\ име-
С. Ю. Подзоров
178
ющей номер е. Пусть Ак = { ( ^ m )
: m
€ 0 ^ и / ^ к}. Тогда маши
на Тьюринга с оракулом для Аа+Ьт имеющая номер е, правильно вы числяет значение Хх(п)-
Множество Аа+Ьп вычислимо с оракулом для
0(а+Ьп) ^ П р И Ч е м номер вычисляющей функции находится эффективно по п (для доказательства этого факта можно, например, привлечь сильную теорему об иерархии). П о е и п эффективно строится машина Тьюрин га с оракулом для 0( a + fen ), правильно вычисляющая Хх(х)
на
элементе
п. Пусть <р — частичная функция, вычисляемая этой машиной Тьюринга, ф(х) = <р(п) для любого натурального числа ж, Wf' a Wj*
=• {х : ф{х) ф\).
= {x : ф(х) = 1},
Согласно сильной теореме об иерархии, по сие?
эффективно находятся Е° +Ьп+1 -формулы Ф с (я) и Ф
и Wj
соответственно. Теперь остается только
определить f(n) = Ф с (^) и
§ 2. Необходимое условие рекурсивности
Пусть 53 — рекурсивная однородная булева алгебра с бесконечной первой характеристикой. В этом параграфе получим верхнюю оценку уровня множества М(35) в иерархии Фейнера. Пусть 1п(ж), Ап(х),
Вп(х) и At n (#) — формулы сигнатуры булевых
алгебр, выделяющие элементы характеристики (fc, m,e), где к < п в пер вом случае, fc = n, w = 1 и £ = 0 - во втором случае, к < п или к — п, т — О, £ = 1 — в третьем случае, к < п или fc = тг, £ = 0 — в четвертом (аналогичные определения введены в [5, § 2.2]). Через 1 п , А п , В п и At n бу дем обозначать множества элементов булевой алгебры, выделяемые этими формулами. Известно, что 1п(х) € Е4п5 Ап(а?) £ П 4 „+ь B n (s) 6 П4п+2 и At n (x) € Щп+з (имеются в виду классы иерархии формул языка булевых алгебр). Непосредственно из определений следует, что п Е М(В) <* (Vx 6
Рекурсивные однородные булевы алгебры
179
Используя алгоритм Тарского—Куратовского [6, §14.3] и предложение 1, получаем М(®) Е Ф(4,4). Однако, как увидим ниже, эту оценку можно улучшить. Для рекурсивной булевой алгебры *В определим по индукции после довательность арифметических множеств {I*, А*,В*, At* : п Е N}.
1) Ц = (<Ы; 2) к Е А* <* к £ I* к (\/х Е <В)(х ^ к -+ х Е I* V к \ х Е I*); к Е В ; < * (Уж Е Ю)(а? ^ А - » х 0 А * ) ; если п £ М ( » ) , то к Е At; *> & € i ; V (Va € ®)(s ^ к -> ж £ В;); если п Е М ( » ) , то к Е At; <S> к Е I; V (3*)(Эу ь ... , yt E 33) ((* = yi V . . . V yt) к ух Е А ; к ... к yt E А;);
к
Е i; + 1
*> (Эх Е ®)(Эу Е ®)(ж
Е в ; & у Е At;
&fc- х v у).
Л Е М М А 1. Справедливы следующие соотношения: •U *п = : *п» А п = А п , В п = г) п , At n — At n ; 2) если 5 — количество элементов множества {х : х £ М(*В), х < < n}, mo i ; E £^__ в ; А ; Е П ^ _ , + 1 ; В ; Е П° п _ в + 2 ; At; E П° п -*+з в случае n £ М ( » ) ti At; E £!in-a+2
в
случае п Е М(<В).
ДОКАЗАТЕЛЬСТВО. Лемма доказывается индукцией по гг, исходя из определений. Детали достаточно очевидны и могут быть опущены. П Т Е О Р Е М А 1. Пусть Ш — однородная рекурсивная булева алгебра с бесконечной первой характеристикой. Тогда М(2$) Е Ф(—оо,4). ДОКАЗАТЕЛЬСТВО. Если М(<В) - конечное множество, то М(<8) Е Е Ф(0,0) С Ф(-оо,4). Пусть М(<8) бесконечно и а Е Z. Покажем, что М(Ш) Е Ф(а,4). Согласно лемме 1, найдется натуральное число fc, для которого /£ Е S4jb4.a-.4- Д л я
п
Z k определим по индукции последователь
ность арифметических множеств I n , A n , B„, At n :
1)Т = ;
* 5
2)шбА„
&
т g Tn k (Vz Е 95) (ж ^ m -> ж Е Т„ V т \ х Е Т„);
т Е В„
<£> (Уж Е 93) (ж ^ m - > ж £ А „ ) ;
га E At n
<* m E l n V (Vx E S)(x ^ ш -4 ж 0 В„); <=> (Зх Е »)(Эу Е Ш)(ж € В„ &у G At n &fc = s Vy).
ШЕТП+1
180
С. Ю. Подзоров Индукцией по п легко показать, что 1п = 1„, А п = А„, В п = В п
и At n = At n . Кроме того, Tn e S^„ +a _ 4 , А„ е П^ п + а _ 3 , В п 6 П^ п + а _ 2 и At n е П2 п + в _1, а соответствующие Ъ%п+а_4-, П^ п+а _ 3 -, И°4п+а_2- и П 2 П + 0 _ Г формулы находятся эффективно по п. Для п ^ к имеем: п € М(<8) « . (V* G <В)[х € At n —• х 61„ V (3m)(3j/ b . . . , ут £ <8) ((x = yi V . . . V y m ) & 2/1 с А п cZ У2 £ А п
& • •• & Ут £ А п )]. Согласно алгоритму Тарского—Куратовского, эта формула принад лежит классу n ^ n + a . Она может быть вычислена эффективно по п. Теперь, для каждого п < к определив EQ- И П^-формулы, истинные лишь в случае п £ М(25), в силу предложения 1 получаем требуемое. • § 3. Достаточное условие рекурсивности Доказательства результатов этого параграфа в значительной степени опираются на технику работы с нормальными сегментами. Ниже дадим все необходимые определения; кроме того, множество полезных сведений, относящихся к этой теме, можно найти в [3] и [5, §3.7]. Здесь мы отступаем от соглашения, принятого в § 1, и под булевой алгеброй понимаем произвольную счетную булеву алгебру, не обязательно однородную, и с произвольной первой характеристикой. Через 2<ш обозначим полное бинарное дерево, отождествляя его эле менты с конечными последовательностями из нулей и единиц. Нормаль ным сегментом Г называется подмножество 2 < w , удовлетворяющее следу ющим двум свойствам: 1) если (7 Е Т и г ^ а, то г £ Т; 2) если а £ Т, то а * 0 £ Г или а * 1 £ Г. Нормальные сегменты естественным образом возникают при рассмо трении нумерованных булевых алгебр. Пусть, например, *8 — счетная бу лева алгебра, / <3 5$ — идеал в *В, а J/ : N —>Ъ — нумерация. Для каждого а £ 2<ш определим элемент v[a] £ *8: 1) i/[A] - 1»;
Рекурсивные однородные булевы алгебры
181
2) u[a * 0] = u[a] Л i/(|a|), v[a * 1] = u[c] \ u(\a\). Теперь множество {о : i/[a] $ 1} будет нормальным сегментом. Для T,F С 2 < а ; полагаем T[F] = {г е Г : {3a G F ) ( a ^ г)}. Пусть У*(2<и;) — фактор-алгебра алгебры всех подмножеств 2 < и ; по идеалу ко нечных множеств; для X С 2 < w через X* обозначается элемент 3>*(2<w), содержащий X . Для нормального сегмента Т через а1(Г) обозначается под алгебра в (Р*(2<и;), порожденная элементами вида T[F]*, где F — конечное подмножество 2 < и \ Справедливо следующее утверждение: если v : N —> 5$ — нумерация булевой алгебры 53 и Т = { al(T), есте ственным образом связанную с нумерацией конечных подмножеств 2<ш. При этой нумерации операции на al(T) задаются вычислимыми функци ями на номерах элементов, a v^ 1{QB\{T)) € Е£ (П£, Д£), если Т £ П£ (Е°, Д°). В частности, если Т — вычислимое множество, то булева алгебра al(T) имеет рекурсивное представление. Для каждого а е 2<ш зададим элемент a G 2<ш. Пусть Л = Л, а * 0 = = а * 00, а * 1 = а * 01. Если каждому г £ 2 < w сопоставлен нормальный сегмент Д г , то под произведением будем понимать нормальный сегмент
^~ 11 ^г' rG2< w
такой, что а е R <==> a = rV
Е^-предложение.
Тогда равномерно п о Ф к Ф можно найти П^„3"формулу 6, выделяющую в 2<и} некоторый нормальный сегмент S, причем если 21 ~ al(T), 53 = al(5) и I <\ 53 — идеал Ерьиова—Тарского булевой алгебры 55, гао
182
С. Ю. Подзоров i)2l = * / i ; 2) если N (= Ф; mo в 03 wera элементов характеристики (0,оо,0);
если N ^ Ф, т о (Уж € ®)(chi(a?) > 0 -> (Зу G ®)(у ^ ж & ch(y) = = (0,оо,0))) и (Уж е »)(ch(s) = (0,оо,0) -> (Зу 6 » ) ( у < ar k ch(y) = (0,ос,0) &сЬ(ж\ у) = (0,оо,0))). ДОКАЗАТЕЛЬСТВО. Пусть Г — нормальный сегмент, выделяемый П^-формулой Ф. Согласно [7, §4], существует П^_3-предикат
P(Ti'miz)i
вычисляемый эффективно по Ф, для которого 1) фТ = {m : (3z)P(r, ra, z)} — непустой начальный сегмент нату рального ряда; 2) г
еТ^(3°°а^т){ф(ТфЩ.
Отношение (Уг < Z)-IP(T, m, г) является Е^_3-отношением. Значит, D'{T, га, z) = Р{т, m, z) к (Уг < *)-iP(r, га, г) = (Уя)Р'(т, га, г, ж) & (Зж)Р"(г, га, г, ж), где Р ' и Рп — Е°_ 4 - и П£_4-отношения. При п > 3 полагаем D(r, га, г, *) = (Уж < t)P'(r, га, *, ж) & (Зж ^ г ) ^ " ( ^ m> г> ж)> Q(r, га, z, t) = (Vs > t)D(r, m, z, 5) & [(t = 0) V -i£>(r, ra, z, t - 1)]. При тг $J 3 полагаем Q ( r , m , z , t ) = P ( r , r a , z ) & (Уг < г)^Р(г,га,г)& (t = 0). Пусть Qr = {(ra,z,£) : Q ( r , m , 2 , i ) } . Следующие свойства проверя ются непосредственно (свойства 1—4 имеют смысл лишь при п > 3): 1) D(r, ra,z,£) — Д°_3-отношение, Q(r, ra, z,t) — П£_3-отношение, Qr — П£_ 3 -множество; 2) га G Vv => (3\z)Df(r)mJz)}
m # фт =» ->(32:)1)'(г, ra,z);
3) £>'(r,ra,z) => (3t0)(Vt > i 0 ) £ ( r , m , 2 , t ) , -"Г>'(т,га,2г) =» (3f0)(Vt ^ ^ t 0 )"'I>(r,ra,z,t); 4) D'(r,ra,2f) =» (3!t)Q(r,m,*,t), -n£>'(r,ra,z) => -i(3t)Q(r,m,2,t); 5) Q r бесконечно <=> Vv = N.
Рекурсивные однородные булевы алгебры Аналогично преобразуем и предложение Ф. Имеем Ф =
183 (Зх)(\/у)
(3z)R(x} у, г), где R £ П°_ 3 - П У СТЬ ft = {m : (Зх <: *)(Vy <
m)(3z)R(x,y,z)}.
Справедливы следующие утверждения: 1) Rt — непустой начальный сегмент натурального ряда; 2) t\ $С #2 =^ Д«1 Q Л* 2 5
3) N |= Ф <^ (3t)(H* = N). Кроме того, ft € £^_ 2 и существует Pi(i,m,2?) E П°_35 дая которого ft = {щ : (3z)Pi(t,m)z)}.
Аналогично предыдущему,
D[ (i, m, г) = Pi (*, m, г) & (Уг < z)-*Pi (t, га, г) = (Уж)Р{(«,т,2г,я;) & (3a)fY(t,m,z,s), где Р[ и Р " — S^_4~ и П°_4-отношения. Определим отношения: — при п > 3 полагаем D i ( t , m , 3 , s ) = (Уж ^ s)P{(£, m,z, #) к (Зх ^ ^ / ^ ' ( т ^ т ^ ж ) , Qi(t, ra,2?,s) = (Vw ^ s)Di(t,m,z,u)
к [(s = 0) V -iDi ( i , m , z , s - 1)];
— при n ^ 3 полагаем Qi(*,m,*,$) = Pi(i,m,z) & (Уг < *)-»Pi(£,m,i) & (5 = 0). Пусть Q\ = {(га, г,5) : Qi(£, ra,z, s)}. Так же, как и в предыдущем случае, можно показать, что Q\ — это П£_3-множество, а также, что Q\ бесконечно в том и только в том случае, если ft включает в себя все натуральные числа. Определим теперь нормальный сегмент 5 . Для т, о 6 2 < w полагаем Lr
=
{е G 2<" : (Уг ^ |е|)(е,- = 1 —• % G Q r ) } ,
М^
=
{e62<w:(Vi^|e|)(e,- = l — > t e Q j ; | U Q T ) } ,
Mr
=
П<г€2<*> М г,<г,
Vr
=
{1 * £ : e e 2
Наконец, пусть
5= n vт£2<ш
184
С. Ю. Подзоров Ясно, что S — П£_3-сегмент и что П£_3~Ф°РмУла> выделяющая 5 , на
ходится эффективно по Ф и Ф. Покажем, что 5 удовлетворяет требуемым свойствам. Сначала заметим, что выполняются следующие соотношения: 1) S[{T * 11}]* является безатомным в al(5); 2) S[{r* 100}]* является безатомным в al(5) при фт = Ми представим в виде объединения конечного числа атомов при фт ф N; 3) элемент 3[{т * 101}]* алгебры al(5) является: (a) безатомным, если фт = N; (b) либо безатомным, либо объединением безатомного и конечного числа атомов, если фт ф N и N (= Ф; (c) атомным, характеристики (0, оо, 0), обладающим свойством: когда элемент х лежит под этим элементом и сЬ(ж) = (0, ос, 0), то найдется у ^ х, для которого ch(i/) = (0,оо,0) и ch(x \у) = (0, оо,0), если ^
г
^ и М ^ Ф .
Действительно, введем следующее определение: выделенным эле ментом сегмента S будем называть a £ 5, для которого выполняются (Vefc=а)(\/6 > а) (г е 5 & « е 5 - 4 e ^ < 5 v H e ) и (Ve^ <т)(е = а V (35 ^ ^= £)(£ £ 5 & S ^ • г £ Q)} равно 2^1, если Q конечно, и равно нулю в противном случае. Опираясь на эти три соотношения, можно установить следующие факты: 1) т £ Т => S[{?}]* не разбивается на объединение атомного и без атомного элементов алгебры al(5); 2) т $ Т => 5[{г}]* является объединением атомного и безатомного элементов алгебры al(5). Поэтому S[F]* не является элементом идеала Ершова—Тарского булевой алгебры al(5) в том и только в том случае, когда (За £ F)(a £ 5'), где 5 ' - {г : г £ Г} U {г * 0 : г £ Г } . В силу al(S') = al(T) выполняется первое свойство леммы. Второе свойство можно получить из доказанных выше соотношений,
Рекурсивные однородные булевы алгебры
185
если заметить, что под любым элементом вида 5[{г}]* или S[{f * 0}]* для г £ 2 < w содержится безатомный. П С Л Е Д С Т В И Е 1. ПустпъТ С 2<w — нормальный Tl^-сегмент. Рав номерно no T моснсно найти нормальный П%_3-сегмент 5, обладающий следующим свойством: если % ~ а1(Г), 25 = al(5) и I <3 25 — идеал Ершо ва—Тарского булевой алгебры %$, то
1)аз*Д; 2) в 55 к е т элементов характеристики (0,оо,0). Л Е М М А 3* Пусть Т С 2 < w — нормальный сегмент, в 2
выделяемый
некоторой U^-формулой Ф. Равномерно по Ф можно найти П^_ 4 -
формулу в, выделяющую в 2
0 -» (Зу G » ) ( y ^ ж & ch(y) = (0,оо,0))) u (Va? 6 ®)(ch(a) = = (0,oo,0) -» (Зу е ®)(у < a: & ch(y) = (0,оо,0) & ch(x \ у) = (0,оо,0))). ДОКАЗАТЕЛЬСТВО. Пусть Т — нормальный сегмент, выделяемый П° -формулой Ф. Без ограничения общности можно считать, что под каж дым элементом о сегмента Т найдется г £ 2<ш такое, что г 0 Т. В против ном случае достаточно рассмотреть сегмент Т1 = {а : о Е Т} U {а * 0 : а Е е Г } ; очевидно, что al(T') = al(T). Согласно [7, §4], существует Е°_ 4 -предикат Pi(r, m,y,z),
вычисляе
мый эффективно по Ф, для которого 1) фт = {ш : (3y)(V;z)Pi(r,m,y, z)} — непустой начальный сегмент натурального ряда; 2) т 6 r ^ ( 3 ° ° ( 7 ^ r ) ( ^ ^ N ) . Для каждого а: Е N определим непустой начальный Е^_3-сегмент натурального ряда: Ст,х = {m : (Vu < m)(32:)-iPi(r,ar,tt,2r)}.
С. Ю. Подзоров
186
Если х Е фт) то с г?х ф N, а если ж ^ ^ г , то сГ)я = N. Пусть сг,* = {™ : (Эз)Р(г, х, т , г)}. Так же, как и раньше, положим D'(r, ж, т , 2:) = Р(г, ж, т , г;) & (Уг < z)-iP(r, ж,га,г) = (Vy)P;(r,a;,m,2:,2/) & (Зу)Р"(г,ж, га, г, у), где Р ' и Р " — это S^_ 5 - и П£_5-отношения. Определим: — при п > 4 полагаем D(r, ж, m, z, *) = (Уу ^ *)Р'(Г>х> т > *> У) & (3У < *)^'( r > xi ш> z. У)» <2(т,ж,т, я,*) = (Vs ^ i)D(r, ж,га, г, s) & [(£ = 0) V -гО(г, ж, га, z,i - 1)]; — при п ^ 4 полагаем Q(r, ж, ra, 2, t) = P(r, ж, т , г) & (Уг < Z)-^P(T,
Ж, т , г) Sz (t =
0).
Пусть Q r ^ = {{га, г, £) : Q(r, ж, га, z, t)}. Тогда непосредственной про верке поддаются следующие свойства (свойства 1—4 имеют смысл лишь при п > 4): 1) £>(т, ж,га, 2,£) — Д£_4-отношение, Q(r1 x,m,z,t)
— П^_4-отноше-
ние, QTX — П^_4-множество; 2) га £ cTiX => (3!z)D'(r, ж,га,2), га g cT}X =» -i(3z)Df(r, ж, га, 2); 3) D'(T,xym,z)
=> (3t0)(V* ^ t 0 )i?(r,«,m,z,*), -iD'(r,&,ra,2r) => (3t 0 )
4) D'(Tyx,myz)
=> (3!*)Q(r,a:,m,z,*), ~^D'(T, Ж, m, г) =» -i(3*)Q(r,a;,
ra,;z,t); 5) Qr,x бесконечно <=> cr>x — N. Определим нормальный сегмент 5. Для г,<тб 2<ш положим Мт><т - { е е 2<" : (Vi ^ |в|)(е, = 1 —• t € Q T l W )} , v
r = П«ге2«*
м
^-
Наконец, пусть
5= П ^т£2<ш
Рекурсивные однородные булевы алгебры
187
Ясно, что 5 является П°„4~сегментом и что П^__4-формула, выде ляющая 5, находится эффективно по Ф. Покажем, что S удовлетворяет требуемым свойствам. Так же, как и в предыдущей лемме, заметим, что элемент S[{r * 1}]* будет 1) объединением безатомного элемента и конечного числа атомов, если фт ф N; 2) элементом характеристики (0,оо,0), если фг = N, причем для х £ £ al(5), лежащего под этим элементом и такого, что ch(#) = (0,оо,0), найдется у ^ х такой, что ch(y) = (0,оо,0) и ch(x \ у) = (0,оо,0). Опираясь на эти свойства, получаем следующие утверждения: 1) г 6 Т => 5[{?}]* не разбивается на объединение атомного и без атомного элементов алгебры al(5); 2) т 0 Г => 5[{г}]* является объединением атомного и безатомного элементов алгебры al(5). Тогда для Sf ^= {т : chi(S[{r}]*) > 0} имеет место S' = {г : г Е Т} U U{r * 0 ; г £ Т } . Первое свойство очевидно, поскольку al(S') = al(T). Вто рое тоже, так как если для х Е al(5) выполняется ch(x) = (0, оо, 0), то под х найдется элемент у характеристики (0,оо,0), лежащий под элементом вида S[{T * 1}]*; кроме того, под любым элементом с ненулевой первой характеристикой найдется элемент вида 5[{т}]*, где т £ Т. О Т Е О Р Е М А 2. Если *В — однородная булева алгебра с бесконечной первой характеристикой и М(5$) £ Ф(+оо,3), то Ъ допускает рекурсив ное представление. ДОКАЗАТЕЛЬСТВО. Если М ( » ) коконечно, то алгебра Ш разреши ма. Пусть М(*В) кобесконечно. Пусть М(Ш) £ Ф(а,3) для а £ Z. Покажем, что в этом случае 2J допускает рекурсивное представление. Согласно предложению 1, для каждого п £ N существует S2+3n+i~ предложение Фп, вычисляемое эффективно по п, для которого N (= Фп <=> ^ п б М(95). Пусть к настолько велико, что множество {п 0 М(*В) : п < к} содержит не менее (а + 1)-го элемента.
С. Ю. Подзоров
188
Для каждого п Е N и для г ^ п определим нормальный сегмент Sn,i так, что 1) если множество {т $ М(<8) : т < minjfc, п — г}} состоит из 5,элементов, то S nj ; является П ^ ^ . . -сегментом; 2) если *8П = al(5 n , n ), то ch(S8n) = (гс, 1,0) и для 5 < п (a) при 5 G М(<В) в 93п нет элементов элементарной характеристики (5,оо,0); (b) при 5 ^ М(2$) выполняются утверждения i) для любого х G © п такого, что chi(a:) > 5, найдется у ^ ж, для которого ch(y) = (5,00,0); И) для любого х £ *ВП такого, что ch(x) = (5,00,0), найдется у ^ ж, для которого ch(y) = (5, 00, 0) и ch(ar \ 2/) = (5, оо, 0). Для каждого п 6 N определим 5П?,- индукцией по г. 1) Положим 5„,о = {еЕ 2 < u ; : (Vi ^ |е|)(бг,- = 0)}. 2) Пусть 5П|« определено и г < п. Возможны три случая: (a) Пусть i < п - к. Тогда S{ = 5,+i ^ a + 1. Предложение Ф п _, является Ез/п_3)4-5 " П Р е А Л О Ж е н и е м ' ^
нем
У
и
сегменту 5 n , t можно приме
нить лемму 2; пусть S„jt-+i — нормальный сегмент, существование которого утверждается в лемме 2; (b) Пусть i^n 5П,«Ч1 ~
это
— кип
— i — 1£ М(<8). Тогда s, + 1 = s l + i- Пусть
нормальный сегмент, который существует для Sn^ в силу
леммы 3; (c) Пусть г ^ п — к и п — г — 1 Е М(*В). Тогда 5,- — 5 J + i. Пусть 5 n ^+1 — это нормальный сегмент, который существует для SfM в силу следствия 1. Указанные выше свойства проверяются индукцией по г, непосред ственно из определений. Рекурсивное представление булевой алгебры 58п находится эффективно по п. Пусть Ln — рекурсивный линейный порядок, порождающий булеву алгебру *ВП [5, § 1.6, § 3.2]. Пусть L — LQ + L\ + ... и - о о — наименьший элемент в L. Линейный порядок L рекурсивен. Пусть г] — плотный рекур сивный линейный порядок с наименьшим элементом, но без наибольшего
Рекурсивные однородные булевы алгебры
189
элемента. Рассмотрим рекурсивные линейные порядки
Пусть th(S) = (®,р)- Покажем, что для i ^ 3 булева алгебра 21,*, построенная по рекурсивному порядку I / , относительно плотная [5, §2.3], ch1(a,-) = ooHt h (Sli) = <*>P>. Пусть i = 1. В алгебре 211 единичный элемент, равный L, имеет беско нечную первую характеристику, так как он содержит все элементы Ln ха рактеристики (те, 1,0). Для любого / £ L первая характеристика элемента [-ос, /) конечна, поэтому для х £ 2li либо chi (ж) < оо, либо chi {C(x)) < оо. Если для х £ 2li либо chi (ж) > ™? либо ch(ar) = (те, оо, 0), то ниже х найдет ся элемент вида [а, 6), где а £ L m , Ь £ £ m U L m +i и m > те. В этом случае те ^ М(2$) и под х имеются два непересекающихся элемента характеристи ки (те, оо,0). Пусть г ~ 2. Этот случай очевиден, так как 212 — 2ti X 2tiПусть г = 3. Бесконечность первой характеристики и условие отно сительной плотности, касающееся элементов вида (те,оо,0), проверяются так же, как в случае г = 1. Кроме того, если chi (ж) = оо для х £ 21з> то под х найдется элемент вида [(/], gi), (l2, г А е Чг < Ч2\ тогда х разбивается на два непересекающихся элемента бесконечной первой характеристики. • Таким образом, класс множеств, являющихся инвариантами Моро зова рекурсивных однородных булевых алгебр, лежит где-то между уров нями Ф(+оо,3) и Ф(—оо,4) иерархии Фейнера. Дать более точное алго ритмическое описание этого класса пока не представляется возможным. Интересен вопрос о том, насколько вообще возможно такое описание. Если мы хотим, чтобы класс множеств Л допускал алгоритмическое описание, то от него естественно потребовать замкнутость относительно рекурсивных перестановок, конечных сдвигов, по модулю конечных мно жеств и т.п. Классы иерархии Фейнера обладают только третьим свой ством. Из результатов этой статьи можно вывести, что класс инвариантов Морозова рекурсивных булевых алгебр не будет замкнут относительно ре курсивных перестановок. А если этот класс замкнут относительно конеч-
С. Ю.
190
Подзоров
ных сдвигов, то тогда к а ж д а я арифметическая однородная булева алгебра является рекурсивной, что кажется достаточно маловероятным. Однако, классы иерархии Фейнера Ф(+оо, 3) и Ф(—оо,4) замкнуты относительно конечных сдвигов. В силу этого справедливы следующие аналоги теорем 1 и 2: Т Е О Р Е М А 1'. Пусть *В — однородная арифметическая гебра с бесконечной
первой характеристикой.
тическое
ал
Тогда М(*8) € Ф(—оо, 4).
Т Е О Р Е М А 2'. Если Ъ — однородная булева алгебра с первой характеристикой
булева
бесконечной
и М(2$) Е Ф ( + о о , 3 ) ; то *В допускает
арифме
представление.
Теорема 2' является прямым следствием теоремы 2. Формальное до казательство теоремы 1' опирается на предложение 1. Интересным представляется также вопрос: при каких а и /3 булева алгебра с типом однородности (а,р)
будет рекурсивна, если рекурсивна
алгебра с типом однородности (f3,p)r! Д л я а,/3 = 1,2 ответ очевиден; д л я а = 3 и / 3 = 1,а также а = 1 и /3 = 3 ответ на данный момент неизвестен. В заключение автор выражает благодарность С. С. Гончарову за по становку проблемы и интерес, проявленный к работе.
ЛИТЕРАТУРА 1. А. С. Морозов, Счетные однородные булевы алгебры, Алгебра и логика, 2 1 , N 3 (1982), 269-282. 2. L. Feiner^ Hierarchies of Boolean algebras, J. Symb. Log., 35, N 3 (1970), 305— 373. 3. С. П. Одинцов, В, Л. Селиванов, Арифметическая иерархия и идеалы нуме рованных булевых алгебр, Сиб. матем. ж., 30, N 6 (1989), 140—149. 4. S. Yu. Podzorov, Arithmetic complexity of first-order definable subsets of recursive Boolean algebras, Sib. Adv. Math., 8, N 1 (1998), 141—150. 5. С. С Гончаров, Счетные булевы алгебры и разрешимость, Новосибирск, Научная книга (НИИ МИОО НГУ), 1996. 6. X. Родоюерс, Теория рекурсивных функций и эффективная вычислимость, М., Мир, 1972.
Рекурсивные однородные булевы алгебры
191
7. А.Н. Lachlan, On the lattice of recursively enumerable sets, Trans. Am. Math. Soc, 130, N 1 (1968), 1-37. Адрес автора: ПОДЗОРОВ Сергей Юрьевич, РОССИЯ, 630090, г. Новосибирск, ул. Пирогова, д. 20/1, к. 304-3. e-mail: [email protected]
Поступило 30 августа 1999 г.
