Содержание к диссертации
Введение
1 Предварительные сведения 8
2 Дизъюнктивное свойство в классе расширений минимальной логики 16
2.1 Дизъюнктивное свойство напарников паранепротиворечивых расширений минимальной логики 17
2.2 Дизъюнктивное свойство логики Lf 22
2.3 Дизъюнктивное свойство логики Lkp 30
2.4 Другие примеры паранепротиворечивых логик с DP 40
3 Канонические формулы для расширений минимальной логики 44
3.1 Алгоритм выделения 50
3.2 Опровержимость на модельной структуре 61
3.3 Канонические формулы 66
3.4 Некоторые приложения техники канонических формул для расширений минимальной логики 77
3.4.1 О моделях паранепротиворечивого аналога логики Скотта 77
3.4.2 О моделях паранепротиворечивой логики Lskp . 109
Литература и работы автора по теме диссертации 117
- Дизъюнктивное свойство логики Lf
- Другие примеры паранепротиворечивых логик с DP
- Опровержимость на модельной структуре
- Некоторые приложения техники канонических формул для расширений минимальной логики
Введение к работе
Одним из бурно развивающихся направлений современной неклассической математической логики является область па,ранепрот,иворечивых логик — логик, которые допускают противоречивые, но нетривиальные теории. Паранеиротиворечивые логики позволяют осуществлять нетривиальные выводы из противоречивого множества гипотез. Логики, в которых все противоречивые теории тривиальны, называют избыточными. Объективной основой появления паранепротиворечивых логик является стремление отразить средствами логики специфику мышления человека о переходных состояниях, которые наряду с устойчивостью и относительным покоем наблюдаются в природе, обществе и познании, и в разной степени связаны с логическим понятием противоречивости. Противоречивые данные возникают на судебных заседаниях; в дискуссиях, полемике, в научных теориях (прежних и новых) и других сферах интеллектуальной деятельности.
Предшественниками паранепротиворечивой логики как нового вида неклассической формальной логики явились логики Н.А. Васильева и Я. Лукасевича. Как новый вид математической логики паранепротиво-речивая логика разрабатывалась в работах польского логика Ст. Яськов-ского. Бразильский математик Н.да Коста, занимающийся исследованиями в области паранепротиворечивой логики, отмечал, что в общем случае эта система должна удовлетворять следующим условиям: во-первых, из двух противоречащих формул (р и ~мр в общем случае нельзя вывести произвольную формулу ф; а, во-вторых, дедуктивные средства классической логики должны быть максимально сохранены, поскольку они — основа всех обычных рассуждений (в первую очередь должен быть сохранен закон modus ponens). История паранепротиворечивой логики изложена в работе [4].
Паранепротиворечивая логика связана со многими видами иекласси-ческих логик: с модальной логикой (системой S5 К.Льюиса), с многозначными логиками, с релевантной логикой, где тоже не принимается принцип ex contraditione quodlibet: противоречие влечет все, что угодно. Отвергая этот принцип, паранепротиворечивая логика позволяет изучать феномен противоречия сам по себе.
Минимальная логика Lj (или, иначе, логика Иоганссона), предложенная И.Иоганнсоном в 1936 году в процессе критики принципа "противоречие влечет все, что угодно" в конструктивных рассуждениях, заслуживает особого внимания как паранепротиворечивый аналог интуиционистской логики Li. Аксиоматика Lj получается вычеркиванием ех contraditione quodlibet из стандартного списка аксиом интуиционистской логики, а именно: Li=Lj+{_L 3 р].
Как оказалось, в логике Lj для любых формул <р; ф можно доказать, что
В свою очередь, это означает, что связка отрицания теряет смысл в противоречивых Lj-теориях, поскольку в таких теориях доказуемо отрицание любой формулы. Этот результат объясняет тот факт, что минимальная логика долгое время находилась вне внимания специалистов по паранепротиворечивости. Однако, в последнее время появились многочисленные работы, посвященные логике Иоганссона, в частности, работы С. Одинцова, в которых изучается класс JHN расширений логики Lj [16, 17, 18, 19, 20, 21].
В указанных работах найдена одна важная черта, отличающая класс Lj-расширеиий от классов расширений избыточных интуиционистской Li и модальной К4 логик. Класс JHN имеет нетривиальную, в некотором смысле трехмерную, глобальную структуру, что позволяет свести его описание, до определенной степени, к хорошо изученным классам промежуточных и позитивных логик. Как оказалось, класс JHN является дизъюнктным объединением трех классов: известного класса промежуточных логик INT; класса NEG, состоящего из негативных логик (дефинициально эквивалентных позитивным), содержащих схему -\р, и класса PAR собственно паранепротиворечивых расширений минимальной логики, содержащего все логики, не попавшие в первые два класса. В работах С. Одинцова для любой логики L Є PAR определяется ее интуиционистский напарник Lint (негативный напарник Lneg) как наименьшая логика из класса INT (соответственно, из класса NEG), содержащая логику L. Там же показано, что имеются сильные трансляции (т.е. сохраняющие отношение следования) логик Ь^ и Lneg в исходную логику L. Тот факт, что существует решеточный гомоморфизм решетки PAR на прямое произведение INT и NEG мотивирует попытку исследования связей между логиками указанных классов, обладающими определенными свойствами, в частности, дизъюнктивным свойством [DP).
Проблема дизъюнктивного свойства логик впервые была поднята в связи с рассмотрением частного аспекта: закона исключенного третьего (tertium поп datur). утверждающего, что одно из двух высказываний <р или -чр является истинным. Л.Брауэр подверг серьезной критике специфику действия данного закона при наличии "неопределенности" в познании и сделал вывод о том, что tertium поп datur применяется лишь там, где познание имеет дело с жесткой ситуацией: или—или, истина—ложь, что, в определенном смысле, отвергается и в контексте паранепротиворе-чивости. Отказавшись в общем случае от закона исключенного третьего и построив интуиционистскую логику, многие исследователи заинтересовались более общим вопросом о наличии дизъюнктивного свойства у произвольной логики.
Гипотеза Лукасевича 1952 года о том, что дизъюнктивное свойство является характеристическим свойством интуиционистской логики (т.е. интуиционистская логика является единственной промежуточной логикой с DP) индуцировала исследования указанного свойства в классе INT. В частности, были выделены логики Крайзеля-Патнема КР и Скотта SL — первые собственные расширения интуиционистской логики, обладающие дизъюнктивным свойством (см., например, [11,15]). Кроме того, было показано, что существует континуум промежуточных логик с DP [24]. Наиболее полно результаты, касающиеся этой тематики, изложены в обзоре [7].
Дизъюнктивное свойство логики Lf
В предыдущем параграфе было показано, что дизъюнктивное свойство негативного напарника логики класса PAR полностью определяется наличием DP у данной паранепротиворечивой логики и определенным в предыдущем параграфе условием на соответствующие отображения вида /Л. В СВЯЗИ С вышеизложенным представляется интересным вопрос о наличии дизъюнктивного свойства у логики Lf, определяемой упомянутым условием. Прежде обратимся к некоторым необходимым в дальнейшем фактам. Теорема Диего [11] Для любого п 0 множество Еп формул, построенных из пропозициональных переменных pi, рч,..., рп с использованием связок Л, 3 и -і, содержит конечное число попарно неэквивалентных относительно Li формул. Предложение 2.9. В произвольной j-алгебре любое замыкание конечного множества элементов относительно операций Л, D конечно. Доказательство. Для доказательства нам потребуется следующий простой факт. Лемма 2.1. Пусть А.п замыкание множества {ci\, ...} (} элементов j-алгебры А относительно операций А. Э- Тогда Ап имеет наименьший элемент. Доказательство. Индукцией по сложности соответствующих термов покажем, что элемент х=а\ Л Й2 Л ... Л ап является наименьшим в Ап. 1. Для любого г, 1 і п, выполняется: х щ. 2. Пусть bk Є An, k Є An и x bk, x Ь\. Тогда x bk A k и ж fy bk D bi по свойствам импликативных решеток. Таким образом, для любого элемента Ъ Є Ап имеем ж 6. Продолжим доказательство предложения 2.9. Пусть А- произвольная j-алгебра сигнатуры (Л, V, D, -L), Ап - замыкание множества элементов {ai, ... , аП) 1} из А с помощью операций A,D. В силу леммы 2.1 Ап имеет наименьший элемент _!_ . Рассмотрим j-алгебру В сигнатуры (Л, V, Э, -1 ) с универсумом В-А. Пусть Вп - замыкание множества {ах, ... , ап, ±} относительно Л, D, - (- а-а Dl/). Ясно, что ВП=АП. С другой стороны, Ъп есть замыкание конечного множества элемен тов рейтинговой алгебры В1 относительно Л, D и - . Согласно Теоремы Диего, Вп конечна, а значит конечна и Ап. Предложение 2.10. (Аналог теоремы Диего для минимальной логики) Пусть Ф( рь ... , (рп) - множество всех формул, построенных из произвольных формул tpi, f2, , fn (п I) с помощью константы _1_ и логических связок Л, D. Тогда множество где [ р] - класс эквивалентности относительно Lj, конечно.
Доказательство. Пусть Fu- ш-порожденная свободная j-алгебра. Известно, что элементами Fw в точности являются классы эквивалентных формул. Множество , определенное в формулировке теоремы, можно рассматривать как замыкание множества {[ /?i], , [фп]} относительно Л, D, _L. Согласно предложению 2.9 указанное замыкание конечно. Определим следующий класс конечных шкал Крипке: Cf {/І = (И , R, Q) множество W конечно и \/х є W множество \х] t П Q либо пустое, либо имеет наименьший элемент}. Теорема 2.1. Логика Lf характеризуется классом Cf. Доказательство. Покажем корректность логики Lf относительно указанного класса шкал. Предположим, что существует шкала ji Є Cf такая, что fi F. Тогда существует элемент XQ Є W, для которого что имеет место в том и только том случае, когда существует такой элемент у Є W, что х$Яу и Последнее в свою очередь равносильно следующему: Если {у} П Q=0, то . Q для любого из конуса {у} j , а это противоречит условиям Зтг є W(yRn n Е Q я п р), Зт Є W(yRm, т Є Q и т Y= q) указанной выше цепочки равносильных преобразований. Если {у} t П Q имеет наименьший элемент , то іійг, tRm, следовательно і \ Р V q, что противоречит конъюнктивному члену Vz((yRz и GQ)= 2;=pVg) упомянутой цепочки. Корректность показана.
Полнота. Пусть Lf И фй для некоторой формулы ф$. Тогда существует такое Lf-полное множество х такое, что ф$ . ж, и, следовательно, по теореме о канонической модели, формула ф$ опровергается на Л4ъ{ Пусть Ф0 множество всех подформул формулы -00; Ф замыкание Фо U {-L} относительно Л и D. Рассмотрим модель Mf—{T, Я , Q , V) -фильтрацию Мы по Ф, где Т есть множество классов эквивалентности (х у & хГ\ Ф=Ї/ П Ф), Q ={[a;] Є Т \ J-Є ж} (важно отметить, что Q ф 0; действительно, так как Lf КІЗ р, то Qbf 7 0; тогда существует по крайней мере один элемент хо Є Qif, причем (XQ П Ф) 3 {_L}, следовательно существует по крайней мере одни класс эквивалентности [жо], принадлежащий конусу Согласно аналогу теоремы Диего для Lj, множество Ф содержит конечное число попарно неэквивалентных относительно Lj формул. Тем более Ф содержит конечное число попарно неэквивалентных относительно Lf формул. Любое множество х Є 2bf вместе с каждой формулой ср содержит и все формулы, эквивалентные ц относительно Lf, поэтому имеется лишь конечное число вариантов пересечения множеств х и Ф. Значит, множество V конечно. По теореме Фильтрации М № ф. Покажем; что шкала // модели М принадлежит классу Cf. Предположим противное, пусть существует такой элемент [XQ] Є Т", что множество {[XQ]} t П Q непусто, причем определяется несравнимыми элементами [жі], ... , [хп], т.е. [у] Є {[XQ]} f Л Q -» [sj]# M для некоторого j. По определению R! для любого элемента [у], не сравнимого с [XJ]} существует такая формула Ф, что Xj \= фу и у фу. Пусть Qj=f\y Фу Тогда Xj (= qj, и так как множество Ф замкнуто относительно Л имеем, что qj Є Ф, следовательно [XJ] [= (. Лемма, жо f= X D Vj Q JJ где XQ Є Хи является представителем класса
Другие примеры паранепротиворечивых логик с DP
В этой части мы определим два континуальных класса собственно пара-непротиворечивых расширений минимальной логики с дизъюнктивным свойством. Прежде сформулируем некоторые дополнительные факты. Пусть L Є JHN. Индукцией по длине формулы f определим выражение \i f ("слэш Клини") аналогично тому, как это было сделано в [7, 5] для промежуточных и модальных логик (далее вместо \і ip и \ i (р будем писать \ ь (р): Предложение 2.12. Пусть Lx Є INT. L2 Є NEG и L\ Є DP. Если Доказательство. Пусть Ь р (далее в доказательстве опустим нижний индекс L\ L2). Индукцией по длине вывода покажем, что (р. 1. Проверим истинность данного утверждения для аксиом L\ Li (a) Случай аксиом Lj легко проверяется; (b) Для аксиом L\ L2 вида J.D ф. где ф Є L% заключение предложения очевидно, так как ІД -Ц (с) Индукцией по построению I(tp), ір Є L\} покажем, что Ь 1{ір) влечет }1( р). Базис индукции очевидно имеется, так как L\ непротиворечива, а значит \/ь ь2 Р V ±, то есть \/L L2 1{р); Пусть 1{ р), 1(ф) таковы, что [Ь 1{(р) = \1((р)] и [(- Цф) =3- /( )](индукционное предположение). (1) Если \- 1{(р) Л І(ф) то Ь /( ) и Ь 7( ), и по индукционному предположению \1( р) и 7( ); (2) Если Ь 7( ) V 7( ), то f- 7( ) или h 7(г). Так как Ьг є 7)Р, и по индукционному предположению Ь 1((р) или \- 1[ф): (3) Если Ь /(t/з) D 7(-0) и j Ь /( /?), то h 7( ) и по индукционному предположению [/( ), а значит по определению получаем j/((/? 3 гі ) и в этом случае. 2. Пусть (/з получена по modus ponens из ф, ф D (р. Тогда но индукционному предположению ф и ф D (/з, следовательно, по определению \ф D ip имеем (J Ь ч/ = /з, а значит /з. Предложение 2.13. Пусть Ьг Є INT, L2 Є NEG u І! Є DP. Тогда свободная комбинация L\ Ь% обладает дизъюнктивным свойством. Доказательство. Пусть Li L \ рУф} тогда согласно предложению 2.12 іі іг V , а значит Ь іа или Ь , то есть Li L2e DP. Учитывая, что существует континуум промежуточных логик с -DP [7], мы нашли класс собственно паранепротиворечивых расширений Lj с дизъюнктивным свойством мощности континуум. В предыдущем параграфе мы исследовали паранепротиворечивый аналог логики Крайзеля-Патнэма, полученный расширением минимальной логики Lj аксиомой Крайзеля-Патнэма. Можно поступить иначе: расширить Lj с помощью интуиционистской трансляции I(tp) формулы (р. Доказанный в [18] важный факт о том, что Lj + 1{ф] — (Li -f { /?}) Ln, дает возможность легко утверждать, что всякое расширение минимальной логики вида Lj 4- Ц р)-, где tp - некоторая формула, обладает DP. В работах [17, 18, 25] рассматривается так называемая логика Гливенко Lg = Lj + {—і— C-L- P)} наименьшая среди логик , удовлетворяющих известной теореме Гливенко: для любой формулы (, Lk h ip = L Ь -і-к . Релятивизоватшя логика Гливенко G(L\, L2) в интервале Spec(Li, L2) определяется в [17, 18] следующим образом: Предложение 2.14. [17, 18] Для Ь\ Є INT, L2 Є NEG эквивалентны следующие условия: Как было замечено ранее, логика і Ґ1 Л2 заведомо не удовлетворяет DP. Предложение 2.15. Пусть Ьг є INT, L2 Є NEG, Lit DP и G — G{L\}L%). Если he , mo \G P Доказательство. Пусть h p. Индукцией по длине вывода формулы р покажем, что \gip. Истинность данного утверждения для аксиом L\ L2 уже проверена в доказательстве предложения 2.12. Покажем, что \G -i(_L D р). По определению имеем \G -(1 Dp) ([\-G (X Э р) D X и G (X D p) D 1] \G -1). Так как h(j -1-1 (X D p) и l/c X, имеем \fg (1 D p) D X. Случай, когда формула (p получена no modus ponens, рассматривался в доказательстве предложения 2X2. D Предложение 2.16. Пусть LY є INT, L2 Є NEG и L{ Є DP. Тогда релятивизованпая логика Гливенко G{L\, L2) обладает дизъюнктивным свойством. Доказательство непосредственно следует из предложения 2.15. Последнее предложение показывает, что все логики класса реляти-визованных логик Гливенко с интуиционистским напарником, который обладает DP, лежат в классе всех логик с DP. Таким образом, мы нашли еще один класс собственно паранепротиворечивых расширений Lj с дизъюнктивным свойством мощности континуум. Как и в случае свободной комбинации, дизъюнктивное свойство описанного выше класса ре-лятивизованных логик не зависит от дизъюнктивного свойства их негативных напарников.
Опровержимость на модельной структуре
Набор a={ai,..., ап} элементов шкалы fJ.=(W: R, Q) называем открытым набором модели М., если п = 0 или существует такое разбиение Пєтг что для любой формулы (р из множества Sub((po) U {J-}. В случае, когда такого разбиения нет, набор а называем закрытым. Замечание. Пусть а - некоторый набор элементов шкалы (j, = {Wt R, Q), а Ъ - набор минимальных элементов набора а (относительно порядка R). Так как (Va Є a)(36 Є 6)(6#a), имеем (Va Є a) (36 Є 6)(6 = ір = а \= (р). Поэтому, легко видеть, что набор a открыт в М открыт тогда и только тогда, когда открыт набор 6. Одноэлементный набор всегда открыт. Далее рассмотрим М = {W,R,Q,S \=) - некоторую контрмодель формулы о модель M+—(W+, R+, Q , Up(W+), \ +) и частичный р-морфизм /+, построенные ранее. Имеет место следующее Предложение 3.4. Пусть а Є f+l{W+) t W. Тогда 1. набор /(af) открыт в М+; 2. если a Q, то а Є f+\W+ \ Q+) і W. Доказательство. Пусть а Є f+1(W+) "\ W, p - произвольная формула из множества 5w6( o)U{l}. Рассмотрим регулярное разбиение Пй- Если у Є ПІ, т0 Vi Є a t имеем /; Є ПІ- Так как Vb Є f+l(W+) Пь=П/+(ь), то Vy Є /+(а t) получаем у Є Пг/ то есть Обратно, пусть ір ПЯ тогда по указанному ранее условию существует Ь Є f+l(W+) такой, что aRb и J]o = П?г Следовательно /+(6) Є /+(а t) и V П/+(ь) а значит tp І Гк/+(аТ) ПІ Доказательство второго утверждения легко следует из того, что Va Є U\W+ t)(36 Є /+"1( +))(аЯ6 и Па - Ш- Модельную структуру 2Jti={Wi, Яі, Qi, 5і) называем допустимой для конечной коитрмодели M=(W,R)Q}Up(W))\=) формулы щ, если существует частичный р-морфизм / из Ш\ на (W, R, Q), удовлетворяющий следующим условиям Теорема 3.1. Формула (ро опровержима па модельной структуре SDti тогда и только тогда, когда Ш\ допустима для некоторой коитрмодели М є . Доказательство. Необходимость. Действительно, если Ш\ щ, то строим с помощью алгоритма выделения шкалу / , соответствующую модели М-1 Є Y w Далее воспользуемся предложением 3.4 и свойствами MJ Достаточность.
Пусть М (W, R, Q, Up(W), \ ) - контрмодель щ из множества } , а Wli={Wi, R\,QuSi} допустима для М то есть существует частичный р-морфизм / : ЗЯі— (W: R, Q), удовлетворяющий условиям ( ) и ( ) предыдущего определения. Рассмотрим подструктуру Wl2=(W2: i?2j Q2j $2) модельной структуры Щ?і, порожденную множеством f l(W). Покажем, что 0 щ. Тогда ПО Теореме О ПОрОЖДеНИИ ПОЛуЧИМ, ЧТО ЭДТ - ipQ. Зададим па шкале {W2, R2, Q2) отношение =2 Для произвольной формулы ip из множества Sub( pa) U {_L} следующим образом: t если а Є f 1{W)i то пусть пусть а f 1(W), тогда а е /" W) t так KaK 9 порождена f l{W). Возможны следующие случаи: (J набор /(at) пуст. В этом случае а Є Qb так как иначе а Є /_1(И0 t \Qh а значит а Є І "1(ИЛ\(3) -і- и набор f(a t) не пуст, противоречие. Положим fl набор /(a f) не пуст. Тогда по ( ) набор /(a t) открыт. Пусть разбиение [J Є 0, причем у Є [ =Ф- tp Є ПГ=іПаі a-i Є f(a t) для любой формулы (р Є Sub((po) U {_L}. В этом случае положим Понятно, что в этом случае Ъ \=-% J- {= а Є Qi. Далее мы покажем, что отношение =2 удовлетворяет семантическим правилам. 1. a \=2 tpi D (p2 Va fai a и a =2 -Pi = а! j=2 ) Действительно, так как а Ц i/5i D (/ == /(e) j= i D 2 имеем: если a 2 i 3 v?2 = f(a) Vi 3 2 = Зж Є И (/(а)Дж, ж \= (p\,x \ = 1 2) == (по определению частичного р-морфизма) 3b Є f 1(x)(aR2b:b \= (phb p2)- Обратно, пусть a \=2 pi D щ. Рассмотрим произвольный элемент & такой, что аД2&: 1). если Ъ Є f l{W), то (6 \=2 pi = Ь 2 tp2); иначе /(a) iD / 2). если 6 0 f l{W) и /(6 t) = 0, т0 (6 =2 Vi == 6 j=2 V2) по определению ОТНОШеНИЯ [=2.; 3). если Ь / (W) и /(6 t) 7 0, то (& 2 Vi = 6 N2 Ы; иначе, ЄСЛИ Ъ \=2 VI И 6 2 V2) т0 V j Є /(6 t) Имеем ( Є ПЦ И Зж;- Є /(6 t) такой, что (f2 Па;-) а значит xj \ Ч \ 2, следова-тельно, /(a) fttpiD Щ 2. a 1=2 і. = а Q2. Пусть a [=2 -L, тогда /(a) [= _L
Следовательно a Є Q2, так как /-1(Q) Q2- Обратно, пусть а Є () тогда /(a) Є Q, а значит /(a) f= 1 и а =21. 3. a 2 фі 3 P2 Va (ai22a и a \=2 i = a h=2 Vz) Пусть a =2 (pi Э v?2, следовательно pi 3 2 Є П . гДе П e nw и f Є П V e ПГ=ІПОІ Для всякого Of Є /(a t) и произвольной формулы /? Є Sub(ipo) U {_L}. В этом случае, получаем, что Рі Є П == 2 П Тогда для любого а7; Є /(a t) имеем а,: [=: = а{ (= 2, то есть f \ai (=2 yi) == /"Ч О Нз Рг- О другой стороны, для любого элемента а Є а такого, что /(a t) = 0 выполняется а [=з р для произвольной формулы р Є Sub(tpo) U {і-}. Таким образом, Va fai a и а =2 ц \ влечет Обратно, пусть a 2 /ч 3 2, тогда (pi D ф2 $. Yl Следовательно Фі 2 . ИІІ Для некоторого aj Є f{a t). Тогда /_1(ОІ) И=2 і Э 2-По пункту 1. настоящего доказательства получаем, что существует элемент а! такой, что $ 1{а{)К2а! и а1 [=2 щ и а1 2 Щ-, а значит 3a (ai?2fl и а 2 Ц \ и а 2 щ) Все остальные случаи рассматриваются аналогично. Кроме того, существует ЙЕІ 2 такой, что a J 2 о- Действительно, так как М щ. то существует XQ Є W такой, что XQ щ. Пусть а Є /_1(жо), тогда а Є И 2 и кроме того, aj 2 Ро Далее покажем, что {а Є W% \ а =2 РІ} Є - Для всякой атомарной формулы из 5м6((/?о) U {_L}. По определению имеем, что #2-{( Cj И 2 (3(7 Є S{){G2 = GC\ W2)}, следовательно W2 Є % Кроме того, Q2—Q1 П W2, а значит и ( Є 1. Далее, ПуСТЬ {Жі, ..., Хг} - ВСе Те Элементы ИЗ W. ДЛЯ КОТОРЫХ Xj \/= р, где р - некоторая атомарная формула из Sub((po) U {_!_}, 1 j г. Тогда /_1(ж;) 2 Р и Va Є f l{%j) і имеем a 2 . Пусть a Є f l(W) t и a 2 P- Тогда Если /(a t) 7 0; то по условию ( ) набор f(a t) открыт. Значит существует регулярное разбиение Yl такое, что
Некоторые приложения техники канонических формул для расширений минимальной логики
Логика Скотта SL-Li+{(- p Э р) D pV p) Э -ipV-v-ip] (в дальнейшем аксиому Скотта будем обозначать через S) изучалась в работах [8, 15], где определена ее семантика в терминах шкал Крипке и различными методами доказано ее дизъюнктивное свойство, Оказалось, что паранепро-тиворечивая логика Ls=Lj+S обладает моделями, исследовать которые проще в технике канонических формул. Однако прежде, мы определим местоположение Ls в соответствующем интервале Spec(Lsint,l,sneg). Непосредственно по определению получаем, что
Предложение 3.5. (Ls)int = SL и (Ls)„es = Ln. Таким образом, Предложение 3.6. Пусть А — произвольная j-алгебра. Имеет, место следующее: А = Ls, если и только если для любого элемента (%,у) Є А выполняется {{{- -,х D х) А /А(У)) Э (ж V -їх)) D (-їх V -і-із) = 1. Доказательство. Пусть (ж, у) Є А1 Ху А - произвольная пара, тогда простое вычисление дает следующее: (((((ж, у) D (1,1)) = (1,1)) D (ж, у)) = (ж, у) V ((ж, г,) Э (1,1))) D мы опускаем нижний индекс Д в случаях когда это не вызывает двусмысленности) П Условия, накладываемые на соответствующие отображения /А ИЗ нижней алгебры, ассоциированной с А, в верхнюю, хотя и являются несколько громоздкими, однако дают возможность определить расположение Ls в интервале [SL Ln; SL П Ln]. Доказательство. Покажем, что Ls отлична от конечных точек интервала [SL Ln;SL П Ln]. Рассмотрим модель А логики SL Ln, устроенную следующим образом. Верхняя алгебра А1 модели А имеет носитель {1,х і,Ж2,, 1}, где % 1, 1 #1 z, 1 Ж2 z и элементы жі и ж2 несравнимы (заметим, что обычная проверка дает возможность утверждать, что при любом означивании переменных выполняется (( -пж D ж) D arVt) D —ire V —і—їж = 1 на А1, то єсть A1 [= SL). Нижняя алгебра Аі - 4-х элементная алгебра Пирса с носителем {0, уі,У2, І}, где 0 уі 1, 0 г/г 1 и элементы гд, г/2 несравнимы; /(1) = 1, /(уі) — ж1; /(у2) = Ж2, /(0) =1. Понятно, что (жі,г/і) Є А. Вычислим а это в свою очередь доказывает, что Ls отлична от нижней точки интервала 5pec(SL,Ln). Далее, рассмотрим модель логики Ls, отличную от прямого произведения гейтинговой и негативной алгебр. Пусть В - - 4-х элементная булева алгебра с носителем {Л,жі,Ж2,1}, где Х х\ 1, Х xi 1 и элементы х\ и Х2 несравнимы. Пусть С — 4-х элементная негативная алгебра С НОСИТелеМ {0,у-[,У2, -L}, ГДЄ 0 ух Х, 0 1/2 -L И Элементы ух, 1/2 несравнимы; /(X) = 1, f(y) —X для всех у Є С т.ч. у Х. Определим А Ї=І В X/ С, тогда, согласно представлению j-алгебр, элементами А и только они. Вычислим значение ((( х D х) А /А(У)) 3 (ж V -їж)) D (- ж V - x) для каждого элемента А. Таким образом, А = Ls и /л не является тождественным, что и тре буется. В работе [12] было показано, что промежуточная логика Скотта SL Li + S аксиоматизируется относительно интуиционистской логики Li канонической формулой вида X(p,V,±.), шкала Крипке которой р имеет вид: Как оказалось, аксиоматизация каноническими формулами паране-противоречивой логики Ls Lj + S имеет более сложную структуру. Определим пять конечных j-шкал специального вида, с выделенными на них некоторыми d-областями. Через 7?i=(VFi, Лі, Q\ = 0) определим шкалу вида: и Т {({х2,х5},{х4})}; Через 5=( 5,- 5)05) определим шкалу вида: Доказательство.
В силу полноты всякого расширения минимальной логики относительно реляционной семантики, для доказательства нам достаточно показать, что всякая модель логики Ls является моделью логики 10+/(41, )+7(42,2 )+7( , )+7(44,2 )+ ( 5) и обратно. Пусть %R={Wy Ry Q, S) —- произвольная модельная структура. Лемма 3.6. Если Wl = S, гп,о Ш J(4i, )+7(42,2?2)+7(4з, &)+J(m, )+7(45, &). Доказательство. Пусть Ж \ S, тогда существует контрмодель М = {дЛ, \=) такая, что а \= (- р Dp) D р V р ж а - р V -i-ip для некоторого элемента а Є М. В дальнейшем для краткости будем обозначать формулу (- р D р) D (р V - р) через Т. Рассмотрим множество Если А\ ф 0, определим частичное отображение f\ : Ш — щ следующим образом: ж о, если а (Е А\\ х\, если а = X, а = J_ D р, а = р D X иа і; /і(а) — ( 2і если а [= X, а = 1 3 р, а[= - -ір, а\ф р, иа 1; х з, если а ) X, а (= J_ D р, а ) р ио[ 1; не определено, иначе. Если множество А\ = 0, то рассмотрим множество Если Л2 ф 0, определим частичное отображение Д : 9Я — щ следующим образом: Если множество Ач = 0, то рассмотрим множество А3={а Є 1 а = X, а -р V -пір и а = ((р D 1) Л (_L Э р)) D 1}. Если А% ф 0; определим частичное отображение /з : 9Я — следующим образом: XQ, если а Є A3; хі, если а \= Т, а \= р D X, а \= ((р D J-) Л (1 D р)) Э _L и /з(а) л жз, если а (= Т, а {= р, а Ц ((р Э -L) Л (_L Э р)) 3 1 и а Х; Ж4, если а [= Т, а = X ий р; не определено, иначе. Если множество А% — 0, то рассмотрим множество Л4—{а Є Wj а ]= Т, а -лр V -i-ip, 36 Є W(aift ,6 h Р Э -Li 6 N (J- Э р) D X, 6 X Э р, 6 X) и 36 Є W{aRb,b pD 1,6 h -L = Р, Ь X)}. Если А4 7 0; определим частичное отображение Д : 3 — Щ следующим образом: жо, если а Є А4;
