Алгебра и логика, 39, N 2 (2000), 198—205
УДК 510.5
АВТОУСТОЙЧИВОСТЬ ГИПЕРАРИФМЕТИЧЕСКИХ МОДЕЛЕЙ*) А. В. РОМИНА
§ 1. Предварительные сведения В работе рассматривались только счётные модели конечной пре дикатной сигнатуры. Все необходимые сведения можно найти в работах [1-4]. Пусть имеется кортеж натуральных чисел п = (по, г н , . . . , rtk) и ну мерация р. Через v(n) обозначим (^(гао, )v(n{),...,
^(п^)). Известно, что
и<ш 6 HYP (и<ш — множество всех кортежей натуральных чисел, HYP — допустимое мнгожество HYP (о;). ОПРЕДЕЛЕНИЕ 1. Модель 9Л = структивизпруемой, {(x,y)\v(x)
(М\Р?)
называется
А{-кон-
если существуют нумерация и : и -> М такая что
= v(y)} 6 Д} и {х | Pi(u(x))} G Д{. При этом v называется
А\-конструктивизацией
модели 9JT, а пара {9Л, и) —
А\-конструкгпивной
моделью, ОПРЕДЕЛЕНИЕ 2. Две Д}-конструктивизации щ и z/i Д*-конструктивизируемой модели Ш называются А\-автожвивалентнымщ
если су
ществует гиперарифметическая функция / : и —> CJ И автоморфизм у> модели 9Л такие, что Ух((р(щ(х)) = &ч(/(ж))). Д}-конструктивизируемая модель называется Д}-автоустойчивощ если любые две ее Д*-конструктивизации Д|-автоэквивалентны. *) Работа выполнена при поддержке Федеральной целевой программы "Интеграция" и межвузовской научной программы "Университеты России".
©
Сибирский фонд алгебры и логики, 2000
Автоустойчивость гиперарифметических моделей
199
Напомним несколько определений из [5]. ОПРЕДЕЛЕНИЕ 3. Зададим по индукции кваншорный ранг формул языка ""цл ,ц» * 1) если <р — бескванторная, то qr ((f) = 0; 2) если <р = -r^&qr (ф) = а, то qr (ф) = а; 3) если <р = Qxi/)(x), где Q — квантор и qr (^>) = а, то qr (<£>) = а + 1; 4) если у> = V,- Ф% и л и V — Л * Ф%<> т о Яг {Ф) — SU P (Qr W>i)) (коньюнкции и дизъюнкции могут быть как конечными, так и бесконечными). ОПРЕДЕЛЕНИЕ 4. Будем говорить, что JOT = а % если для всех формул кванторного ранга ^ а выполняется 2Л \= <р f-» 91 f=
w € м<ш((т,х) =а (an,г') -> (ют,i) = a + 1 (ая,г'))ОПРЕДЕЛЕНИЕ 6. Рангом Скотта модели 2Л (обозначим: sr(JOT)) назовем первый ординал а, который не меньше ранга любого из кортежей из M<w (sr (JOT) ^ sup {г(ж) | .х G М < а ; » . Напомним несколько определений и обозначений, относящихся к бу левым алгебрам. Все необходимые сведения о булевых алгебрах можно найти в [1]. Там же приводятся определения естественного порядка на бу левой алгебре a
идеала Фреше. Следуя [1], через F a (2l)
обозначим а-тый итерированный идеал Фреше алгебры 21. В дальнейшем, если из контекста ясно, о какой алгебре идет речь, будем использовать запись Fa вместо F a (2l). ОПРЕДЕЛЕНИЕ 7. Рангом Фреше булевой алгебры 21 называется первый ординал р(21) = а такой, что Fa = F a +i« Известно, что ранг Фреше суператомной булевой алгебры являет ся непредельным ординалом и в фактор-алгебре 2l/F p (^)„ 1 (2t) содержится конечное число атомов (см. [1]). Тогда типом суператомной булевой алге бры называется пара г (21) = (а, га), где />(21) = а + 1 и ш ~ - число атомов в 2 l / F a . Известно, что счетная суператомная булева алгебра определяется своим типом с точностью до изоморфизма [1].
200
А. В. Ромина § 2. Изложение основных результатов
Для дальнейших рассуждений нам потребуется следующая лемма. Л Е М М А 1. Пусть (ЯЛ, v) u (ЯЛ',*/) — это
/^{-конструктивные
модели одинаковой сигнатуры. Тогда существует функция f из первого неконструктивного
ординала в HYP такая, что
/ ( а ) = {(х,х') | (3rt,i/(ai)) Г
№У(х'))}
= s*a
и f является Ш-функцией на HYP. ДОКАЗАТЕЛЬСТВО. Положим s* = {(х, х') | Зу? (бескванторная формула)
(отИ^И^&^И^И^)))}, *; +1 = {<*, 2') | зу е u>W е ««(*, у), (Эд) € < ) V3y' € u;Vy G w«(5,y),(i' f yO) G < ) } , 5* = M s * для предельных 7. Индукцией по а проверим, что s* = {(х,х')\(ЯЯ,1/(х))
фа (ЯЛ, */(ж'))}.
Если а = 0 или осуществляется переход от а к а + 1, то заключение леммы очевидно. Проверим для предельных ординалов. 1) Включение С — очевидно. 2) Проверим включение Э. Пусть (x,xf)
G {(ж, х') | (ЯЛ,*/(ж)) ^ a
^ а (ЯЛ, f'(x')}? тогда существует формула Ф(т) = Vt(Aj W,i) такая, что ЯЛ |= Ф(1/(х))&ЯЛ' (= -1ф(*/(я')) и qi((fij)
< а. Поэтому найдутся
i,j,
для которых ЯЛ (=
такой,
что r(c) = wjp*. Пусть класс УК является Д}-вычислимым. Тогда для ск
всех z € ы<из либо имеем (ЯЛ, £>(£)) фш*
(ЯЛ, *>(с')), либо существуют
(91, //) G 9t и функция, осуществляющая эквивалентность соответствую щих конструктивизаций (это условие задается Е-формулой). Тогда, по приципу Е-рефлексии, найдется элемент Ь из HYP такой, что Vz е и<ш3(а,д)
€ b3(0l,/i) € 9fy((£OT,i/(*)) ^ a (ЯЛ, с) V (д осуществля
ет эквивалентность (ЯЛ, v(z)),v)
и (91,^))). Поэтому существует и просто
изоморфизм. Пусть гпк(Ь) = /3. Тогда (Vc7 G М <и, )((ЯЛ,с) = " (ЯП,?) -> -> (ЯЛ, с) = (ЯЛ, с')), получили противоречие с неконструктивностью г (с). 2) Гиперарифметическая модель, очевидно, 1-разрешима в некото рой степени 0^\
7 < ufK.
В [6] доказано, что в этом случае, если ЯЛ
автоустойчива, существует конечное константное обогащение с, при кото ром (ЯЛ, с) будет простой. Тогда sr (ЯЛ, с) ^ о;. Так как sr (ЯЛ, с) ^ sr (ЯЛ) ^ ^ sr (ЯЛ,с) +<и (^.и + и < cjf А ), получили противоречие. П
§ 3. Автоустойчивость булевых алгебр Здесь рассматривались вопросы А}-автоустойчивости Д^-конструктивизируемых булевых алгебр. Поэтому начнем с критерия.
Автоустойчивость гиперарифметических моделей
203
Т Е О Р Е М А 3 (критерий Воота эквивалентности конструктивиза ций булевых алгебр). Пусть (21о,г>о), (2ti»^i) — это
А\-конструктивные
булевы алгебры. И пусть существует А{-множество S С А0 X А\у {{n,m)\(v(n),v{m))
т.е.
G 5} G А\, такое, что
1)(1,1)€S; 2) ( а , Ь ) Е 5 - > ( а = 0 ^ Ь : = 0 ) ; 3) ( a , b ) G 5 - > V x < a 3 y < Ь ( ( ж , у ) б 5 & ( а - ж , 6 - у ) 6 5); 4) (а, Ь) € S -+ Vj/ < 6Эх < о((ж, у) G 5 & (а \ х, 6 \ у) G 5). Тогда э т и конструктивизаций
эквивалентны.
ДОКАЗАТЕЛЬСТВО. Если (2l0,i/0) и (2l b i/i) являются Д{-кон структивными, то они конструктивны в некоторой степени О^
(71 <
к
< u?f ). Если 5 — это Д}-множество, то оно рекурсивно в некоторой сте пени О^
(72 < <*>1К)- Пусть 7 = max{71,72}- Тогда (2i0, щ), (21ь »г) кон
структивны в степени О ^ и 5 рекурсивно в степени O^h По релятивизованному критерию Воота (см. [2]) для конструктивизаций булевых алгебр эти конструктивизаций эквивалентны относительно Я 7 (в степени О ^ ) , следовательно, Д}-эквивалентны. Очевидно, что из эквивалентности кон структивизаций следует существование такого множества. D С Л Е Д С Т В И Е 1. Пусть а — конструктивный *8 —- это а-атомная А\-конструктивизируемая является А\-автоустойчивой.
Тогда 5$ будет
ординал.
Пусть
булева алгебра, и *B/Fa А\-автоустойчивой.
ДОКАЗАТЕЛЬСТВО. Нам потребуется Л Е М М А 2. Пусть (*B,v) — это А\-конструктивная
булева алге
бра. Тогда существует Е-функция F на HYP такая, что SF = ufK &V7 < u f A ' ( F ( 7 ) = {п\и(п)
G F 7 }).
ДОКАЗАТЕЛЬСТВО леммы. Положим Fo = 0 , Fa+i = {п | 3m G и<шЧп' G u(v{n') < v{n) f> (i/(n') П i/(m,-)) U (i/(rnt-) П z/(n')) G F 7 для некоторого г}, F 7 = [ J F a для предельных 7.
h
204
А. В. Ромина, Рассмотрим оператор Г(Ф) ?=± {(a, F*) | Vn G u(i/(n) & F*v3(y, F'*) G
G Ф(Эш G w ^ V n ' G w(i/(n') < u(n) <-• {^(nf)nu(mi))U(u(mi)nu(nf)) для некоторого i))k(v(n)
G F'*
G F* V V7 G a3(7,F'*) G Ф(Ут G u;
G w(i/(n') < i/(n)& (^(n7)nc(i/(mf-))) U Кт,-)Пс(1/(п'))) £ F'* для всех г))}. Нетрудно видеть, что F* = {n | i/(n) G F tt (5J)}. По теореме Ганди такая функция существует (неподвижная точка этого оператора будет ее графиком). Более того, очевидно, что р(Ъ) ^ и^к.
•
Вернемся к доказательству следствия. Пусть щ^х
— две различ
ные Д{-конструктивизации 05. Рассмотрим индуцированные конструктивизации и>,i7i факторалгебры 2S/F a (v%(n) = i/j(n)/F a ), эквивалентные по условию. Тогда существует Д{-множество 5о, удовлетворяющее усло виям 1—4 критерия Воота. Рассмотрим 5 = {(я, у) | (щ(х) = 0 +* ui{y) = = 0) & (ц,(з) G F Q H fa (у) 6 F a & г Ц ( х ) ) = r(z/ 1 (j/)))))&(c(i/ 0 (x)) G 6 f a H
(C(l/i(y)) G F a & r ( c f a ( * ) ) ) - т(с(иг(у)))))
k (v(x)/Fay
^(y)/FQ)
€
G5o}. Проверим равенство т(щ(х)) = r(i/i(y)): r fa (я)) = r(i/1(y)) «-> З7 G G a f a ( s ) G F 7 +i&i/i(y) G F 7 + i & 3 m G w < u W G a>fa(s') < ^o(a?) *-> <-> fa(s') П cfa(w*,-)))
u
fafat) П cfa(s'))) ^ &y Д ЛЯ некоторого г) &3n G
G u><"Vy' G wfa(yO < i/!(y) <-• fa(y') П c f a f a ) ) ) U fa fa) П cfa(y'))) G F 7 для некоторого г) & (m и п имеют одинаковую длину и не могут быть короче). Очевидно, что 5 — это Д*-множество, также удовлетворяющее всем условиям критерия Воота. • В [4] указан пример рекурсивной булевой алгебры, имеющей по крайней мере две конструктивизации, не СИа)-эквивалентные при любом а < u^Ki
а значит, и не Д{-эквивалентные (это алгебра ^шскх^г\).
Ана
логичными рассуждениями можно показать, что класс *Н Д}-конструкти визации этой алгебры не лежит в Д } . У Т В Е Р Ж Д Е Н И Е 1. Класс всех А\-констпруктивизаций алгебры ^шскх^+1\
булевой
не лежит в А\.
Действительно, предположим, что он вычислим (в смысле Д*-кон-
Автоустойчивость гиперарифметических моделей
205
структивизируемости). Тогда существует a < и^к , при котором этот класс лежит в Рассмотрим класс % всех вычислим в степени О^).
-конструктивных булевых алгебр (он
Пусть (2l,i*a) — булева алгебра из этого клас
са. Если 21 = *Вшскх(г)+1)1
то
найдется гиперарифметическая функция,
осуществляющая эквивалентность соответствующих конструктивизаций, в противном случае найдется а такое, что 21 не является а-атомной. Тогда, по принципу Е-рефлексии найдется 7 такой, что V(2l, v%) G % (21 = *Вшскх(т)+1) V 2t не является 7-атомной). А это не так. D Автор выражает благодарность своему научному руководителю С. С. Гончарову за постановку задачи и существенную помощь в работе.
ЛИТЕРАТУРА 1. С. С. Гончаров, Счетные булевы алгебры и разрешимость, Новосибирск, Научная книга (НИИ МИОО НГУ), 1996. 2. Ю. Л. Ершов, Проблемы разрешимости и конструктивные модели, М, На ука, 1980. 3. X. Роджерс, Теория рекурсивных функций и эффективная вычислимость, М, Мир, 1972. 4. C.J.Ash, Categoricity in hiperarithmetical degrees, Annals Pure Appl. Logic, 34, N 1 (1987), 1-14. 5. J. Barwise, Admissible sets and structures, Berlin, Springer-Verlag, 1975. 6. 0. JB. Кудинов, Проблема описания автоустойчивых моделей, Алгебра и ло гика, 36, N 1 (1997), 26-36.
Адрес автора:
Поступило 10 сентября 1999 г.
РОМИНА Анна Валерьевна, РОССИЯ, 630090, г. Новосибирск, ул. Пирогова, 2, Новосибирский государственный университет.
Окончательный вариант 1 февраля 2000 г.
