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

Алгебра и логика, 39, N 6 (2000), 711-719

УДК 510.5

ОПРЕДЕЛИМОСТЬ БУЛЕВЫХ АЛГЕБР В ^-НАДСТРОЙКАХ** А.В.РОМИНА Введение

В последнее время широкое распространение получили исследова­ ния по вычислимости для абстрактных типов данных. С этой точки зре­ ния особый интерес представляет понятие определимости в наследственноконечных надстройках, поскольку в последних хорошо интерпретиру­ ются все известные способы построения новых данных. Кроме того, наследственно-конечные надстройки являются наименьшими допустимы­ ми множествами над моделью». В рамках подхода S-определимости, введенного Ю.Л.Ершовым, в данной работе изучается определимость булевых алгебр и их рангов Фре­ ше в наследственно-конечных надстройках. Строятся примеры суператом­ ной булевой алгебры, ранг Фреше которой не является Е-определимым в наследственно-конечной надстройке над ней и допустимого множества, в котором безатомная булева алгебра не является автоустойчивой.

§ 1. Предварительные сведения В настоящей работе рассматриваются только счетные модели конеч­ ной предикатной сигнатуры» Поскольку речь, как правило, будет идти о *^ Работа выполнена при финансовой поддержке Федеральной целевой программы ^Интеграция", проект 274, и Российского фонда фундаментальных исседований, проект N 99-01-00485. ©

Сибирский фонд алгебры и логики, 2000

712

А. В. Ромина

булевых алгебрах, напомним несколько определений и обозначений, от­ носящихся к булевым алгебрам. Все остальные необходимые сведения о булевых алгебрах можно найти в [1]. В [1] определяются естественный порядок на булевой алгебре а < b <-» f-> a U Ь = Ь и идеал Фреше. Следуя принятым там обозначениям, через Fa{S&) обозначается а-й итерированный идеал Фреше алгебры 21. В даль­ нейшем, если из контекста ясно, о какой алгебре идет речь, будем исполь­ зовать выражение Fa вместо F a (2l). ОПРЕДЕЛЕНИЕ 1. Рангом Фреше булевой алгебры 21 называется первый ординал /)(21) = а такой, что Fa = F a +iИзвестно, что ранг Фреше суператомной булевой алгебры являет­ ся непредельным ординалом и в фактор-алгебре 2l/Fp(gi)_1(2l) содержится конечное число атомов [1]. Типом суператомной булевой алгебры называ­ ется пара т (21) = (а, га), где р(21) = а + 1 и т - число атомов в 2 l / F a . Известно, что счетная суператомная булева алгебра определяется своим типом с точностью до изоморфизма [1]. ОПРЕДЕЛЕНИЕ 2 [1]. Если 21 - алгебраическая система и ! С |21|, то наименьшую подсистему, содержащую множество X, назовем подсисте­ мой, порожденной множеством X, и обозначим gr(Jf). Говорят, что X — множество, порождающее 21, если gr(X) = 21. ОПРЕДЕЛЕНИЕ 3 [1]. Линейно упорядоченным базисом булевой ал­ гебры 21 называется линейно упорядоченное подмножество L, порождаю­ щее 21, такое, что 1 ^ L и О G L. Известно, что каждая счетная булева алгебра имеет линейно упо­ рядоченный базис и изоморфна его алгебре полуинтервалов. Более того, каждая конструктивизация конструктивной булевой алгебры эквивалент­ на конструктивизации алгебры полуинтервалов некоторого конструктив­ ного линейно упорядоченного множества [1]. Теперь рассмотрим понятия, касающиеся вычислимости в допусти­ мых множествах. Допустимые множества будем рассматривать в расши­ ренной сигнатуре а9 = a U {U, 5, £}, где а — исходная сигнатура модели, лежащей в основании допустимого множества. Определение допустимых

Определимость булевых алгебр в Ш¥-надстройках

713

множеств и все необходимые сведения о них содержатся в [2, 3]. ОПРЕДЕЛЕНИЕ 4 [2]. Пусть А - допустимое множество, ЯЛ = (М; (P"*)*
— предикатные символы местности щ.

Модель ЯЛ является Yt-определимой в А, если существуют Е-формулы (p(x)ji?o(xQyxi)i'ipo(xo1xi)i^i(x)^i(x)1

где ^(ж), ф{(х) зависят от щ пере­

менных, такие, что фо определяет отношение эквивалентности на у?А[ж], N = (fA[xl N2 \ ф£[х] = ЛГ2 П г^о Л И, iVni \ ф*[х] = iVn> П ^ / [ ж ] и модель (iV/^o; (#"•" П Vi4*])M>> изоморфна ЯЛ. ОПРЕДЕЛЕНИЕ 5 [2]. Если в предыдущем определении формула фо задает отношение равенства, то ЯЛ называется однозначно Неопредели­ мой в А, ОПРЕДЕЛЕНИЕ 6 [2]. Пусть задано некоторое семейство 5. Тогда А-нумерацией семейства 5 называется любое частичное отображение v : А —> 5, являющееся отображением "на". Пусть заданы модель ЯЛ = (М; (Р?*){<к), где Р/ 4 — предикатные символы местности щ, и А-нумерация i/ модели 97t = (М; (P«-)«
если существует Е-предикат Д(аг,у) и ав­

томорфизм <р модели ЯЛ такие, что UQX(M)

С 8R & V(x,y) Е Д {х Е

Е z^ a (M) <-» (у Е / / ^ ( М ) & ^о(я) = ^ ( ^ ( У ) ) ) ; В ЭТОМ случае используется обозначение (ЯЛ, щ) « (ЯЛ, i^i).

714

А. В. Ромина ОПРЕДЕЛЕНИЕ 9. Модель ЙЛ называется А-автоустойчивощ

если

две любые ее А-конструктивизации эквивалентны. Определения 8, 9 аналогичны определениям, относящимся к конструктивизируемым (в арифметике) моделям [4]. Определим, следуя [3], в допустимых множествах Е-функцию sp(x), выделяющую носитель х. ОПРЕДЕЛЕНИЕ 10. Определим индукцией по носителю х: 1) U(a) ->sp(a) = {a},

2)S(x)-+sp(x)

=

\J{sp(y)\yex},

где U и 5 — предикаты, выделяющие праэлементы и множества соответ­ ственно. Первый неконструктивный ординал, как и в [5], обозначим и\,

§ 2. Основные результаты Хорошо известны следующие факты: если модель конструктивизируема, то существует ее однозначная конструктивизация [4]; безатомная булева алгебра автоустойчива [1]; каждая конструктивная булева алгебра имеет конструктивизируемый линейно упорядоченный базис (например, [1]). Построим примеры допустимых множеств, в которых данные свой­ ства не выполняются. Существует допустимое множество, в котором безатомная булева ал­ гебра не является автоустойчивой. ПРИМЕР 1. Пусть в — конструктивизация гебры {являющаяся А-конструктивизацией

безатомной булевой ал­

для любого допустимого мно­

жества А [2]). Пусть 53 — абстрактная безатомная булева алгебра. То­ гда в и id<3 не эквивалентны в A — HF(93). ДОКАЗАТЕЛЬСТВО проведем методом от противного. Пусть R — это Е-предикат, определяющий эквивалентность конструктивизаций в и id<£. Поскольку нумерация id
= f будет Е-

функцией. Пусть {а,} — атомы булевой алгебры, порожденной носителем можества параметров, которые входят в Е-формулы? определяющие R.

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

715

Пусть х £ (0)~1 такое, что f(x) < аг для некоторого а;. Тогда для любого у < щ существует (р автоморфизм Ш, оставляющий а« на месте и такой, что (p(f(x)) = у. Следовательно, R(x,y),

и в конструктивизации в будет

много элементов с номером х. В общем случае из Е-определимости не следует однозначная Е-определимость. Т Е О Р Е М А !• Существуют допустимое мноэюество и Неопре­ делимая в нем модель такая, что последняя не является ^-определимой

однозначно

в этом множестве.

ДОКАЗАТЕЛЬСТВО. Пусть 9Л =

(M;P2,Q2),

где Q{x,y)

<+

«-> (Р(ж, у) & Р(у, ж)) — отношение эквивалентности с бесконечными смеж­ ными классами и (M/Q,P/Q)

=

(wi> <) (напомним, что u;f — первый

неконструктивный ординал). Тогда wf является Е-определимым, но не бу­ дет однозначно Е-определимым в ШГ(ПЛ), Очевидно, что u>J является Е-определимым в ШГ(ШТ). Предполо­ жим, что и\ однозначно Е-определим в HF(27t). Тогда существуют фор­ мулы <р(х) и ^ 2 (ж) (возможно, с параметрами из SDT) такие, что ЯЛ' = = {^(2Л),^(2Л) П (<р(ЯЛ))2) =

(^i»<); пусть С — множество констант,

входящих в эти формулы. Формулы конечны, поэтому С Е ШГ(2Л). Вве­ дем на 9Л отношение эквивалентности в 2 такое, что в(х} у) ++ (({х $ sp(C) & у £ sp(C) & Q(s, у)) V ж - у). Для любой пары (х? у) такой, что 0(#,у), существует автоморфизм / : ЯЛ --> Ш такой, что f(z) ~ z для всех г из sp(C), /(ж) = у и /(у) = ж. Для любого х существует бесконечно много у из М таких, что в (ж, у). Определим в* на ШГ(ЯЛ): 9*(#, у) тогда и только тогда, когда существует автоморфизм ШГ(ЯЛ) такой, что f(z) = £ для любого г из С, f(x) = у и /(у) = х\ На М отношения 0* и 0 совпадают. Из определения автомор­ физма следует: если ©*(#, у) выполняется для всех пар (ж, у) из ШГ(ЯЛ), то ((^(ж) f-> <,р(у))е Пусть существуют ж, у из HF(9Jl) такие, что 0*(ж,у) & ¥>(#), тогда у>(у), и из линейности порядка < на wf следует, что в НЕ(ЯЛ) вы­ полняется ф(х,у) или ф(у„х). Так как / оставляет С на месте, то для

716

А. В. Ромина

произвольной пары (z,t) из HF(2ft) выполняется ij)(f{z),f(t)),

если ф(г,Ь).

Поэтому из ф(х, у) следует ф(у, ж), а из ф(у, х) — ф(х, у). Так как ф2 задает порядок, то х = у. Легко заметить, что 0*(ж, у) влечет х = у тогда и толь­ ко тогда, когда sp(x) С sp(C). Таким образом, и\ определим в HF(sp(C)). С другой стороны, в HF(sp(C)) определимы только конструктивные орди­ налы [2]. Существуют допустимое множество А и Е-определимая в нем буле­ ва алгебра 21, не имеющая Е-определимого в А линейно-упорядоченного базиса, это показывает следующая Т Е О Р Е М А 2. Пусть 21 — суператомная булева алгебра. Пусть £ = (L; <) — линейный порядок, И-определимый в HF(2l). Тогда £ конструктивизируем. ЗАМЕЧАНИЕ 1. Пусть ЗЛ и 9Л' — модели одной сигнатуры, причем 91 определима в ОЛ формулами <р, фо, • • • с параметрами а £ М. 9

существуют b из М w

С M xM

/w

такой, что (9Л, а) = (ЯЯ',Ь), и отношение Т С

такое, чтоТ(х,у)

€ MHrfoyJ&fVy

6

Пусть

-> (2Л,а,х) = (9Л',Ь,у), (Уж Е M w )(3y <Е

M /U, )(3a 6 №)Т(х,у)

иТ(х,у)

->

Т{хиУ1),

причем 1) (Г(аг, у) & T(z', у) & v (x)) -+ Vo(x,*'), 2) (Т(х, у) & Г(х,у') & (*)) -> ШУ,
которые получаются из у>,фъ,... заменой а на Ь.

Действительно, рассмотрим /

С

<рм*[х]/ф'о х (рм [х]/ф0 со свой­

ством: два класса попадают в / тогда и только тогда, когда в них най­ дутся представители такие, что соответствующая пара попадает в Т (т. е. Т(х,у)

-> (х/фо,у/ф'0)

€ / ) . Тогда / — корректно определенное отобра­

ж е н и е и индуцирует требуемый изоморфизм. ДОКАЗАТЕЛЬСТВО теоремы 2. Пусть 21 — суператомная булева алгебра, £ — линейный порядок, Е-определимый в HF(2l), И Й - парамет­ ры, входящие в формулы, которые определяют £. Если 21 конструктивна, то порядок конструктивен. Пусть 21 не является конструктивной. Тогда

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

717

не конструктивен ее ранг Фреше. Значит он больше и + 2. Рассмотрим алгебру *8 = *Bu,w+2. Пусть S — множество атомов конечной алгебры, по­ рожденной sp(a). Рассмотрим частичный изоморфизм / : 21 -» *В такой, что (т(х) = r(f(x))

V (р(ж) > <J + 1 & p(f(x))

> u + 1))) для всех я из

5 . Продолжим / до частичного изоморфизма /* : НИР(21) -» HF(*B) сле­ дующим образом: 8f* = {,т | sp(s) С (£}, / С /*, / сохраняет отношение принадлежности, где С — алгебра, порожденная носителем а. Полагаем

Ь = Г(а). Полагаем, что выполняется Т{х,у) тогда и только тогда, когда су­ ществует конечный частичный изоморфизм g : HF(2l) -» HF(5B), для ко­ торого (V/i e 5gf) A{{r{h) = r(g(h)) V (p(h) > ukp(g(h)) CSg)k(g(a,x)

> u)))) & (а С

= (b,y)).

Покажем, что (HF(2l),a, x) = (HF(5J),6, у). Доказательство этого факта практически полностью повторяет доказательство из [6]. Индук­ цией по га можно показать, что (ШГ(21),ж) = г о (EF(*B),y), если суще­ ствует частичный изоморфизм / : HF(2l) -» HF(9J), для которого r(h) = = r(f(h)) V (p(/i) > га & />(flf(fe)) > га)) при всех h из 5 / П А. Пусть Т(я, z) &; Т(у, г) & <£(ж), тогда фо(х1 у). В самом деле, рассмо­ трим атомы конечной алгебры (£, порожденной sp(a). Пусть So — {щ \ ai ~~ атом € и р{щ) < w}, а 5i — атомы С, не попавшие в 5о, и G So, ж,,уг — атомы алгебр, порожденных sp(a?) U sp(a),sp(y) U sp(a) под и, такие, что (#0~ 3 о у : х{ н-^ у,-, где у и у' — соответствующие частичные изоморфизмы в определении Т. Тогда г(ж^) = т(у{). Пусть Cij = ж,- П yj. Покажем, что существуют последовательности х°, х1,...

, ж т и у 0 , у 1 , . . . , у т , для которых выполняется (г(ж* П #j + 1 ) =

= r ( x } n x f + 1 ) k r ( y ? n » J + 1 ) = r(yf Пу? +1 ) & *? = s'i & y? - y,-) & ф ™ П HyJ1) = r ^ J " П ж™) при всех i,j,&. Будем строить эти последовательно­ сти по индукции. Обозначим: с\- = ж^ П yjf. Пусть ж*, у* уже построе­ ны, и (г, j)

— первая (в лексикографическом порядке) пара такая, что

r(xf П у^) т^ г ( ж ? П yf). Без ограничения общности можно считать, что т €

( п) > r ( c i*)- Пусть г0 = min {г, j } . Найдутся г ; 0 + ь r t - 0 + 2 ,... , и такие, что

718 Г

Р <

А. В. Ромина, C

pi &

U

<

C

tf & T(Cf; \

и

) =

T C

( )i)

&

T

(Urp) =

Г

(^) Д Л Я

ВСеХ

Р-

Полагаем 4 + 1 - 4 U t*f cf/1 - с% \ и, скр+1 = с*. \ г р & c j / 1 - с& U г р для всех р, у£ +1 = Ucph1****"1 = U ^ p 1 Д л я р

всех h

- Нетрудно прове-

р

рить, что т(х1? П s* +1 ) = т(х) П ж*+1) & r(t/f П y^ +1 ) = r ( y | П у*"1"1) для всех г, j и г(ж* +1 П У*+1) = т(хк+1 П rj/* +1 ) для всех г, j ^ г0. За конеч­ ное число шагов эта последовательность будет построена. Проделаем дан­ ную процедуру со всеми элементами So. При этом строим отображения fk : ж* и-> ж х " н , у& • У? •-> Vi*11 продолжаем их до частичных изомор­ физмов /£,#£ соответственно, и полагаем xk+l = /fc(#fc),yfc+1 = fk(yk)- То­ гда < Щ а ) , а , ^ я * + 1 ) > = (НР(Я),а,(х* +1 ,ж л )> и (HF(2l),a, (yfc, y fc+1 )) ~

Рассмотрим 5 из 5i и атомы алгебры, порожденной множеством sp(a) U &p(x) U sp(y) под s. Если p(s) > и + 1, то среди них есть хотя бы один, для которого р(с) > и) + 1. Пусть {х{} — атомы алгебры, поро­ жденной множеством sp(a) U sp(x) под § , и с < ж0- Выберем ж£ так, чтобы 4<сЬ

((r(xj) - r(*f-) & ,(*,-)

<

a;) V (р(хг) > и к т(х$ = (w, 1)))

при i ^ 0 и XQ = 1 \ ((J ж,-). Рассмотрим отображение / : ж,- н #(• и частичный изоморфизм /*, продолжающий / . Пусть ж' — /*(ж). Нетрудно заметить, что (HF(2l),a, (ж, ж')) = (HF(2l),a, (ж', ж)). Если с < у0 (образ х0 при соответствующем отображении), то оставляем все неизменным. Пусть с < у\ (достаточно подходящим образом перенумеровать жг- и у г ). Пола­ гаем у[ == a?J при % £ {0,1} и yt- = х[_{ в противном случае. Аналогично определяем у'. Тогда (HF(Sl), a, (у, у7)) =
ha,(x\xl+l))

=

(mW,a,(xl+\z%

(ш | (а) 1 аЛу' 1 у |+1 )> = <БГ(а),аДу|+1,у/)>, (HF(2t),a,(y / o ,^)) = (HF(2l),a,(^,y / o )). Следовательно, ^ 0 ( ^ , х / + 1 ) & фо(х1°,у1°) & ^о(у'?!/' +1 )- Значит, Утверждение теоремы немедленно следует из замечания 1.

ф0(х,у).

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

719

С Л Е Д С Т В И Е 1. Существует суператомная булева алгебра 21 та­ кая, что ее ранг Фреше не является Е -определимым в HF(Ql). Приведем пример результата, который удалось обобщить из обычной теории рекурсии на произвольные допустимые множества: ПРИМЕР 2. Пусть А — произвольное допустимое множество и £ — некоторый Е-определимый в А линейный порядок. Тогда алгебра по­ луинтервалов £©£ тоже ^определима

в А.

Это справедливо, поскольку ®£ будет Е-определима в HF(£). Нетрудно заметить, что суператомная булева алгебра, имеющая Е-определимый в А ранг Фреше, также Е-определима в А. Автор выражает благодарность своему научному руководителю С» С, Гончарову за постановку задачи и существенную помощь в работе. ЛИТЕРАТУРА 1. С» С Гончаров, Счетные булевы алгебры и разрешимость, Новосибирск, Научная книга (НИИ МИОО НГУ), 1996. 2. Ю. Л. Ершов, Определимость и вычислимость, Новосибирск, Научная кни­ га (НИИ МИОО НГУ), 1996. 3. J. Barwise, Admissible sets and structures, Berlin, Springer-Verlag, 1975. 4. Ю. Л.Ершов, Проблемы разрешимости и конструктивные модели, М., Наука, 1980, 5. X. Роджерс, Теория рекурсивных функций и эффективная вычислимость, М., Мир, 1972. 6. И. А. Кирпотина, Элементарная эквивалентность в языке списочных над­ строек, в сб. 'Теория вычислений и языки спецификаций" (Вычислитель­ ные системы, 139), Новосибирск, 1991, 26—37.

Адрес автора:

Поступило 5 мая 1999 г.

РОМИНА Анна Валерьевна,

Окончательный вариант

РОССИЯ, 630090, г. Новосибирск, ул. Пирогова, 2, Новосибирский государственный университет.

8 июня 1999 г.