Паранепротиворечивая логика в CN-категориях

В настоящее время существует много паранспротиворечивых логик, поэтому оговоримся сразу, что мы будем иметь дело главным образом с пропозициональным исчислением С„ (1 <п<со которое было введено бразильским логиком Н. да Костой [da Costa 1963] в 1963 г. Первая алгебраизация этих логик была получена самим да Костой [da Costa 1966] и позднее исследована им вместе с А.М. Сетте и М. Фиделем. Проблема существования алгебры Лин- денбаума для С_п оставалась долгое время открытой, пока К. Мор- тенсен не обнаружил, что не существует отношения эквивалентности для С„, позволяющего получить нетривиальную фактор-алгебру [Mortensen 1980]. В некотором смысле стало очевидным, что алгебраический эквивалент этих исчислений вообще не может быть получен.

В 1984 году В. А. Карниелли и Л. П. Алькантара [Camielli Alcantara 1984] сформулировали понятие алгебры да Косты, отражающей большинство логических свойств С„. Было показано, что

алгебра да Косты изоморфна паранепротиворечивой алгебре множеств, которая могла бы приниматься в качестве эквивалента сто- уновской теоремы о представлении для булевых алгебр. Однако подобная аналогия законна только с неклассической точки зрения: некоторые операции в паранепротиворечивой алгебре множеств сформулированы не в обычных теоретико-множественных терминах.

Ввиду того, что наши теоретико-категорные конструкции существенным образом основываются на алгебре да Косты, для дальнейшего употребления приведем полные определения[СагшеШ Alcantara 1984, р.81].

Определение 1. Под алгеброй да Косты будем понимать следующую алгебраическую структуру

такую, что для каждых а,Ь,с в S выполняются следующие условия:

Если существует xeS, такой, что неверно, что хлх' = 0, то про алгебру А говорят, что она представляет собой собственную алгебру да Косты

Предложение 1. Если А = (S, 0, 1, <, a, v, з, ' )является алгеброй да Косты, то имеют место следующие свойства:

Доказательство. Очевидно. ?

Модификация конструкции N-категории с целью получения так называемых CN-категорий, позволяющих нам передать свойства алгебры да Косты, дает нам возможность получить версию категорией семантики С„. Следует отметить, что существуют альтернативные категорные семантики для паранепротиворечивых логик, например, Мортенсена-Лаверса-Джеймса основывающиеся на ко- гейтинговых алгебрах (см. [Mortensen 1980]).

В дальнейшем мы покажем, что так называемые CN-алгебры, чья конструкция приводится ниже, позволяют преодолеть многие из трудностей, связанных с алгебраизацией паранепротиворечивых логик.

Определение 2. CN-категория представляет собой категорию предпорядка С, снабженную контравариантным функтором W:C—>С, такую, что

• (i) С имеет конечные произведения (-,-), копроизведения [-,-] и С дистрибутивна по отношению к ним, т.е. ([а,6],[а,с])= [а,(Ь,с)] для любых объектов а,Ь,с в С;
• (ii) С имеет терминальный объект 1 и инициальный объект 0, 1 = [a,Na] and 0 = (a°,Na°), где а⁰ = N(a,Na);
• (Ш)для каждого объекта а в С существуют стрелки N² a-hi и a°—>(Na)° in С;
• (iv) С допускает экспоненцирование;
• (v) а—>6 есть стрелка в С тогда и только тогда, когда а => b = 1 для любых двух объектов а, b в С, где а => b является экспоненциалом;
• (vi) для любых двух объектов а,Ь в С существует стрелка

Легко проверить, что любая CN-категория имеет следующие свойства:

экспоненциал а => h в С будет резидуалом;

С декартово замкнута;

у -> х есть стрелка в С тогда и только тогда, когда (х,у)= у и

[х.у]= х;

каждая CN-категория имеет, по меньшей мере, три объекта. Дадим интерпретацию в терминах CN-категорий следующего списка аксиом и правил вывода [da Costa 1963, р.3790]:

Здесь а⁰ есть сокращение для —i(aA-ia). Эта аксиоматика фактически описывает систему С паранепротиворечивой логики да Косты.

Примем следующий список в качестве словаря перевода высказываний в CN-категории:

Процесс интерпретации аксиом и правил вывода очевиден. Например, интерпретацией А5 будет а => (Ь => (а,Ь). Но утверждение, что это аксиома, означает, что а => (b => (a,b)) = 1, что по (v) дает нам стрелку а —> b => (а,Ь>.

Мы получаем исчисление С„, когда подставляем вместо А11 -А 15 следующие аксиомы:

где а⁽"⁾ (0<и<м) означает а'ла²л...ла" и а", в свою очередь, означает а^{00 0} , где символ⁰ повторяется п раз.

Нетрудно видеть, что аксиомы AIV-А]5' будут переводиться в CN-категории как и в случае Ci и их переводы схожим образом будут связаны с категорными свойствами CN-категорий.

Определение 3. Пусть Cn и C_N’будут двумя CN-категориями (с функторами N и N' соответственно). CN-функтор F: C_N —> Си- шредставляет собой функтор, имеющий следующие (для а,Ь, 1,0 в Сц и 1 ^,,0^> в C/v):

С помощью соответствующей CN-категорной модификации понятий паранепротиворечивой алгебры множеств и фильтров в алгебрах да Косты можно доказать следующие предложение [Camielli Alcantara 1984, р.81-82]:

Предложение 2. Каждая CN-категория имеет полное расширение. (Полнота означает здесь существование бесконечных произведений и копроизведений).

Предложение 3. Пусть А,В,С будут CN-категориями, где В является расширением А и С является полной. Любой CN-функтор F: А —» С может быть расширен до CN-функтора Н: В —* Е.

В дальнейшем С будет обозначать CN-категорию.

Пусть р есть объект С и обозначим через С_р категорию С_р = {х: р—есть стрелка в С},

чьи стрелки совпадают со стрелками С. Если мы определим N_p:C_p—> С_р как NpX=[Nx,p], то тогда легко видеть, что N_p будет кон- травариантным функтором, таким, что пара (C_P,N_P) становится CN-

категорией с р в качеегве инициального объекта и 1 в качестве тер-

о

минального. Ясно, что при таком определении (Npa,a^p) будет играть роль N-функтора в N-категориях, в то время как С_р будет очевидным образом CN-категорным обобщением полных фильтров в алгебре да Косты.

Пусть Е будет непустой совокупностью элементов С. Для п>2 рассмотрим

и определим

Заметим, что в сущности эти (Е) являются совокупностями CN- категорных переводов фильтров в алгебрах да Косты.

Определение 4. (Е) максимально, если не существует ?' с С, такого, что (Е) с (?') с С.

Свойства (Е) допускают, что совокупность может быть интерпретирована как множество доказуемых высказываний теории. Элементы (?) можно было бы понимать как аксиомы и рассматривать их как порождающие доказуемые высказывания, т.е. аксиомы (и их конъюнкции) «влекут» доказуемые высказывания.

Определение 5. CN-категорная интерпретация системы С„ представляет собой пару (С,(Е)), которая описывает множество высказываний вместе с доказуемыми высказываниями.

Логика (С,(Е)) синтаксически непротиворечива, если не имеет места, что и высказывание и его отрицание одновременно доказуемы, что эквивалентно неравенству (?) * С. В N-категориях <a,Na) = О, что ведет к тривиализации логике в случае противоречивости. В

CN-категориях (a,Na) S 0 и имеет место более слабое условие (ii),

т.е. (a°,Na°) = 0, что приводит к противоречивости (С,(Е)), но без тривиализации.

Логика (С,(Е)) синтаксически полна, если для любого высказывания Р мы имеем либо ре(Е), либо {Np,p°)e(E), но не одновременно (взамен ре(Е) или Npe(E) в случае N-категорий). Это означает, что невыполнение подобного условия преобразует (Е) в (||0|| —> ||1||), следовательно (Е) будет максимальным.

Случай теорий с конечным числом аксиом (что может быть сведено к их конъюнкции) дает нам Е = {р,...,р_п} и (Е) = Е_р с р = (р,...,р„). Отсюда (С,(Е)) является полным тогда и только тогда, когда р является минимальным относительно упорядочения, индуцированного на С.

Рассмотрим пару (С,(Е)) - категорный перевод паранепротиво- речивой логики. Пусть В будет нетривиальной CN-категорией. Как

и в случае N-категорий мы вводим понятие оценки, допускающей, что каждая CN-категория имеет, по меньшей мере, три элемента.

Определение 6. В-оценка есть CN-функтор V: С —»В, такой, что:

Оценка V называется сингулярной, если существует такой ре С, что Vp = VNp = 1 и нормальной в противном случае. Объект ре С называется истинным по отношению к V, если Vp = 0.

Если (С,(Е)), как в случае N-категорий, называлось бы семантически непротиворечивой (т.е. если бы существовала оценка V, такая, что реС влечет Vp = 1), то по отношению к сингулярной оценке (С,(Е)) было бы противоречивой. Но в то же время (С,(Е)) будет нетривиальным, поскольку (Vp,VNp) = (1,1) = 1. В общем случае (С,(Е)) будет противоречивым, но нетривиальным, если мы примем во внимание, что любая CN-категория имеет, по меньшей мере, три элемента.

Определение 7. Модель (С,(Е)) есть В-оценка V, такая, что Vp = 1 для всех ре С.

Согласно вышесказанному (С,(Е)) имеет модель, что не означает, что (С,(Е)) будет непротиворечивой, но лишь свидетельством ее нетривиальности.

Определение 8. (С,(Е)) семантически полна, если имеет место следующее: р доказуемо (т.е., ре(Е)) тогда и только тогда, когда р истинно во всех моделях (С,(Е)).

Теорема /. (С,(Е)) семантически истинно.

Доказательство такое же, как в случае N-категорий с (А/р,р°)вместо Np. Ш