Полная версия

Главная arrow Логика arrow КАТЕГОРНАЯ ЛОГИКА

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Свободные экспоненциальные дедуктивные мультикатегории

Для данного мультиграфа G мы можем сконструировать им- пликативные исчисления D(G) и свободную экспоненциальную дедуктивную мультикатегорию Fr(G), порожденную G. Объекты этой мультикатегории получаются индуктивно из объектов G с помощью операции Ее секвенции получаются из секвенций G путем присоединения базисных секвенций 1А, гАв, >л т. д., и формирования новых операций из старых с помощью правил (-)Е, (-)' и т.д. Наконец, тождества между сравнимыми секвенциями в FlG) будут те и только те, которые следуют из тождеств в G, и мульти- категорные тождества

Помимо этого, добавляются еще и тождества и т. п., рассмотренные ранее.

Введем теперь понятие мультифунктора, используя следующие определения:

Определение 1. Мультифунктор F из дедуктивной мультикатегории М в дедуктивную мультикатегорию М' представляет собой отображение класса объектов М в класс объектов М' вместе с отображением из класса стрелок М в класс стрелок М такие, что если f. А1 ... АпI- В есть стрелка в М, то F(J): F(A,) ... F(An)h F(В) есть стрелка в /И'и F( lA) = 1^,, F{g F(g) ( F(f)).

Определение 2. Экспоненциальный мультифунктор F из экспоненциальной дедуктивной мультикатегории М в экспоненциальную дедуктивную мультикатегорию М' представляет собой мультифунктор, сохраняющий экспоненциальную структуру, т.е.

Пусть U будет стирающим мультифунктором, тогда мультифунктор G->L/F(G) будет, как известно, полным и точным [Lambek 1993] (полнота свидетельствует о том, что мультифунктор не порождает никаких новых секвенций по сравнению со старыми, а точность свидетельствует об отсутствии новых тождеств между секвенциями).

Пусть G будет б’/ДСИ'Л'-мультикатегорией. Для экспоненциального С/ВСИА-мультифунктора F (т.е. сохраняющего BCWK- структуру G) имеет место следующая теорема:

Теорема 1. (устранение сечения). Если стрелки е, /, р, у, w, к заменить на правила {-}, (-)", (-)г,В (-)*, то любая секвен

ция в UF(G), сконструированная с помощью правил сечения, будет эквивалентна секвенции, сконструированной без применения правила сечения.

Доказательство. Для доказательства, прежде всего, без потери общности допускаем, что стрелки / At- Aug: ГЛДЬ- В уже были получены без применения правила сечения. Позднее покажем, 4Tog (/ Эквивалентна секвенции, в конструировании которой были вовлечены сечения меньшей "степени", причем степень сечения g (/ Определяется как

где с/(А) есть число вхождений всех импликаций в А и с/(Г) = d(A,) + ... + + d(Am). Возможны следующие случаи:

  • 0. И/и g содержатся в G.
  • 1. На последнем шаге конструирования / вводится импликация по левую сторону стрелки.
  • 2. На последнем шаге конструирования g вводится импликация по левую сторону стрелки, но не в А.
  • 3. На последнем шаге конструирования g вводится импликация по правую сторону стрелки.
  • 4. На последнем шаге конструирования и/и g вводится импликация по правую сторону.

В случае 0 стрелка g(J) уже содержится в G, замкнутой относительно сечения. Рассмотрим теперь по очереди остальные случаи. Начнем со стрелок с импликацией.

(1) Пусть А = Г '(A' D В') А'Д' и/= g'{f'}. В этом случае мы имеем:

Заменим это выражение на:

где новое сечение имеет меньшую степень. Более того,

' gig'{/'}>= gr'}>»=ggig[1])^} что означает, что обе стороны сводятся к одной и той же секвенции в силу определения (- }и {-}.

(2) Пусть ГАА = Г'(А' дэ В')А'А', g = g'{f'}. Допустим, что А содержится в А'= А]АА2. Тогда мы имеем:

Заменим это выражение на:

где новое сечение имеет меньшую степень. Более того,

что означает, что обе стороны сводятся к одной и той же секвенции в силу определения (- )и {-}.

Случай, когда А содержится в Г', аналогичен, и его можно опустить. Однако, остается случай, когда А содержится в Л'= Л1ЛЛ2. Тогда мы получаем:

Заменим это выражение на:

(сечение)

где новое сечение имеет меньшую степень. Помимо этого, согласно определению (-)е.

Отсюда в силу единственности стрелки г получаем тождество

означающее, что обе стороны сводятся к одной и той же секвенции. (4)А =Л' zDBf=f е иg = g’{h). Мы имеем:

Заменим все это на:

где новое сечение имеет меньшую степень. Более того,

в силу определений и свойств (-), {-} и (-)

Для константы Т случай 3 невозможен. Рассмотрим оставшиеся случаи.

Заменим это выражение на:

где новое сечение имеет меньшую степень. Более того,

откуда обе стороны сводятся к одной и той же секвенции.

(2) Допустим, что Г = Г'ТД' и g = g ". Мы имеем:

Заменим это выражение на:

где новое сечение имеет меньшую степень. Более того,

откуда g'' (/>= (g '(f))' в силу единственности /. [2]

(1) Пусть Л = (АЪВ')А' и/=/. Если мы имеем дело с g:VAA- В, то вначале с помощью /-стрелок приводим g к виду g: ЯДЬ В. Затем мы получаем:

Заменим это выражение на:

где новое сечение имеет меньшую степень. Более того, легко видеть, что g(f' р>= (g(f » р.

(2) Пусть ГАА = А' (А' з В') A', g = Допустим, что А содержится в Д' = Д1ЛД2. Тогда имеем:

[3] [4]

Заменим все это на:

При этом g'p (/'р )= (g'(/'p ))р (следует в силу тождеств GIBCWK- экспоненциальной мультикатегории).

Для перестановки возможны следующие случаи:

(1) Пусть Л = А'В'А' и/=/'т. Если мы имеем дело с g: ГААЬ- В, то вначале с помощью /-стрелок приводим g к виду g: ЛАН В. Затем получаем:

Заменим это выражение на:

В силу тождеств С/ВСЖЛГ-экспоненциальной мультикатегории получаем g(f >= (g{f »т.

(2) Пусть YAA = А'В'А', g-g' у. Допустим, что А содержится в А' = Д|ЛД2. Тогда имеем:

Заменим это выражение на:

В силу тождеств С/ВСВ'й'-экспоненциальной мультикатегории получаем g'r (/ )= (g'_(f))Y.

(3) Пусть А = А'В'А',/=fn, АА = CD'A', g = g'y. Допустим, что А содержится в Д' = Д[ЛД2. Тогда имеем:

Заменим все это на:

В силу тождеств б/ЙС'В'Л'-экспоненциальной мультикатегории получаем g' у(/'у >= (g/'т »у.

Для сокращения получаем:

(1) Пусть А=А'А'А' и /=/'*’. Если мы имеем дело eg: ГЛД1- В, то вначале с помощью /-стрелок приводим g к виду g: A Ah В. Затем получаем:

Заменим это выражение на:

В силу тождеств С/ДСВ'ЛГ-экспоненциапьной мультикатегории получаем g,M)= (g(f ))w.

(2) Пусть ГАА = A'A'A', g = g'w. Допустим, что А содержится в А' = AiAA2, Тогда имеем:

Заменим это выражение на:

В силу тождеств GIBCWЙГ-экспоненциапьной мультикатегории получаем g'w(f )= (g'.(/»w.

(3) Пусть Л = А'А'А',/ = f'w, ГАА = C'D'A', g = g'w. Допустим, что А содержится в Д' = А[А А2. Тогда имеем:

Заменим все это на:

В силу тождеств б'/ВСТТВ-экспоненциальной мультикатегории получаем g'’(/'w >= (g'(f'w »"•

Для ослабления получаем:

(1) Пусть А = А'А' и/=/' к. Если мы имеем дело с g: ГЛДЬ В, то вначале с помощью /-стрелок приводим g к виду g: АД1- В. Затем получаем:

Заменим это выражение на:

В силу тождеств ЫВЫгК--экспоненциальной мультикатегории получаем g(f'K)= (gif'»".

(2) Пусть ГАА = A'A', g = g' к. Допустим, что А содержится в Д'= Д|ЛД2. Тогда имеем:

Заменим это выражение на:

В силу тождеств GIBCWK-экспоненциальной мультикатегории получаем g'Kif)= (g’Af))*-

(3) Пусть Д = /ГД',/=/, ГЛД = С A', g = g'K. Допустим, что А содержится в Д' = Д|ЛД2. Тогда имеем:

Заменим все это на:

В силу тождеств б’/ВОТА-экспоненциальной мульти категории получаем g'K{f'K )= (g'{f к ))к, что и заканчивает доказательство. ?

(3) Пусть А = (A'zdB')A' и/=/'р. Если мы имеем дело с g.VAAh В, то вначале с помощью /-стрелок приводим g к виду g: A Ah В. Затем мы получаем:

Заменим это выражение на:

где новое сечение имеет меньшую степень. Более того, легко видеть, что g(f' р>= (gif' » р.

(2) Пусть ГАА = A' (A' z> В') Д', g = g,(1. Допустим, что А содержится в Д' = Д|ЛДг. Тогда имеем:

Заменим это выражение на:

Более того, легко видеть, что g' р (/ )= (g'_i /)) р в силу тождеств G/BCWAT-экспоненциальной мультикатегории.

(3) Пусть Д = (А' з В')Д',/=/' р, ГАА = D' (D' С) A', g = g' р. Допустим, что Л содержится в Д' = AAAi. Тогда имеем:

Заменим все это на:

При этом g"p (f'[5] >= (g'p »p (следует в силу тождеств GIBCWK- экспоненциальной мультикатегории).

Для перестановки возможны следующие случаи:

(1) Пусть А = А'В'А' и/=/'у. Если мы имеем дело с g: ГАА- В, то вначале с помощью /-стрелок приводим g к виду g: АА- В. Затем получаем:

Заменим это выражение на:

В силу тождеств G1BCWK-экспоненциальной мультикатегории получаем g(f V (gifr-

(2) Пусть ГА А = А'В'А', g = g'у. Допустим, что А содержится в Д' = Д1ЯД2. Тогда имеем:

Заменим это выражение на:

В силу тождеств GIBCWА'-экспоненциальной мультикатегории получаем g1 т(/ )= ШЛ)г-

(3) Пусть А = A'B'A',f=fn, АА = CD'A', g - g''. Допустим, что А содержится в Д' = Д^Дт. Тогда имеем:

Для сокращения получаем:

(2) Пусть А = А'А' А' и Если мы имеем дело с g: ГЛД1- В,

то вначале с помощью /'-стрелок приводим g к виду g: АЛЬ- В. Затем получаем:

Заменим это выражение на:

В силу тождеств GIBCWK-экспоненциальной мультикатегории получаем ?{/'")= (gif' »*•

(2) Пусть ГАА = A'A'A', g = g"v. Допустим, что А содержится в А' = Д|/)Д2. Тогда имеем:

Заменим это выражение на:

В силу тождеств GIBCWIf-экспоненциальной мультикатегории получаем g'"(f >= (g'_{f)T.

(3) Пусть А = A'A'A',f- f'w, Г/4Д = CD'A', g = g'"'. Допустим, что А содержится в А' = AAAi. Тогда имеем:

Заменим все это на:

В силу тождеств С/ВСЖВ-экспоненциальной мультикатегории получаем g'w(f'w )= (g'(f'w ))w?

Для ослабления получаем:

(4) Пусть А = А'Д' и/=/' к. Если мы имеем дело с g: ГЛДН В, то вначале с помощью /-стрелок приводим g к виду g: ААг- В. Затем получаем:

Заменим это выражение на:

В силу тождеств G1BCWK-экспоненциальной мультикатегории получаем g(f'*)= {gif' ))к.

(5) Пусть ГЛД = A'A', g = g1 к- Допустим, что А содержится в Д'= ААА2- Тогда имеем:

Заменим это выражение на:

В силу тождеств С/ВС/ЕА-экспоненциальной мультикатегории получаем g'Kif )= (g'_{f))K.

(6) Пусть А = A'A',f=f'K, ГАА = СД', g = g'K. Допустим, что А содержится в Д' = AAA2. Тогда имеем:

Заменим все это на:

  • [1] Заменим все это на: где новое сечение имеет меньшую степень. Более того, что означает, что обе стороны сводятся к одной и той же секвенциив силу определения (- )и {-}.
  • [2] А = Т,/ = i и g = g ". Мы имеем: Но g "(/ )= g' была сконструирована и без сечения. Перейдем теперь к правилам слабой транзитивности, перестановки, сокращения и ослабления. Для доказательства, прежде всего, вновь без потери общности допускаем, что стрелки f. ЛЬ- Aug:ГАА~ В уже были получены без применения правила сечения.Возможны случаи: 1. На последнем шаге конструирования / используется дополнительное правило. 2. На последнем шаге конструирования g используется дополнительное правило. 3. На последнем шаге конструирования и /и g используетсядополнительное правило. В случае слабой транзитивности получаем:
  • [3] Заменим это выражение на: Более того, легко видеть, что g' р (/ )= (g'( /)) 15 в силу тождествС/вС/Т/Г-экспоненциальной мультикатегории.
  • [4] Пусть Д = (А' з B')A f=f р, ГАА = D' (?>' з С) Д', g =g'15. Допустим, что А содержится в Д' = ААА2. Тогда имеем:
  • [5] Заменим все это на:
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>