Алгебра и логика, 40, N 2 (2001), 218-242
УДК 510.642+512.57
АЛГЕБРАИЧЕСКИЕ ЭКВИВАЛЕНТЫ СВОЙСТВ
НЕКОТОРЫХ
СУПЕРИНТУИЦИОНИСТСКИХ
П Р Е Д И К А Т Н Ы Х ЛОГИК*)
Д . Е. Т И Ш К О В С К И Й
В [1] введен и исследован класс квазицилиндрических алгебр: дока зано, что каждая суперинтуиционистская предикатная логика полна от носительно некоторого многообразия квазицилиндрических алгебр. Дан ная статья продолжает исследования в этом направлении: осуществляется трансляция свойства Бета, проективного свойства Бета, интерполяционно го свойства, дизъюнктивного свойства и экзистенциального свойства су перинтуиционистских предикатных логик на язык соответствующих мно гообразий квгьзицилиндрических алгебр. Основные обозначения и опреде ления указанной выше работы сохранены.
§ 1. Некоторые определения и обозначения Будем рассматривать языки 1-го порядка, не содержащие функцио нальных символов, предметных констант и символа равенства. При этом множество предметных переменных любого рассматриваемого языка пред полагается равным фиксированному счетному множеству Var = {#,• | г < < и}. Так как при вышеуказанных соглашениях множество предикатных символов однозначно определяет язык 1-го порядка, будем отождествлять *' Работа поддержана Российским гуманитарным научным фондом t проект N 00— 03-00108.
©
Сибирский фонд алгебры и логики, 2001
Алгебраические эквиваленты некоторых свойств
219
множество предикатных символов и соответствующий ему язык, исполь зуя для них одно и то же обозначение. Пусть Р — некоторое множество предикатных символов. Функция # : Р -> а; каждому р из Р ставит в соответствие его арность, т. е. всякий р из Р является #р-арньш преди катным символом. Обозначим через For(P) множество всех формул языка Р. Для каждой формулы А обозначим через FV(A) множество свободных переменных формулы А, а через Р(А) — множество всех предикатных символов, встречающихся в формуле А. Через s^A обозначается резуль тат замены свободных вхождений переменной Xi в А на переменную х$, при условии, что эта замена допустима, т.е. ни одно свободное вхожде ние x-i в А не попадает в область действия квантора по Xj. Для любых двух формул А и В выражение А ~ В служит сокращением формулы (АэВ)Л(ВэА). Пусть Рг — некоторое фиксированное множество предикатных сим волов, содержащее для всякого натурального п счетное множество преди катных символов арности п. Всякое множество формул языка Рг, содер жащее интуиционистскую предикатную логику и замкнутое относительно правил: подстановки [1], modus ponens и обобщения, будем называть супер интуиционистской
логикой. Так как далее будут рассматриваться только
суперинтуиционистские логики, будем опускать в указанном словосочета нии слово "суперинтуиционистский". Пусть L ~~ некоторая логика, Р ~ некоторое множество предикат ных символов. L-теорией в языке Р называется всякое множество фор мул указанного языка Р , содержащее все формулы языка Р , являющиеся подстановочными частными случаями формул логики L, и замкнутое от носительно правил modus ponens и обобщения. Ясно, что множество всех формул языка Р , являющихся подстановочными частными случаями фор мул логики L, образует наименьшую L-теорию в языке Р . Эту теорию будем обозначать через L(P). Пусть L — логика, Р — некоторый язык 1-го порядка, Г U {А} С С For(P). Пишем Г Ь-£, А и говорим, что в L из Г выводима А, если формула А принадлежит наименьшей Х-теории в языке Р , содержащей
220
Д. Е.
Тишковский
множество Г. Если Г — пустое множество, пишем L Ь А и говорим, что в L выводима А. Формулы А и В называют конгруэнтными (пишем: А ~ В), если А и В получаются друг из друга применением общеизвестного принципа замены связанных переменных (см., например, [2]). Через
а
обозначается
сигнатура
(Л, V, Т, 1_, -», D, V,-, 3,-, s*•). .
,
где Т, JL — пропозициональные константы, ->, Vi, 3,, 5*- — унарные, а Л, V, D — бинарные символы операций. Алгебру А = (Дя") назовем квазицилиндрической,
если (А, Л, V, Э, -ч,Т, J_) — псевдобулева алгебра и
в А для любых i , j , fc,/ < u; верны следующие совокупности тождеств: (Q1) з\Х = X;
(Q10) s)(X Э У) = 4 * Э ^ У ;
(Q2) У.-З^-Х" - 3,-Х;
(Q11) з){Х Л У) - ^-Х" Л s)Y]
(Q3) s'V.X = V.-JT;
(Q12) s){X V У) - s)X V *}У;
(Q4) З.-^Х - s)X (i ф j);
(Q13) *rX
(Q5) 3f-± - _L;
(Q14) V,-(X DY)<
(Q6) s)3kX
(Q15) V,X < sJX;
= 3 ^ ; Х (fc ^ г, j ) ;
= -4-Х; tyX
D У,У);
(Q7) 8$fkX = V*s*X (* ф г, j ) ;
(Q16) V;(X D Y) < (3,-X D 3.-У);
(Q8) sjs*X = ф } Х ;
(Q17) s)X < 3,-X;
(Q9) sjs*X - sf 4-Х (fc ^ г', j и l ф i); (Q18) V
если все
ее элементы финитарны. Для всякого класса К алгебр обозначим через К^
класс всех локально-финитарных алгебр из класса К, Л Е М М А 1.1 ([1, предл. 5.2]). Для любых элементов a, b про
извольной квазицилиндрической (г, j
алгебры верны следующие
(5) А (а V Ъ) С Аа U ДЬ;
(2) Д-io С Аа;
(6) AV,a С Аа \ {г};
(3) А(а D Ь) С Аа U A6;
(7) Д3;а С Да \ {г};
(4) Д(а Л Ь) С Да U Д6;
(8) Aeja С (Да \ {г}) U {j}.
соотношения
221
Алгебраические эквиваленты некоторых свойств
Из леммы 1.1 следует, что множество всех финитарных элементов любой квазицилиндрической алгебры образует локально-финитарную по далгебру данной алгебры. Подалгебру, составленную из всех финитарных элементов данной алгебры, назовем наибольшей локально-финитарной по далгеброй данной алгебры. Л Е М М А 1,2. Для любого элемента (aj \ j € J) из прямого произ ведения YI Aj квазицилиндрических С (J
алгебр выполняется А(а^ | j 6 J ) С
Aaj. ДОКАЗАТЕЛЬСТВО. Если г £ (J Да,-, то V.-а, = а, для всех j G J .
Следовательно, V$(aj | j £ J) = ( V ^ | j £ J ) = (aj | j E J ) . Поэтому г $ A(a3 \j e J ) . О Означиванием формул в алгебре А называется любое отображение v формул 1-го порядка в носитель алгебры А такое, что для любых формул А, В и чисел i , j < u? выполняется: (1) vT = Т и trJL = JL;
(2) v-iA = -и;А; (3) v(AVB) =
vAVvB;
(4) и(АЛВ) = иЛЛиВ; (5) v(A D B)^vAD
VB]
(6) vVa:l-A = V,-t7A;
(7) v3xiA = 3JVA; (8) если замена переменных s*-А допустима, то vs'jA = ^г;А. Говорим, что формула А истинна при означивании и, если г?А яв ляется наибольшим элементом Т алгебры А. Пусть К — класс квазици линдрических алгебр. Формула А называется семантическим
следствием
множества формул Г относительно класса К (пишем: Г f=# А и \=% А при пустом Г), если для любых алгебры из класса К и означивания v фор мул в этой алгебре истинность всех формул из Г при v влечет истинность А при том же v. Если К состоит из единственной алгебры А и \=к А, то формула А называется общезначимой на алгебре А. Логика L в язы ке Р полна относительно класса К (характеризуется классом К), если
222
Д. Е. Тишковский
L ~ {А | A G For(P) и \=к А}. Логика L сильно полна
относительно
класса К, если для любых формулы А и множества формул Г верна эк вивалентность Г \~ь А
<==>
Г \=к А. Ясно, что если L сильно полна
относительно А', то L полна относительно К. Л Е М М А 1.3 ([1, предл. 5.3]). Пусть v — означивание в некоторой квазицилиндрической
формул
алгебре. Для всякой формулы А из
FV(A) = {ж,- 0 ,... ,Х{п} следует AvA С {г 0 ,... ,г„}. Пусть Т — интуиционистская теория языка Р . Для данной теории Т и произвольной формулы А из For(P) положим ||Л)| = {BG For(P) | Т Э Э АЕЕ В}. Обозначим через F(T) множество {||А|| | А £ For(P)}. Опреде лим на F(T) операции сигнатуры а: (1) Т = ||Т|| И 1 = ||±||; (2) Н|А|| = Ц-ЛЦ; (3) |И|| э ||Я|| = \\А D ВЦ; ( 4 ) | | А | | Л | | В | | = ||АЛВ||; (5)||A||V||B|| = ||AVB||; (6) V,-||A|| = ||V*,A||; (7) 3,i|A|| = ||Э»,-А||; (8) 5j||-A|| = ||5*-JB||, где В — некоторая формула, которая конгруэнтна формуле А и для которой допустима замена переменных s* Р . Корректность определения вышеуказанных операций доказывается стандартным образом. Алгебра У(Г) = (Р(Т),сг) называется алгеброй Линденбаума—Тарского теории Т. Алгеброй Линденбаума—Тарского логи ки L в языке Р называется алгебра Линденбаума—Тарского теории L(P). Отметим, что отображение VT : For(P) -» F(T), определенное равенством VTA = \\А\\ для всех A G For(P), является означиванием формул в З'(Т). Отсюда по лемме (1.3) получаем, что произвольная алгебра Линденбаума— Тарского любой теории является локально-финитарной. Заметим, что теорема 5.7 из [1] остается верной в следующей форму лировке: Л Е М М А 1.4. Пусть А — квазицилиндрическая алгебра, At — мно-
223
Алгебраические эквиваленты некоторых свойств жество всех атомарных формул вида р(х^,...
, #*п); где я^ 1 Г ... , ж,-п —
некоторая, закрепленная за данным п-арным предикатным символом р последовательность различных переменных. Пусть VQ — отображение множества At в носитель алгебры А. Если для всех p{xix,...
, Xin) из At выполняется Аюор(х^ , . . . , ж;п) С
С {ii,*.. , г п } ; то vo единственным образом продолжается до означива ния v формул в алгебре А. Пусть h — произвольный гомоморфизм из квазицилиндрической ал гебры А в квазицилиндрическую алгебру Ъ. Нетрудно заметить, что для всякого элемента а алгебры А выполняется Aha
С Да. Если множе
ство Аа \ Aha конечно, то существует такой элемент а1 алгебры Л, что ha = ha1 и Аа' = Aha'. Действительно, пусть Аа \ Aha = {г 0 ,... ,««}• В качестве а! возьмем элемент V,0 • •-V tn a. Так как го,... , гп £ Д/ш, то u(Vj0 • •'Vj n a)
=
Vt-0 • • -\/inha
A(Vt0 • • • V,-na) С Aa\{i0,
= /ia. Кроме того, учитывая лемму 1.1,
. . . , t„} = Д/ш = Ah(V,-0 • - • Vino) С Д(У<0 • . - V,-na).
Таким образом, верна, в частности, ЛЕММА
1.5. Пусть h : Л —» Ъ — гомоморфизм
локально-
финитарных алгебр. Для всякого элемента Ь £ h(A) существует эле мент а £ А такой, что ha = Ъ и Аа = АЬ. Следствием леммы 1.4 является следующая Л Е М М А 1.6. Пусть L — суперинтуиционистская локально-финитарная
квазицилиндрическая
логика, А —
алгебра. Если в А общезна
чимы все формулы из L, то А является гомоморфным образом алгебры Линдепбаума—Тарского логики L в подходящем языке. ДОКАЗАТЕЛЬСТВО. Каждому элементу а алгебры Л, отличному от Т и JL, поставим в соответствие атомарную формулу pa(%i0, •. • »#im)» где г 0 ,... ,г ш — различные индексы переменных, составляющие все мно жество Да, а ра — предикатный символ соответствующей арности. Это соответствие взаимно однозначно. Если предикатных символов в языке Рг логики L недостаточно, то расширяем язык Рг до языка Р , добавляя необходимое количество предикатных символов требуемой арности к Рг.
224
Д. Е. Тишковский Положим для всех а из \Л\: vT = T, VJL = J_, v p a ( x l 0 , . . . , ж«т) —
= а. Для каждого предикатного символа q £ {ра \ a Е \Л\} положим: vq(xoi...
, a r ^ - i ) = Т. По лемме 1.4 отображение v продолжается до озна
чивания в алгебре А. Рассмотрим алгебру # = $(L(P)) Линденбаума—Тарского логики L. Определим гомоморфизм h из $ на A: h\\A\\ ^ vA. Определение h кор ректно: если ||А|| = ||В||, то L h A = J3, следовательно, и(А = 2?) = Т, т. е. г; А = t>23. Нетрудно показать, что h — гомоморфизм. Действительно, все усло вия гомоморфизма тривиально выполняются для ft, за исключением усло вия, касающегося операций s^. Пусть А — произвольная формула. Дока жем, что fcsj|f А|| = 5}Л||А||. Имеем: s*-||A|| = \\sljB\\ для некоторой формулы В, конгруэнтной формуле А) причем допустима замена переменных s^B. Таким образом, верна цепочка равенств /is*-ЦАЦ = /is*-||2?|| = /i||s*B|| = = vs)B - s)vB = 8)h\\B\\ = s)h\\A\\. П Л Е М М А 1.7. В любой алгебре # Линденбаума—Тарского логики L общезначимы все формулы из L. ДОКАЗАТЕЛЬСТВО. Пусть L Ь A, v - означивание в алгебре #. Покажем, что vA = Т. Пусть р\,...
,pk — все предикатные символы, име
ющие вхождение в А, переменные у з , . . . , yi (/ = max{#pt- | г = 1 , . . . , fc}) различны и не встречаются в А, при этом vpi(yi,...
,Уфр{) = | | Д | | (« —
= 1 , . . . , fc). Можно считать, что связанные переменные формул В о , . . . . . . ,J3fc отличаются от y i , . . . , у/ и не встречаются в формуле А. Тогда подстановка SPB\ (уг, . . . , у # Р 1 ) • • - ^ ( y i , . . . , у#Рк) А допустима [1, § 1], и ее результат С выводим в L) так как L \- А. Значит, ||С|| = Т. Индукцией по длине формулы А нетрудно проверить, что vA = ||С||. П
§ 2. Дизъюнктивное свойство Говорят, что логика L обладает дизъюнктивным свойством [3], если для всякой формулы А V В из Ь по крайней мере одна из формул А и В принадлежит L.
225
Алгебраические эквиваленты некоторых свойств
Квазицилиндрическая алгебра называется вполне связной, если для любых ее элементов а и 6 и з а У б = Т следует либо а = Т, либо Ъ = Т. Легко доказывается (см. [3]) следующая Л Е М М А 2.1. Если L обладает дизъюнктивным свойством, то лю бая алгебра Линденбаума—Тарского для логики L является вполне связ ной. ТЕОРЕМА 2.2, Пусть L — суперинтуиционистская
предикат
ная логика, характеризуемая замкнутым относительно взятия подал гебр классом К квазицилиндрических
алгебр. Следующие условия эквива
лентны: (1) L имеет дизъюнктивное свойство; (2) для любых алгебр Л, В из К^ локально-финитарная
существуют вполне
связная
алгебра Q, в которой общезначимы все формулы из
L, и гомоморфизм из Q на А X Ъ. ДОКАЗАТЕЛЬСТВО является предикатным обобщением доказа тельства аналогичной теоремы в [4]. (2) => (1). Пусть L $ А и L $ В. Тогда А и В опровергаются соответ ственно в некоторых алгебрах Л и Ъ из класса А\ Таким образом, vA < Т, wB < Т для некоторых означиваний v, w в алгебрах Л, Ъ соответственно. По лемме 1.1 образ любого означивания в квазицилиндрической ал гебре состоит из финитарных элементов. Так как К замкнут относитель но взятия подалгебр, то, переходя, если это необходимо, к наибольшим локально-финитарным подалгебрам алгебр Л и В, будем считать, что Л и Ъ локально-финитарны, т.е. принадлежат По (2) существуют вполне связная локально-финитарная алгебра С, в которой общезначимы все формулы из L, и гомоморфизм h из С на Л X Ъ. Заметим, что по лемме 1.2 аягебра АхЪ
локально-финитарна.
Пусть р — произвольный предикатный символ. Так как С и А X Ъ локально-финитарны, то, по лемме 1.5 существует такой эле мент с алгебры С, что Ас == A{vp(x0,... = (vp{xo, •. • , хп), wp(x0,...
,ж п ), wp(xo,...
, хп)). Положим ир(хо,...
,ж п )) и he =
, хп) ^=± с.
226
Д. Е. Тишковский По лемме 1.2, Аир(хо,...
С Дир(а;о,... , хп) U Awp(xo,...
, хп) = A{vp(xo,...
, хп), wp(xo1...
, хп)) С
, жп) С { 0 , . . . , п}. Значит, по лемме 1.4, и
продолжается до означивания в алгебре С. По свойствам гомоморфизмов и означиваний для любой формулы С выполняется huC — (vC^wC). Таким образом, huA < Т и huB < Т. Следовательно, и А < Т и иВ < Т. Так как С вполне связна, получаем и(А V В) = иА V иВ < Т. Значит, L^ AM В. (1) => (2). Так как L обладает дизъюнктивным свойством, то лю бая алгебра Линденбаума—Тарского логики L является вполне связной. Всякая алгебра Линденбаума—Тарского логики L является локальнофинитарной. По лемме 1.7 в любой алгебре Линденбаума—Тарского логи ки L общезначимы все формулы из L. Далее, по лемме 1.2 алгебра Л X Ъ локально-финитарна. Легко доказать, что все формулы из L общезначи мы в Л X Ъ. Таким образом, по лемме 1.6, Л х Ъ является гомоморфным образом подходящей алгебры Линденбаума—Тарского логики L. • § 3. Экзистенциальное свойство Суперинтуиционистская предикатная логика L обладает экзистен циальным свойством [5], если условие L Э Эж,-А влечет L Э s%-B для неко торой предметной переменной Xj и некоторой формулы В, конгруэнтной формуле А. Квазицилиндрическую алгебру назовем 3-связной, если для любого ее элемента а и любого г < и из 3,а = Т следует s*a = Т для некоторого 3 € w. Так же, как и лемма 2.1, легко доказывается следующая Л Е М М А 3.1. Если L обладает экзистенциальным
свойством, то
любая алгебра Линденбаума—Тарского для логики L является Т Е О Р Е М А 3.2. Пусть L — суперинтуиционистская
3-связной. предикат
ная логика, характеризуемая замкнутым относительно взятия подал гебр классом К квазицилиндрических лентны:
алгебр. Следующие условия эквива
227
Алгебраические эквиваленты некоторых свойств (1) L имеет экзистенциальное свойство; (2) для любого счетного семейства (Ai \ г £ и) ных алгебр из К существуют локально-финитарная
локально-финитар В-связная алгебра
С, в которой общезначимы все формулы из L} и гомоморфизм из 6 на наибольшую локально-финитарную
подалгебру алгебры \\ «Ai-
ДОКАЗАТЕЛЬСТВО. (2) => (1). Пусть для любой формулы В, кон груэнтной формуле А, и любого j E и формула s* В не принадлежит L. Тогда каждая s* В опровергается в некоторой алгебре Af Таким образом, vfs^B
из класса К.
< Т для некоторого означивания v& в алгебре
Af.
Так же, как и в доказательстве теоремы 2.2, можем считать все алгебры Af
локально-финитарными. По (2) существует вполне связная локально-финитарная алгебра С,
в которой общезначимы все формулы из £, и существует гомоморфизм h из 6 на наибольшую локально-финитарную подалгебру Ъ алгебры П ( ^ ^ I j
еи.В^А}. Пусть р — произвольный предикатный символ. Применяя лем
му 1.5, получаем, что существует такой элемент с алгебры С, что Ас = = A(vfp(x0,...
, хп) | j е и, В ~ А) и he = (vfp(x0,...
~ А). Положим ир(хо,...
, хп) ^± с.
По лемме 1.2, Аир(хо,... ж
, хп) \ j G a?, В ~
, хп) = A(vfp(xoy...
, хп) | j Е w, В ~ А) С
ж
С U i ^ ^ Р ( о » • • • » п) | j 6 u>, В ~ А} С { 0 , . . . , п}. Значит, по лемме 1.4, и продолжается до означивания в алгебре 6. По свойствам гомоморфизмов и означиваний для любой формулы С выполняется huC = (vfC
\ j € w,B ~ А). Таким образом, huSjB < Т, и,
значит, us%jB < Т для всех В, конгруэнтных А, и всех j б w. Так как С является Э-связной, получаем «Э;А = 3iuA < Т. Значит, L ^ 3,А. (1) ==> (2). Так как L обладает экзистенциальным свойством, то вся кая алгебра Линденбаума—Тарского логики L является Э-связной. Всякая алгебра Линденбаума—Тарского логики L является локально-финитарной. По лемме 1.7 в любой алгебре Линденбаума—Тарского логики L общезна чимы все формулы из L. Ясно, что все формулы из L общезначимы в
IK^f
I 3 £ CJ,B ~ А}. Таким образом, по лемме 1.6, наибольшая
228
Д. Е. Тишковский
локально-финитарная подалгебра алгебры ГК^-f I 3 G ^> В ~ А} явля ется гомоморфным образом подходящей алгебры Линденбаума—Тарского логики L. •
§ 4. Свойство Бета Пусть А — формула, р0? • • • ,Pk ~ различные предикатные символы. Будем использовать запись А\р0,...
}pk]
вместо А, если все предикатные
символы формулы А содержатся среди ро,...
, р&. Если q$ — предикатный
символ той же арности, что и р$, то через A[qo}p\,...
^Рк] будем обозначать
формулу, полученную из А заменой символа ро на доСуперинтуиционистская предикатная логика L обладает свойством Бета, если для всякой формулы А[р,ро, •« • ,Pk] из А\р,ро,...
,Рк]А Л[д,ро,... ,Р*] Ьь р(а? 0 ,... , s # P - i ) = д(ж 0 ,... , Z # P - I )
следует A\p,p0l . . . ,р*] 1-/, р{хо,.• • , ХФР~\)
= В для некоторой формулы
S [ p o , . . . ,Рл]. Пусть if — произвольный класс квазицилиндрических алгебр, за мкнутый относительно взятия подалгебр. Говорим [б], что К обладает свойством ES*, если для любой алгебры Ъ из К и любой подалгебры Л алгебры Ъ выполняется следующее условие 1?S*(!B, Л): для любого b из |В| \ \А\ такого, что множество \А\ U {Ь} порождает Ъ, найдутся алгебра С из К и мономорфизмы д, h из Ъ в С, для которых д Г Л = /г \ А и #6 / hb. Говорим, что К обладает свойством ES* для конечно-порожденных алгебр, если условие 2£5*(£,Л) выполняется для любой конечно-порож денной алгебры Ъ из К и любой ее конечно-порожденной подалгебры Л. Т Е О Р Е М А 4.1. Пусть L — суперинтуиционистскал логика, полная относительно некоторого многообразия V ческих алгебр. Следующие условия эквивалентны: (1) L обладает свойством Бета; (2) V^
обладает свойством ES*;
предикатная квазицилиндри
229
Алгебраические эквиваленты некоторых свойств
(3) VW обладает свойством ES* для конечно-порожденных алгебр. ДОКАЗАТЕЛЬСТВО является предикатным обобщением доказа тельства аналогичной теоремы в [б]. (2) => (3). Очевидно, что данная импликация имеет место. (1) => (2). Пусть Ъ — локально-финитарная алгебра из V (т.е. ДЬ конечно для всех Ь из |В|), А — подалгебра алгебры В, Ь € |В| \ |Л|, и В порождается множеством \А\ U {Ь}. Пусть каждому элементу а алгебры А, отличному от Т и 1 , соот ветствует предикатный символ ра такой, что Card (Да) = # р а , причем это соответствие взаимно-однозначно. Пусть Аа = {jo>--- ,3п}- Поставим в соответствие элементу а атомарную формулу pa(zj0j • • • > xjn)Точно так же с элементом b взаимно-однозначным образом свяжем предикатные символы р и q. Поставим в соответствие элементу 6 две разные атомарные формулы p(xiQ}...
, #,-m) и q(xioi...
,
- { t 0 , . . . , * m } . Пусть Р0 ^ {Pa I a е |Л|} U Ы , Рг-{ра\а£
\А\} U {«},
P^POUPL
Положим для каждого а из \А\: v0T т=± vxT ^± T, v0± ;=± v\A. ?=* -L, . . . ; x tm ) ;=± Ь. По лемме 1.4, г>о и г?1 продолжаются до означиваний в алге бре В. Пусть Тг ?± {А £ Fov(Pi) | ViA = Т}, г = 0,1. Положим Т ^ {А Е 6 For(F) | Т0 U Ti Ьх А}. Пусть С — алгебра Линденбаума—Тарского теории Т, она заведомо является локально-финитарной. Для каждого а из \А\ полагаем: дТ ^± КТ ^ Т, g± ^± h± ^=± JL, да ^± — Ы ^
\\pa(xjo1,..
,xjn)\\T,
#Ь ^
||р(я«о, • • • > ж 1 т )||т, ЛЬ ^
||g(a?j 0 ,...
Докажем, что отображения д и h продолжаются до гомоморфизмов из В в С. Поскольку алгебра В порождается множеством |Л| U {&}, до статочно показать, что для любых термов t и tf в языке квазицилиндриче ских алгебр и произвольных элементов со,... , сь из |Л|и{Ь} выполнимость равенства t(c0)...
, Ck) = £'(со,... , с*) в алгебре 3 влечет истинность ра~
230
Д. Е. Тишковский
венств t(gcQ,... , gck) = t'(flrc 0 ,... , 5 с*) и *(Лс 0 ,... , ftc*) = t'(hc0,...
, Лс*)
в алгебре С. Докажем указанное утверждение для отображения д. В пределах это го доказательства будем обозначать через гъ символ р. Будем также обо значать через г с соответствующим нижним индексом с произвольный пре дикатный символ из множества {рс \ с £ \А\}. Пусть со,... , Ck £ \A\U {6} и *(с 0 ,... ,6*) = £'(с 0 ,... ,с*). Имеем: рс; = ||г с .(ж, 0 ,... ,я,- п )||т Для % = = 0,...,fc. Индукцией по длине терма t построим формулу А[г С о ,... , rCk] такую, Ч Т О
* ( l l r c o ( « t o » - - - i«I-„)|JT, . - - , | к с Л ( « 1 о , - - . . * 1 „ ) | | т )
=
||А[ГС0, . . . , Г С Л ] | | Т
И
и0А = t ( c 0 , . . . ,Cfc). Б а з и с и н д у к ц и и тривиален. Шаг
и н д у к ц и и для операций V, Л, Э, -«, V», 3,- не пред
ставляет трудностей. Рассмотрим случай £ =
sfa.
По индукцион
ной гипотезе для t0 построена формула Ло[г Со ,... , rCk] такая, что *o(||rcp(«to»--- »«f„)||r,-.- »1КЛЯ|о»--- >x*n)ilr) = 1Ио||т и г;0Л0 = t 0 ( c 0 , . . . . . . , с^). Если ни одно свободное вхождение в AQ предметной переменной Xi не попадает в область действия квантора по Xj, а значит, замена пере менных S%-AQ допустима, то в качестве искомой формулы А возьмем ре зультат этой замены переменых, т.е. А ;=± S%-AQ. Тогда VQA = VQS^AQ = = S^VQAQ = s^o(^o». •. , Cfc) = *(co,... , с*). В противном случае заменим все связанные вхождения в AQ переменной Xj на какую-либо переменную, не встречающуюся в AQ. В результате получим формулу Ai, интуицио нистски эквивалентную формуле AQ. Таким образом, VQA\ = VQAQ. Кроме того, замена переменных s^A\ допустима, и, следовательно, в качестве ис комой формулы А возьмем результат этой замены. Аналогично строится формула Af такая, что ЦЛ'Цт = ^ ( I K o ^ o * *• • . . . ,я*п)1|т, ..• ,|кс Л (я?.- 0) ... , O H T ) И VQA1 = t ' ( c 0 , . . . ,с Л ). Тогда г;0А = — £(с 0 ,... , Ck) = t'(cQ,... , Ck) — v0Af'. По определению То получаем А = =
A!
£
T0. Тогда t(\\rCo(xio,...
, x , J | | r , . . . , ||r C| ,(s,- 0 ,... , а,-п)||т)
=
= 1И11т = 1И'||т = t'dkco^io.--- » ^ J I I T , . - . , 1 К ( Ж * 0 , . . . > S ; J I I T ) , И тре буемое равенство доказано. Доказательство аналогичного равенства для
231
Алгебраические эквиваленты некоторых свойств
отображения h получается из вышеприведенного доказательства заменой vQ на vi и Т0 на Т\. Проверим, что д и h являются мономорфизмами. В самом де ле, если дс0 = дсъ то ||г Со (а: 1о ,... ,xim)\\T rCo (xiQ,...
, ж,-т) ЕЕ гС1 (ж,-0,... , xim)
= ||rCl (xi(n . . . , ^ m ) | | T , т.е.
£ Т. Отсюда Г 0 U Тг h L rCo (ж, 0 ,...
. . . , я , т ) = rCl (я,- 0 ,... ,Ж| т ). Заменив в выводе формулы гСо ( х , 0 , . . . , я 1 т ) = = t'ciiziQT- ixim) вод rCQ(xiQJ...
из
Го и Т{ каждый символ q'c на qC) получим вы
,а?,-т) = г С1 (ж, 0 ,... , я ; т ) из Т 0 . По определению Т 0 имеем
с 0 = С!.
Допустим, что gb = hb. Тогда ||p(s t - 0 ,... , xirn)\\T и значит, Т
hL
р(ж 1 о ,... ,ж, ш )
Т0 U Ti h L р ( я 1 о , . . . }xim)
=
= ||ф, 0 > •.. , ж 1 т )|| т ?
ф ; 0 , . . . , xim).
Таким образом,
=: }(a?i 0 ,... ,а?,-те). В силу конечности вы
вода получаем А[р,р а о ,... , p a J Л А[д,р а о ,... , p a J h L р(з,- 0 ,... ,a?jm) = = ?(ж,-0, • • • i ж«т) Д л я некоторой формулы А[р,р а о ,... , p a J из Т 0 . По свой ству Бета найдется формула В [ р а о , . . . , p a J такая, что А[р,р а о ,... ,p«J hjr, р(ж,- 0 ,... ,ж»т) = Л. Отсюда иоР(ж,-0,... ,з» т ) - ^о^. Представим г>0£ в виде терма от i; 0 p a o (s; 0 ,... ,a?j n ),... ,«оРа л (^ 0 1 ••• >%*)• Таким образом, Ь = t>op(#i0>--- , Ejm) представим в виде некоторого терма от элементов алгебры Л, это противоречит тому, что b £ \А\. Следовательно, gb ф hb. (3)
=£•
(1). Предположим противное. Пусть m
А[Р, Ро, * • • , p*j Л A[q, р 0 , . . . , р*] HL р(а 0 , • •. , xm) В. Пусть Р
^
{р?РО).-- ,Рк}- Положим: Т
# р — 1,
= q(x0, •. - , ж т ) и нет
такой формулы J3[po,... ,р*], что А[р, р 0 , • • • , Рк] К =
=
р(&о, • • • > ж т)
^± {С
е
For(P)
= |
^[р>Рсь--- iPk] ^~ь С}. Пусть Ъ — алгебра Линденбаума—Тарского те ории Т. Пусть Л — подалгебра алгебры В, порожденная элементами ||ро(яо,... , я П 0 ) | | т , . . . ,\\рк(х0,... Если \\р(х0,...
,xm)\\T
e
,хПк)\\т. |Л|, то ||р(ж 0 ,... , я т ) | | т представим в
виде ^(||ро(ж 0 ,... ,ж Л о )||т,..- >||р*(зо,... »ж«*)11т), где * — терм в язы ке квазицилиндрических алгебр. Тем же способом, что и при провер ке импликации (1) => (2), строится формула В[ро,... ,р&], для которой
)Ит,...,1ы:
)\\т) = ||В[ро,... >Р*]||т. Таким об
разом, ||р(ж 0 ,... ,ж т )||т = ||J3[po? • • • IJP*]||TI или в других обозначениях
232
Д. Е. Тишковский
MjPtPoi • • • iPk] l~L p(zo) • • • > #m) = -В, что невозможно по первоначальному предположению. Следовательно, ||р(жо, • • • > х т ) | | т §£ |*А|Множество |Л|и{||р(жо, •. - , # т ) | | т } порождает алгебру Ъ. В силу (3) существуют локально-финитарная алгебра С из V и гомоморфизмы из Ъ в С такие, что д \ Л = h \ А и дЬ ф hb. Положим: vT = Т, v± = ±, ир;(а;о, ••• , s n J ^ 5||jPi(so, • • • >жп;)||т> г = ^
0,...,fc, vp(x0, •.. , xm)
^
flUpfao,...
,« г о )||т, vq(x0,...
,a?m) ^±
Л||р(ж 0 ,... , s m ) | | r . Тогда Дир(а 0 ,... , я т ) С { 0 , . . . , m } ,
Avq(x0,...
• • • » *т) С { 0 , . . . ,га} и Дир в '(х 0 ,.. • , я п .) С { 0 , . . . , п,-} (г = 0 , . . . , к). Проверим только второе включение. Пусть г Е Дг;д(жо,... , ж т ) , т.е. Vivq(x0,...
, з т ) / ug(ar0, •. • , xm). Таким образом, Ч{Щр(хо,... , ^ m ) | | T ^
^ /t||jp(a?0,... , ж ш )||г. Далее, h\\Vxip(x0,... т. е. Т \/L \txip(x0,...
, xm) = р(ж 0 ,... , я т ) | | т < Т,
, ж т ) = р(ж 0 ,. •. , хт). Значит, L \/ Vxip(xQ,...
, хт) =
= р(жо,... , жго), что возможно только в случае, когда г £ { 0 , . . . , т } . По лемме 1.4 отображение v продолжается до означивания в ал гебре С. Имеем: vA\p,p0,...
,рк]
vA[g,po,--- ,Р*] = h\\A[q,poj...
= д\\А[р,р0,...
,р*]||т =
0~Г =
Т,
,Рк]\\т = ЬТ = Т, с другой стороны,
t;p(a?o,... , ж т ) =^ ^д(ж 0 ,... , Хт). Полученное противоречие с первоначаль ным предположением завершает доказательство теоремы. •
§ 5. Проективное свойство Бета Суперинтуиционистская предикатная логика L обладает проективним свойством Бета, если для любой формулы А[р, ро,... ,р&, qo, •.. , qi] условие
р(^о, • • • J s # p - i ) = ?(s
влечет А[р,р 0 , ••• iPfc,?o,--. ,«] ^ L p ( s 0 , . . . , Z # P ~ I ) = J3 для некоторой формулы В[ро,... ,рл]. Пусть /С — произвольный класс квазицилиндрических алгебр, за мкнутый относительно взятия подалгебр. Говорим [6], что К обладает
Алгебраические эквиваленты некоторых свойств
233
свойством SES, если для любой алгебры Ъ из К и любой подалгебры Л алгебры "Б выполняется следующее условие
SES(b,A)\
для любого Ь из |В| \ |Л| найдутся алгебра С из К и мономорфизмы д и h из Ъ в С такие, что # f Л = ft f Л и #Ь ф hb. Говорим, что К обладает свойством SES для конечно-порожденных алгебр, если условие SES^,A)
выполняется для любой конечно-порож
денной алгебры Ъ из К и любой ее конечно-порожденной подалгебры Л. Т Е О Р Е М А 5.1. Пусть L -— суперинтуиционистская логика, полная относительно некоторого многообразия V
предикатная квазицилиндри
ческих алгебр. Следующие условия эквивалентны: (1) L обладает проективным свойством Бета:, (2) У Н обладает свойством
SES:
(3) V(w) обладает свойством SES для конечно-порожденных алгебр. ДОКАЗАТЕЛЬСТВО является обобщением на случай предикатной логики доказательства аналогичной теоремы в [6]. Очевидно, что из (2) следует (3). (1) => (2). Пусть Ъ — локально-финитарная алгебра из У, Л — подал гебра В, Ь € |В| \ |Л|. Пусть каждому элементу а алгебры Л, отличному от Т и 1 , соответствует предикатный символ ра такой, что Card (Да) = # р а , причем это соответствие взаимно-однозначное. Пусть Да = {jo?••• ijn}Поставим в соответствие элементу а атомарную формулу pa(#j0> • • • i xjn)Точно так же с каждым с из |В| \ \А\ взаимно-однозначным образом свяжем предикатные символы qcnqfc. Каждому такому с ставим в соответ ствие две разные атомарные формулы qc(xi0,...
, Xim) и q£(x, 0 ,... , я?,-да),
где Ас = {i 0 , • • • , гт}. Пусть Р0 ?± {ра | a £ \А\] U {qc \ с g | S | \ |Л|}, Рг ^ {Pa I a б |Л|} U {^ | с 6 |В| \ |Л|},
P^P0UPX.
Для всех а из |Л| и с из | S | \ \А\ полагаем: г;0Т ^± г^Т ;=± Т, VQJL ?=± ^=± vi± ^± J_, v0pa{xjQ,... x
••• i im) ^
yXjn) ж
^1^(^*0? ••• > 1т) ^
^ с
г;1р а (ж л ,... ,x J n ) ^
- ^°
ле
a, иоЯс(з,-0,...
мме 1.4, г?0 и ui продолжаются
до означиваний в алгебре Ъ. Пусть Ti т=± {A G For(Fi) | i?«A = Т } , г = 0,1. Положим Т ^ {Л е
234
Д. Е. Тишковский
£ For(P) | То U Т\ !-£, А}. Пусть С — алгебра Линденбаума—Тарского теории Г, она заведомо является локально-финитарной. Для всех а из \А\ и с из \Ъ\ \ \А\ полагаем: дТ ^ КГ ^ Т, gl. ;=± / i . L ^ -L, ga^tha^
^
||р в (ж л ,... ,а,- п )||т, ffc^± ||? c (s,o,... .^т)11т, Лс ;=±
^ ||^(ж, 0 ,... ,011тПокажем, что д и h являются гомоморфизмами. Будем обозначать через г с соответствующим нижним индексом произвольный предикатный символ из множества {рс \ с £ \А\} U {qc \ с 6 |В| \ \А\}. Пусть с = s*c0. Тогда v0rc(xio,... сюда rc(xio1...
, a?t-m) = s)vQrC0 {xio,... , a,-ra) = sir^xio,...
, xim) = г; 0 ^г С о (я; 0 ,... , ж,-т). От
, xim) e To С Т. Следовательно, #c =
= | | г с ( ^ 0 ? . . . ,a?iTO)||T = eJ||rco(a?,'0,... , ^ т ) | | т = 45 с °- Случаи с = c0 Л с ь с = с 0 V ci и пр. рассматриваются аналогичным образом. Так же, как и в теореме 4.1, доказывается, что д и h являются моно морфизмами. Допустим, что gb = hb. Тогда ||дь(х 1о ,.,. , < О Ц т ж
=
IkbC^'o»-••
ж
• • • > ^ m ) | | T , и, значит, ?ь(ж.-0,... ,ж,-т) = 9ь( »о> ••• > *т) € Т. Таким образом, Т0 U Tx h L
ft(«i0)...
,s,-m)
=
q'b(xi0,...
,а« т ). В силу ко
нечности вывода получаем А[$>,Ра0,. • • ,Ра к , Яс0,.. • , ?cj Л Л[д£,рао> • • • ••-iPa^gio,...^,] торой
формулы
тивному ЧТО
свойству
Ь-L %(ж.о,---.^т)
=
^(ж,- 0 ,...,х^ т ) для неко
A[qb, Рао,--- ,Рак,Ясот- , ?с«] Бета
найдется
А[ф>, Р а 0 > • • • > Pa* » (fco 7 • • • , Qct]
формула ^L
из
Т0.
В\рао,...
Qb{xio , • • • , 3; TO )
По
проек-
,paJ
такая,
=
В.
vo9b(a?,-0,... , £ tm ) = v0B. Значит, как и в теореме 4.1, v0qb{xio1...
ОтСЮДа
,x l m )
представим в виде терма от v0pao (zjo»• • • > ^in),.'.. , t;0pafc ( я ? 0 , . . . , xjn), это противоречит тому, что voqb(xi0)...
, ж,-т) = b £ \А\. Следовательно,
gb ф hb. (3) => (1). Предположим противное. Пусть m = # р - 1, А[р,ро»--. . •• ,Pfc,9o,... ,«] Л Л[д,Ро,... ,Р*,9си--- »9j] ^
р ( з 0 , . . . , ж т о ) ~ g ( s 0 , . •.
. . . , ж т ) и нет такой формулы В[ро,... ,Р*], что А[р,ро, • • • »Р*» 9о, • • • • • - , « ] ^ ь р(ж 0 ,... ,ж ш ) = -В- Пусть Р ^ лагаем: Г ^ { С е
{р,Ро,... ,р*,?о,. •• , « } - По
For(P) | Л[р,ро,... ,Р*,9о,... ,«] ^ L С } . Пусть 3
-
алгебра Линденбаума—Тарского теории Т,А — подалгебра алгебры £ , по-
Алгебраические эквиваленты некоторых свойств
235
рожденная элементами ||ро(^о, • • • , хп0)\\т, • • • , ||Pfc(#o>• • • , S „ J | | T . Как и в теореме 4.1, получаем ||р(яо>... , ж т )||т ^ \А\. Отсюда, существуют ло кально-финитарная алгебра С из У и гомоморфизмы из Ъ в б такие, что д Г Л = Л f Л и gb ф Kb. Полагаем: vT = Т, и± = _L, ир,-(жо,... ,жп,-) ^ ff||Pt(s
* m j ) | | T , j = 0 , . . . , /, г;р(ж 0 ,... ,xm) ид(жо,... ,ж т ) ^
^ g\\p(xQ,.. • , x m ) | | T ,
/i||p(£o,.., ,ж т )||г. Как и в теореме 4.1, легко прове
рить, что Avp(xQ,..., Avp f -(a? 0 ,...-,x n .)
^
xm) С
С { 0 , . . . , m } , Дг;д(а? 0 ,... ,а?т) С { 0 , . . . , га},
{ 0 , . . . ,7г,},
Ди^(жо,... ,а т ,-)
С
{0,... ,т,-},
Д ^ - ( х о , . . . , a m i ) С { 0 , . . . , mj} (г = 0 , . . . , &,j = 0 , . . . , /). Таким образом, по лемме 1.4 отображение г? продолжается до означивания в алгебре С. Имеем: vA[p,p0,...
,р*, «>,••• ,«] = ff||A[p,po,... ,p*,go,... ,«]||т =
= #T = - Т , г;А[^,р 0 ,... ,р*, «&,... ,«Я = /i||A[?,p 0 ,... ,Pfc,?oi--- »9J]||T = = feT = Т и г;р(ж 0 ,... , хт) ф vq(xo)...
, хт). Полученное противоречие с
первоначальным предположением завершает доказательство теоремы. •
§ 6. Интерполяционное свойство Суперинтуиционистская предикатная логика L обладает интерполя ционным свойством (ИС), если условие L Ь A D В влечет L Ь А Э С и L \- С Э В для некоторой формулы С, содержащей только те предикат ные символы, которые входят в формулы А и В одновременно. Формула С называется интерполянтом формул А и В. Суперинтуиционистская предикатная логика L обладает интерпо ляционным
свойством выводимости (ИСВ), если условие А Ь^ В вле
чет А Ьх С и С \~ь В для некоторой формулы С такой, что Р(С) С С Р(А) ПР(В). Формула С называется интерполянтом по выводимости формул А и В. ЗАМЕЧАНИЕ 6.1. Классическая формулировка ИС предполагает также выполнение для интерполянта условия на свободные переменные: FV(C) С FV(А) ПFV(В). Однако это условие в формулировке ИС можно
236
Д. Е. Тишковский
опустить. В самом деле, если х £ FV(C)\FV(B),
то из Int Ь Уж (С Э J3) Э
Э (3zC D В) получаем С D В \-L ЗхС D В. Кроме того, из Int h С D ЗхС следует, что А э С Ь/, А Э ЗяС. Если же ж Е F F ( C ) \ F V r ( A ) ) то аналогич ным образом из Int \~ Vx(A D С) D (A Э УхС) и Int Ь УжС Э С вытекают A D С Н/, А Э VxC и С D J5 Н/, VxC D В. Таким образом, если в интерполянт формул А и В переменные, не встречающиеся в FV(A) О FV(B), входят свободно, то переменные, не входящие в FV(B),
можно связать
квантором существования, а переменные, не входящие в FV(A),
— кван
тором всеобщности, и в результате получить классический интерполянт формул А и В , для которого выполняется вышеуказанное условие на сво бодные переменные. В формулировке ИСВ отсутствует указанное условие на свободные переменные по следующей причине. В суперинтуиционистских логиках формула D выводима из посылок Г тогда и только тогда, когда из Г вы водимо универсальное замыкание D. Поэтому, если С является интерполянтом по выводимости формул Л и В, то \/хС является классическим интерполянтом по выводимости формул А и В. Класс алгебр К называется амальгамируемым [7], если для любых алгебр Ло, А\, Л 2 из К и вложений i\ : AQ —• А\ и г2 : А$ —> Л 2 существуют алгебра Л из К и вложения е\ : А\ —> Л и е2 : Л 2 —• Л такие, что е\%\ = = в2г*2. Класс алгебр К называется сверхамалъгамируемым
[7], если усло
вие амальгамируемое™ класса К дополнено условием: для всех а\ Е \А\\ и а 2 Е |Л 2 | выполняется ^i^i < е 2 а 2 <£=> За 0 Е |Л 0 |(а1 < iia 0 Л г 2 а 0 < а 2 ), е 2 а 2 < е\а\ <=> За 0 € |Л 0 |(а 2 < г2«о Л П^о < «ОЕсли класс Л' амальгамируем (сверхамальгамируем), то будем также го ворить, что К обладает свойством АР (соответственно: Sup АР). Пусть далее L — суперинтуиционистская предикатная логика, полная относительно некоторого многообразия V квазицилиндрических алгебр. Л Е М М А 6.2, Если L обладает ИСВ (ИС), то класс мируем
{сверхамальгамируем).
амальга
237
Алгебраические эквиваленты некоторых свойств
ДОКАЗАТЕЛЬСТВО является модификацией доказательств соот ветствующих лемм в [8] и [9]. Пусть Л о , Л ь Л 2 € V^\
a i\ и г2 — моно
морфизмы из алгебры Ло в алгебры А\ и Л 2 соответственно. Не уменьшая общности можно считать, что Ло — общая подалгебра алгебр А\, А2- По строим алгебру Л из V^
и мономорфизмы ei, е2 из алгебр А\, Л 2 в Л
соответственно такие, что ei f Ло = е2 f ЛоПоскольку Л1 и Л 2 принадлежат V^\
то Card(Aa) < и для любого
а из |Лх|и|Л 2 |. Поставим в соответствие каждому элементу а из |Л1|и|Л 2 |, отличающемуся от наибольших и наименьших элементов алгебр А\ и Л 2 , атомную формулу ра(ж ^ , . . . , xjn), где Да = { j 0 , . . . , j n } , a p a — некоторый предикатный символ соответствующей арности. Считаем, что разным а и а' соответствуют разные предикатные символы ра и j v , T - e - отображение а ^ ра взаимно-однозначно. Полагаем: P t ^ {pa | a 6 |Л г |} (г = 0,1,2), Р ?± Р\ U Р 2 . Определим отображения Vi (г — 1, 2): г;,Т ^± Т, u;JL ^ JL и Vipa(xj0,...
, x Jn ) ?=± a для
всех а из |Л,-| \ { Т , ± } . По лемме 1.4 отображения г?1, г;2 продолжаются до означиваний в алгебрах Л ] , Л 2 соответственно и совпадают на всех формулах из For(Po)Пусть Ti ^ {А € For(Pi) | и.-Л = Т} (г = 1,2), Г ^ {А 6 For(P) | 1\ UT2 !-£, А}. Пусть Л — алгебра Линденбаума—-Тарского теории Т. Спра ведливо включение Л Е V ^ ' . Определим отображения е4 : Л г —» Л (г = 1,2). Пусть е;Т ^
Т,
ei± ?=± ± и e,a ^=± ||p a (x J O ,... ,a; i n )|| r для всех а € |Л,| \{T,_L} (г - 1,2). Проверим условие гомоморфизма для операции s*. Для к = 1,2 вы полняется и*р,< в (х л> . • • , S j J = sja = s)vkpa{xk,... ...,ж,- п ). Таким образом, vk{p8i.a{x3o,...
, xjn)
, xin) = =
vks)pa(xjo,...
ф ^ ^ о * • • • fSjJ)
= Т. Значит, по определению Tk, Psi.a(xj0,- - • , S j J = s)pa(xjo,...
=
, xjn) G
G Tk С Т. Отсюда e/bsja = | b ^ . a ( ^ 0 , . . . ,^ п )11т = ||*}р в (ау л ,... ,xin)\\T
=
= в*-||ра(а;^0,... , £j n )||r = sj-ej-a. Другие условия гомоморфизма проверя ются аналогичным образом. Таким образом, е\ и е2 являются гомомор физмами.
Д. Е. Тишковский
238
Чтобы доказать, что е\ и е2 являются мономорфизмами, потребуется следующая Л Е М М А 6*3. Для г = 1,2 если А е For(jFJ) П Г, mo v{A = Т. ДОКАЗАТЕЛЬСТВО. Пусть А е For(Pi) П Г, т.е. Гх U T 2 h L A. Значит, существуют такие конечные подмножества Fi и Г 2 множеств 2\ и Т2 соответственно, что Т\ U Г2 I~L А. Через А, обозначим конъюнкцию всех формул из Г; (г = 1,2). По теореме о дедукции верно А2 \~ь VxAx Э D А. Так как L имеет ИСВ, найдется такая С из For(Po), что А2 \~ь С и С Ь/, VxAi D А. Отсюда А2 \~ь С и Ах, С \~L А. Поскольку А2 G Г 2 , имеем и2А2 = Т. Логика L полна относительно класса V^\
поэтому г>2С — Т.
В силу С 6 For(Po) выполняется v\C = и2С = Т. Учитывая А\ € Ti, имеем viAi = Т. И, наконец, снова пользуясь полнотой L относительно V^\
заключаем, что v\A — Т. Случай, когда А 6 For(P 2 ), рассматривается аналогично. • Пусть теперь для некоторого г =
т.е. \\pa(xj0,...
1,2 выполняется e t a == е,Ь,
»ж>т)11т = !|Рб(ж*о>--- ^ * п ) | | г - Таким образом, р а ( ж л , . . .
. . . , ^ ' т ) = Pb{xka,--- ,Xkn) е Т. По лемме 6.3 получаем •••>**») = Рь(я*о,...,я* п )) = "Г- Отсюда а = vtpa(xJQ,...
Vi(pa(xj0,... ,xim)
=
= V|j?b{a;-jb0-,-: ..-,£* n ) == 6. Следовательно, ei и е^ являются мономорфиз мами, поэтому класс V^
амальгамируем.
Предположим теперь, что L обладает ИС, и покажем, что V^
свер-
хамальгамируем. Пусть a Е |*Ai|, 6 Е |Л 2 | и е\а < е26. Таким обра зом, | | p e ( s j b f - » ж *Л1т < ||рь(**о»--- >^ П )1Ь т.е. Г Э Pe(«jb»--- i*im) => Э Рь(%к0 > • • • ? ж*п)- Отсюда, как и в лемме 6.3, для некоторых формул Ах из 1\ и А2 из Т2 имеем А ь А2 h L Pa(xJO, • • • »^-ш) Э p&(zfco, • • • > ж О - Исполь зуя теорему о дедукции, нетрудно получить L Ь (VxA!Ap a (xj 0 ,... , a?jTO)) D D (V#A2 D P6(^fco?--- »ж*гп))в Поскольку L обладает ИС, существует С из For(P 0 ) такая, что L Ь (VxAi
& р а (ж^ 0 ,... ,Xjm))
Э С и L (- С Э
D (VxA2 Э р ь ( ^ 0 , . . . ,ЖА.П)). Отсюда Ах b-L Pafajb, - • • »ж>т) Э С и А2 Нь С D ръ(хк(п... Э С D Рь{хк0,-"
,хкп),
т.е. Ti Э Pa{xJQ,...,xjm)
D С и Г2 Э
,Xkn). Таким образом, a = vipa(«jo» ••• >^jm) < *>iC
и
t>2C < V2Pb(xk0, • • • , ^ J = Ь. Остается заметить, что в силу С Е For(Po)
Алгебраические эквиваленты некоторых свойств
239
элементы viC, v2C принадлежат AQ и совпадают. Значит, V^
сверхамаль-
гамируем. П Л Е М М А 6.4, Пусть класс У'4"' амальгамируем, А и В — формулы, Т^=±{С £ For(P(A) П Р(В)) | A \-L С } . Ясли Г f/L В, mo Л \fL В. ДОКАЗАТЕЛЬСТВО является модификацией доказательства соот ветствующей леммы в [10]. Пусть Р 0 ^
Р{А) П Р(В),
Т\ т± {В* £
£ For(P(J3)) | Г h L В'}, Г2 ^- {А' £ For(P(A)) | A h L А'}. Очевидно, что Гх и Г 2 являются L-теориями, В <£Т\ и А Е Т 2 . Нетрудно доказать, что Ti П For(Po) = Т2 П For(Po). В самом деле, если С 6 Т\ П For(P 0 ), то Г \~ь С. Значит, А Ь^ С и, следовательно, С € Т2. Обратно, если С £ Т2, то А Ьх С и, значит, С £ Г С Ть Положим Г 0 ?=± 2\ П For(Po) = Т2 П For(Po). Для г = 0,1,2 пусть Л,- -
алгебра
Линденбаума—Тарского теории Г,-. Заметим, что все указанные алгебры локально-финитарны, т.е. принадлежат
V^\
Определим отображения i\ : Ло -> Л х и г2 : AQ —> Л 2 по правилу п||С||то — ЦСНтх и г 2 ||С|| То ^ ||С||т 2 для всех С £ For(P 0 ). Легко дока зать, что i\ и г2 являются гомоморфизмами. Проверим, например, условия гомоморфизма для гх и операции s%-: ч«*-||С||т0 = ^И^СЦть = ||^C' / || T l = = ^-ЦС'Цт! = ^J-||C||TI = 5 ^ I | | C | | T 0 J г Д е С" ~ некоторая конгруэнтная фор муле С формула, для которой допустима замена переменных s* С'. Условия гомоморфизма для других операций проверяются аналогичным образом. Так как для любых C,D £ For(Po) верна цепочка эквивалентностей ||С||т 0 - \\D\\ro <=> C - D G T o ^^
II^IITI
= ||-D||TI
И
ЦС||Т2
Ф=> C = D£T1HC~D£T2
= ||^1|т 2 »
то
h
и
<=*
^2 являются мономорфизма
ми. Поскольку класс V^
амальгамируем, найдутся алгебра Л в у(^) и
мономорфизмы ei : А\ ~* Л и €2 : Л 2 -> Л такие, что eiii = е2г2. Для каждого предикатного символа/? полагаем:
(
ei\\p(x0,...
,a:#p~i)||Tn
е2\\р{х0,...
, а?#Р-1)||та, если р Е Р(А),
Т
если р G Р(В), в остальных случаях.
240
Д. Е.
Тишковский
Отображение v корректно определено для р G Ро, так как ei||p(a?o,... . . . ,s#p-i)||7i = вгНК^о, .-•
=
eiii||p(a?o,... ,a?# P -i)||r 0
»S#P-I)HT2-
=
е2г2\\р(х0,...
,Z#P_I)||T0
=
Кроме того, A i ^ ( z 0 , . . . » « # P - i ) = Де,-||р(а? 0 ,...
. . . , ## P -i)||Ti С Д||р(ж 0 ? • • • » ##p-i||r,- С # р . Следовательно, по лемме 1.4, г; продолжается до означивания в алгебре Л . Нетрудно доказать, что vC - eiHCHm если С 6 F o r ( P ( B ) ) , и vC = е 2 ||С||т 2 , если С Е БЪг(Р(Л)). Итак, В £ Т ь т.е. ||B||ri
< "Г. Значит, vB = е ^ ^ Ц т !
< Т , так
как ei — мономорфизм. Подобным образом, из А £ Т 2 заключаем, что и А — Т . Значит, A Y^A В . И, наконец, поскольку L полна относительно V^\
получаем A \fL В . П Л Е М М А 6 . 5 . Если класс
обладает
сверхамалъгамируем,
то логика
L
ИС.
Д О К А З А Т Е Л Ь С Т В О . Идея доказательства принадлежит Л . Л . Ма ксимовой [8, 9]. Пусть L Ь A D В , Р 0 ^± Р ( А ) П P(J3), Л 0 , Л х и А2 алгебры Линденбаума—Тарского логики L в языках Ро, Р ( А ) и Р(В)
со
ответственно. Заметим, что все указанные алгебры локально-финитарны, т. е. принадлежат V^K
Очевидно, что AQ вложима в алгебры А\ и Л 2 при
помощи отображений %\ и г2 соответственно, определенных равенствами ч\\С\\цРо)
^ \\С\\ЦР{А))
и i 2 | | C | | L ( f t ) ^ \\С\\цР(в)),
С е For(Fo).
w
Так как F ( ' сверхамальгамируем, то найдутся алгебра А в V^ мономорфизмы ei : А\ -> Л и е2 : Л 2 —> А такие, что e\ii
и
= е2г2 и д л я
всех ai E |«Ai | и а 2 € | Л 2 | eifli < е 2 а 2 <=> Эа 0 £ |Ло|(а1 < 4 a 0 & «2^0 < ^2), ^2^2 < ^ i a i <=> Эа 0 £ |Ло|(а 2 < г 2 а 0 & 1га0 < а\). Д л я каждого предикатного символа р полагаем: ei||p(a:o, • • • , vp(xQ,...
, s # p - i ) ^ < ег|Ь(я?о,... Т
S#P-I)||L(P(A))>
,S#P-I)||L(P(B))>
если
Р е Р(^),
если р 6 Р ( В ) , в остальных случаях.
Используя рассуждение из доказательства леммы 6.4, заключаем, что v корректно определено, продолжается до означивания в алгебре Л , vC ~
241
Алгебраические эквиваленты некоторых свойств = ^I\\C\\L(P(A))J
если С € For(P(A)), и vC = е 2 ||С||ь(р(в)).
если
С €
еБЬг(Р(в)). Поскольку L h A D В, то г?(Л Э В) — Т, т.е. vA < vB. Значит, e
i|Hlli/(F(yi)) < е2\\Щь(Р(В))- Класс V^
сверхамальгамируем, поэтому су
ществует С из For(Po) такая, что ||Л||цр(Д)) < *I||C||L(P 0 ) = ||C||L(P(A)) и ||C|| L (P(JB)) = «гЦСЦцА,) < ||В||ь(Р(В))« Таким образом, L Ь А Э С и L\~ С Э В,т.е. формула С является Интерпол янтом формул А и В, что и требовалось доказать. • ТЕОРЕМА 6.6. Пусть L — суперинтуиционистская логика, полная относительно некоторого многообразия V
предикатная квазицилиндри
ческих алгебр. Следующие условия эквивалентны: (1) L обладает ИСВ (ИС); (2) класс V^
амальгамируем
(сверхмальгамируем).
ДОКАЗАТЕЛЬСТВО. (1) => (2) следует из леммы 6.2. (2) => (1). Пусть У Н амальгамируем. Пусть А Ь^ J3. Значит, для Г из условия леммы 6.4 выполняется Г \~L В. Таким образом, для некоторого конечного подмножества Го множества Г верно Го KL В. Пусть С — конъ юнкция формул из Го- Так как С принадлежит Г, то A \~L С Кроме того, С Ьх В. Таким образом, С — интерполянт формул А и J3. В случае, когда y(w) сверхамальгамируем, утверждение теоремы следует из леммы 6.5. D
ЛИТЕРАТУРА 1. Д.Е. Тишковский, Об алгебраической семантике для суперинтуиционист ских предикатных логик, Алгебра и логика, 38, N 1 (1999), 68—95. 2. Ю. Л.Ершов, Е.А.Палютин, Математическая логика, М., Наука, 1979. 3. Е.Расёва, Р. Сикорскищ Математика метаматематики, М., Наука, 1972. 4. L. Maksimova, On maximal intermediate logics with disjunction property, Stud. Log., 45, N 1 (1986), 69-75. 5. A. Г. Драгалин, Математический интуиционизм. Введение в теорию дока зательств, М., Наука, 1979. 6. L. Maksimova, Explicit and implicit definability in modal and related logics, Bull. Sect. Log., Univ. Lodz, Dep. Log., 27, N 1/2 (1998), 36-39.
242
Д. Е.
Тишковский
7. Л. Л, Максимова, Теорема Крейга в суперинтуиционистских логиках и амальгамируемые многообразия псевдобулевых алгебр, Алгебра и логика, 16, N б (1977), 643-681. 8. Л. Л. Максимова^ Интерполяционные теоремы в модальных логиках и амальгамируемые многообразия топобулевых алгебр, Алгебра и логика, 18, N 5 (1979), 556-586. 9. Л, Л. Максимова, Модальные логики и многообразия модальных алгебр: свойства Бета, интерполяция и амальгамируемость, Алгебра и логика, 3 1 , N 2 (1992), 145-166. 10. J. Czelakowski, Logical matrices and the amalgamation property, Stud. Log., 4 1 , N 4 (1982), 329-341.
Адрес автора: ТИШКОВСКИЙ Дмитрий Евгеньевич, РОССИЯ, 630090, г. Новосибирск, пр. Ак. Коптюга, 4, Институт математики СО РАН. e-mail: [email protected]
Поступило 22 июля 1999 г.
