МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени В.М. ЛОМОНОСОВА

На правах рукописи

ШИЯН

Тарас Александрович

СТРУКТУРНЫЕ ОПИСАНИЯ МНОЖЕСТВ

ФОРМАЛЬНЫХ ТЕОРИЙ

(на материале формальных силлогистик)

Специальность 09.00.07 – логика

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата философских наук

Научный руководитель – доктор философских наук, профессор В.А. Бочаров Москва 2008 Оглавление Список сокращений и некоторых обозначений

Введение

I. Теоретико-методологические основания §1. Реляционные систематизации

§2. Построение структурных описаний

§3. Основные понятия теории формальных теорий

§4. Сравнение формальных теорий

II. Структурное исследование языков формальных силлогистик (алфавиты, классы термов, классы формул) §1. Алфавиты

§2. Термы

§3. Формальные языки (классы формул)

§4. Заключение: системное описание языков

III. Чистые позитивные силлогистики в языке LS §1. Обзор силлогистик в языке LS

§2. Расширения С4: обзор и соотношения с другими теориями.............. §3. Расширения С4: характеристические семантики

§4. О построении счетного класса расширений C=

IV. Соотношение силлогистик в других языках §1. Обобщенные силлогистики

§2. Негативные силлогистики

§3. Сингулярные силлогистики аристотелевского типа

§4. Сингулярные силлогистики оккамовского типа

§5. Заключение: граф негативных и сингулярных расширений С2, ФС и С4

Заключение

Список литературы

Приложение. О некоторых ограничениях формально-математической методологии

Список сокращений и некоторых обозначений др. – другие. ППТ – правильно построенный терм.

е.т.е. – если и только если. ППФ – правильно построенная формула.

КЛВ – классическая логика с. – страница.

высказываний (независимо от см. – смотрите.

языка). т.е. – то есть.

КЛОП1 – классическая логика т.о. – таким образом.

одноместных предикатов т.п. – тому подобное.

первого порядка. ЧУ частично упорядоченное – ЯЛОП1 язык логики (множество).

– одноместных предикатов df. – definitio, определение.

первого порядка.

Некоторые математические обозначения A( ) – алфавит теории. + – объединение с замыканием. В L( ) – язык (класс ППФ) зависимости от контекста: объединение теории. теорий или присоединение к теории новой «аксиомы».

T( ) – класс ППТ теории.

в зависимости от Буквы n, k, l, m, r, i, j (возможно, с || – контекста, мощность индексами), если не оговорено иное, множества или значение обозначают целые положительные формулы в семантике. числа.

Ссылки на литературу В квадратных скобках через запятую указываются фамилии авторов и через пробел год издания работы (если на один год в Списке литературы приходится несколько работ данного коллектива авторов, то после года идет латинская буква). После указания года через запятую могут идти номера страниц из указанного издания. Если подряд идут ссылки на несколько работ, то они разделяются точкой с запятой. Если подряд идут ссылки на несколько работ одного автора (коллектива авторов), то фамилия (фамилии) не повторяется и указываются только годы издания (и, если нужно, буквы) через точку с запятой.

Актуальность темы. За последний век построено огромное количество различных формальных теорий, показано существование счетных и континуальных классов формальных теорий. Например, описан счетный класс конечно-значных логик Лукасевича, счетный класс собственных расширений силлогистики Лукасевича-Смирнова [Шиян 2002e, 2004a], континуальный класс суперинтуиционистских логик [Янков 1968]. Число индивидуально описанных теорий давно измеряется сотнями. Так, за последние 25-30 лет в русскоязычной литературе описано более формальных силлогистик (и теорий в силлогистических языках). связи с этим, обзор, систематизация, сравнительный анализ построенных теорий является насущной задачей для более эффективной ориентации в материале и интенсификации дальнейших исследований. Одним из необходимых шагов является «картографирование» пространства уже описанных в литературе теорий. Использование языка графов дает возможность наглядного представления результатов подобных компаративных исследований.

Степень разработанности проблемы. У нас в стране и за рубежом идут активные исследования соотношения формальных теорий, изучаются различные классы теорий, строятся структурные систематизации отдельных групп формальных теорий. К сожалению, исследования эти во многом разорваны, сравнение теорий не перерастает обычно в построение структурных систематизаций. В рамках построения структурных систематизаций ограничиваются обычно сравнением чистых пропозициональных логик с неполными наборами связок. Автору известен ряд исследований, в которых соотношение теорий представляется в виде графов теорий, но эти исследования касаются только импликативных и модальных пропозициональных логик.

Если в сравнительном анализе силлогистик автор существенным образом опирался на работы В.И. Маркина ([Маркин 1991] и др. из списка литературы в конце работы), то идеей графического представления соотношений теорий автор обязан работам А.С. Карпенко [Карпенко 1993;

1995; 1997a-b; 1999a-b; 2001]. Причем, именно под влиянием Карпенко сформировалась установка автора, что получение (и обоснование) графа теорий может быть целью и основным результатом подобного рода сравнительных исследований. В области изучения модальных логик можно, например, указать статью Томаса Шнайдера [Schneider, 2005], в которой строился граф (соотношения по дедуктивной силе) 25 нормальных модальных систем.

В области изучения предикатных логик вообще и силлогистических теорий, в частности, мне подобные работы не известны. Исключением составляют две работы В.А. Смирнова [Смирнов 1983b, 4; 2002, 155], в которых он представляет соотношение четырех формулируемых им теорий (С1, С2, С3, С4) в виде графа.

В литературе описаний специальных методик, направленных на доказательство адекватности графа теорий, автору также не известно.

Методика, используемая Карпенко в [Карпенко 1993; 1995; 1997a-b; 1999ab; 2001], обеспечивает адекватность графа, но нацелена на достижение несколько других задач, чем простое построение графа теорий. Часто же ограничиваются доказательством наличия между теориями отношения нестрогого включения по множеству теорем, а строгость порядка (попарное представления на графе отношения «включение по множеству теорем»

принимаются как очевидные.

Научная новизна исследования.

Работа имеет научную новизну в двух аспектах: методологическом и предметном.

Методологический аспект. Во-первых, в работе вводится понятие структурной систематизации, как особой интеллектуальной процедуры, систематизирующей объекты через задание на них некоторой структуры (решетки, дерева и т.п.), и проводится различение между структурной систематизацией (в общем случае) и классификацией (как процедурой построения иерархии таких разбиений). Такое различение является важным, поскольку в литературе часто построение структур теорий называют классификацией, хотя никаких разбиений на классы при этом не производится. Вводится представление о частном случае структурных систематизаций, при котором систематизирующего эффекта добиваются путем задания на множестве (систематизируемых) объектов некоторого отношения частичного порядка. Адекватным описанием (представлением) такой систематизации будет граф особого вида, называемый обычно диаграммой Хассе.

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

В-третьих, сформулированные методы построения структурных систематизаций конкретизируются применительно к формальным теориям.

В частности, выделяется особая методика (на основе сводных таблиц аксиоматик) построения адекватных структурных систематизаций (по множеству теорем) исчислений и формальных теорий, не применимая для систематизации объектов произвольной природы.

Предметный аспект. Основные результаты диссертации состоят в построении структурных систематизаций (на основе отношения включения по множеству теорем) нескольких групп формальных силлогистик и теорий в силлогистических языках. Доказывается адекватность построенных систематизаций. Всего в работе представлены результаты исследования около 50-и формальных теорий. Результаты исследований представлены в виде 5 графов (структурных систематизаций) теорий. До работ автора изученные теории не исследовались с точки зрения построения графов ни на основе их соотношения по множеству теорем, ни по иным основаниям.

В качестве дополнительных предметных результатов можно указать следующие. Построен и изучен ряд расширений «силлогистики Лукасевича» С4, показана расширяемость С4 (следовательно, и всех ее подтеорий, среди которых различные реконструкции силлогистических учений Аристотеля, Уильяма Оккама, Льюиса Кэрролла, Б. Больцано, фундаментальной силлогистики) до теории эквивалентности (равенства).

Для этого расширения и ряда других расширений С4 построены силлогистические теоретико-множественные семантики стандартного типа и показана их адекватность. Предлагается способ построения счетного ряда конечно-аксиоматизируемых расширений С4 и силлогистических семантик для этих теорий.

В диссертации уделяется специальное внимание – насколько известно автору, впервые – рассмотрению соотношения языков (классов формул), классов термов и алфавитов формальных теорий. Строятся структурные систематизации 27 алфавитов, 10 классов термов и 28 классов формул (языков); демонстрируется адекватность построенных графов. Хотя это исследование в диссертации носит вспомогательный характер, по мере роста количества сравниваемых теорий (в разных языках) роль и необходимость таких сравнений будет возрастать. Кроме того, на основании этих систематизаций, в работе применяется новый метод классификации, при котором классификация объектов одной группы осуществляется за счет построения структурной систематизации объектов другой группы, сопоставленных объектам первой группы. В частности, построенные структурные систематизации языков (классов формул), классов термов и алфавитов формальных силлогистик могут использоваться для классификации силлогистических формальных теорий (или исчислений) по признаку эквивалентности по языку, по классу термов или по алфавиту, соответственно. Такие разветвленные теоретические классификации являются альтернативой традиционным дихотомическим делениям силлогистик (по классу термов) на позитивные и негативные, сингулярные и чистые (несингулярные) и т.п. или выделению отдельных типов силлогистик (расширенные, обобщенные, васильевского типа, сингулярные аристотелевского типа и т.п.).

Цель и задачи исследования. Целями работы были: формулирование логико-методологического аппарата, необходимого для построения структурных систематизаций теорий и доказательства их адекватности, и исследование группы бескванторных предикатных теорий (формальных силлогистик и сродных с ними систем) с точки зрения их соотношения по множеству теорем. В качестве задачи бралось исследование сформулированными методами, построение и обоснование адекватности структурных описаний нескольких групп формальных силлогистик; при этом, область исследования ограничивалась теориями, удовлетворяющими совокупности следующих условий: (1) построение на базе классической логики высказываний (КЛВ) в языке без кванторов и модальных операторов, (2) формулировка в виде аксиоматического исчисления, (3) наличие описания в русскоязычной литературе (по преимуществу, в достаточно узком круге периодических изданий).

Методологические основания. Работа и по предмету исследования, и по применяемым методам относится к области так называемой символической логики. Круг привлекаемых в работе математических дисциплин задается, в первую очередь, объектом исследования и аспектом его изучения. Объектом исследования являются «формальные теории" (термин заимствован мной у В.А. Смирнова, в частности, применялся в [Смирнов 2002]; понятие введено А. Тарским, в частности, использовалось в [Tarski 1956]), которые понимаются как множества формул (того или иного формального языка), замкнутые относительно некоторого набора правил вывода. Отсюда, помимо аппарата современной символической логики, обращение к теории множеств, топологии, абстрактной алгебре, ориентация на методологию формализма. Формальные теории исследуются с точки зрения наличия отношения включения (по множеству теорем), которое является частным случаем отношения частичного порядка, что обуславливает обращение к теории бинарных отношений, теории частично упорядоченных множеств, теории решеток. И, наконец, поскольку результаты исследований представляются в виде графов, то необходимо обращение к теории графов.

Центральным методологическим понятием работы стало понятие диаграммы Хассе как особого представления частичного порядка на антитранзитивный ориентированный граф, вершинами которого являются элементы ЧУ множества, а связи соединяют только ближайшие (относительно представляемого порядка) элементы множества. При этом, направление связей обозначается на графе не стрелками, а считается направленным снизу вверх (если не оговорено иное).

Для того, чтобы показать, что некоторый граф G является диаграммой Хассе некоторого множества M, частично упорядоченного отношением R, нужно:

1. Показать, что множество вершин графа G есть в точности множество элементов M. Для этого необходимо и достаточно показать, что a) каждая вершина G представляет некоторый элемент M;

b) разные вершины G представляют разные элементы M;

c) все элементы M представлены вершинами на графе G.

2. Показать, что каждой паре вершин, непосредственно соединенных на графе G связью, соответствует пара элементов M, находящихся в отношении R.

3. Показать, что каждой паре вершин, между которыми нет пути на графе, соответствует пара элементов M, не находящихся в отношении R.

4. Поскольку диаграмма Хассе является результатом т.н. транзитивной редукции (т.е. изображаются связи только между «ближайшими»

элементами ЧУ множества), то необходимо убедиться, что на графе нет связей между вершинами, если между ними есть путь, идущий через другие вершины.

«содержательные»

упорядоченные множества и некоторые др. имеют формальные математические модели одного типа: упорядоченная пара, где M – некоторое множество и R(MM). В разных ситуациях такая пара трактуется то как граф (тогда M – множество вершин, а R – множество связей), то как упорядоченное множество (тогда R – бинарное отношение на M). Этот факт активно эксплуатируется в работе, в первую очередь, за счет совмещенного использования терминологии из теории графов, теории бинарных отношений и теории упорядоченных множеств.

Все рассуждения проводились в рамках классической логики. Для формальных выводов использовался вариант системы натурального вывода, описанный в книге [Бочаров, Маркин 1994], но допускаем также и использование напрямую тех или иных законов классической логики.

Все рассматриваемые силлогистики строятся на базе классической логики высказываний (далее – КЛВ). Ее можно задать пропозициональной частью упоминаемого исчисления натурального вывода из [Бочаров, Маркин 1994] или исчислением со схемами аксиом и единственным правилом вывода modus ponens, например, описанное в [Мендельсон, 49] и расширенное двумя аксиомами для эквивалентности (Мендельсон вводит эквивалентность с помощью определения). В основной части работы этот вопрос больше не оговаривается.

Последовательному введению необходимых понятий и описанию применяемых методик посвящена первая глава.

Основные положения, выносимые на защиту.

– Построенные в работе структурные систематизации формальных теорий (графы 3.1.1, 3.2.1, 4.1.1, 4.2.1), языков (граф 2.3.1), классов термов (граф 2.2.1) и алфавитов (граф 2.1.1) – адекватны, т.е. являются диаграммами Хассе соответствующих частично упорядоченных (отношением ) множеств объектов.

– Построенные в работе фрагменты матриц операций пересечения и объединения языков, классов термов и алфавитов (таблицы 2.1.3, 2.1.4, 2.2.3, 2.2.4, 2.3.4) – корректны, т.е. представленные в них данные верны.

– Теория С4 расширяема до теории эквивалентности (равенства).

– Теории С=, С(2), С(1) адекватны (семантически полны и непротиворечивы) построенным для них семантикам (теорема 3.3.2).

– Теория С= (а значит, и С4) имеет по крайней мере счетное число конечноаксиоматизируемых гильбертовского типа собственных расширений, для которых существуют экстенсиональные силлогистические семантики стандартного вида.

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

Методологические и предметные результаты диссертационного исследования нашли практическое применение и дальнейшую разработку при создании в 2003-2005 гг. в Интернете Информационной системы по формальным теориям Theo.ru (грант РГНФ №03-03-12003в).

Апробация описываемых в диссертации идей, результатов и методов состоялась в ходе обсуждений и дискуссий на кафедре логики философского факультета МГУ, на секторе логики Института философии РАН, в ходе научных конференций. Основные идеи, методы и результаты диссертанта докладывались и обсуждались в ходе следующих научных мероприятий:

1)

Защита дипломной работы на кафедре логики философского факультета МГУ им. Ломоносова (Москва, 2000).

2) 3-я Международная конференция «Смирновские чтения» (Москва, 2001).

3) Международная конференция «Человек – Культура – Общество.

Актуальные проблемы философских, политологических и религиоведческих исследований» (Москва, 2002).

4) VII Общероссийская научная конференция «Современная логика:

проблемы теории, истории и применения в науке» (Санкт-Петербург, 2002).

5) Третий Российский Философский конгресс «Рационализм и культура на пороге третьего тысячелетия» (Ростов-на-Дону, 2002).

6) Ломоносовские чтения 2003 (Москва, 2003).

7) 4-я Международная конференция «Смирновские чтения» (Москва, 2003).

8) Ломоносовские чтения 2004 (Москва, 2004).

9) VIII Общероссийская научная конференция «Современная логика:

проблемы теории, истории и применения в науке» (Санкт-Петербург, 2004).

IX Общероссийская научная конференция «Современная логика:

10) проблемы теории, истории и применения в науке» (Санкт-Петербург, 2006).

Все основные идеи, подходы, методы и результаты диссертанта нашли отражение в публикациях на русском и английском языках, размещенных как в печатных изданиях, так и в научном электронном журнале «Logical Studies». По теме диссертации автором опубликовано 9 статей и 7 тезисов конференций (см. список публикаций). Из них одна статья в журнале из списка ВАК России и одна статья в периодическом сборнике статей из списка ВАК Украины.

Структура диссертации. Диссертация состоит из введения, 4-х глав, заключения, списка литературы, списка сокращений и обозначений и приложения.

Глава I. Методологические основания и общие представления об объекте исследования §1. Реляционные систематизации Рост числа изучаемых некоторой наукой объектов неизбежно приводит к применению и развитию различных способов систематизации объектов.

Известно много разных способов систематизации: классификация, типологизация, построение рядов, различные формы пространственновременной систематизации (периодизация, районирование и т.п.), такие формы теоретической систематизации как параметрическая, дедуктивная, алгебраическая систематизации, и др. (см., например, [Субботин 2001]). В последнее время в логике все больше применяется способ систематизации исследуемых объектов посредством построения на множестве этих объектов различных структур (деревьев, решеток и т.д.) (см. [Смирнов 2002, 155], [Карпенко 1993; 1997a-b; 1999a-b], исследования автора [Шиян 2000a-b; 2002a; 2002e; 2003b-c; 2004a-b] и др.). Буду называть этот способ систематизации структурной систематизацией. Именно его применению (к различным формальным силлогистикам) и посвящена настоящая работа.

Уточним терминологию и используемые обозначения.

Df.1.1.1. Математические медели систематизаций.

a) Алгебраическая систематизация есть множество, где M – множество систематизируемых объектов, а – множество операций на b) Реляционная систематизация есть множество, где M – множество систематизируемых объектов, а – множество отношений c) Реляционно-алгебраическая систематизация есть множество, где M – множество систематизируемых объектов, – множество отношений на M, – множество операций на M.

В ряде случаев алгебраические, реляционные и реляционноалгебраические систематизации дают один и тот же эффект (в этом случае, их иногда смешивают друг с другом), например, в случае различных эквивалентная ей (по систематизирующему эффекту) булева решетка и, наоборот, для всякой булевой решетки существует эквивалентная ей (по систематизирующему эффекту) булева алгебра. Это же верно для псевдобулевых (брауэровых) алгебр и решеток.

Если на множестве M задано произвольное отношение R, то иногда говорят (например, [Лисовский, Марков 2004]), что M произвольно упорядочено отношением R. Особый интерес среди реляционных систематизаций представляют систематизации посредством одного отношения.

Df.1.1.2.

a) Бинарное отношение R на M называется отношением предпорядка (квазипорядка) е.т.е. 1 оно рефлексивно и транзитивно.

эквивалентности е.т.е. оно рефлексивно, транзитивно и симметрично.

c) Бинарное отношение R на M называется отношением нестрогого антисимметрично.

d) Бинарное отношение R на M называется отношением строгого частичного порядка е.т.е. оно антирефлексивно, транзитивно и асимметрично.

e) Бинарное отношение R на M называется диагональным отношением е.т.е. R = { / xM}. Диагональное отношение на M буду обозначать EM.

Здесь и далее – сокращение для связки «если и только если».

Из определений Df.1.1.2 видно, что отношения эквивалентности и нестрогого частичного порядка являются частными случаями предпорядка.

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

a) Если R – нестрогий частичный порядок, то – представляет частный случай структурной систематизации (в том смысле как данный термин определяется ниже и используется в данной работе).

b) Если R – эквивалентность, то – задает разбиение (в традиционной логической терминологии – деление), или элементарную классификацию.

c) Если же R – не симметричный и не антисимметричный предпорядок (на некоторых подмножествах M отношение симметрично, а на некоторых – нет), то буду называть структурной классификацией.

Каждое отношение предпорядка порождает отношение естественной эквивалентности [Драгалин 1979, 77-78]:

Df.1.1.3.a. (x=*y) df (xRy & yRx).

Класс эквивалентности элемента обозначается обычно Отношение R*, заданное следующим образом на фактор-множестве M/=*, является отношением (нестрогого) частичного порядка [Расева, Сикорский 1972, 44]:

Df.1.1.3.b. [x]=*R*[y]=* df xRy.

Таким образом, структурная классификация разбивает M на классы эквивалентности, множество которых получается частично упорядоченным. На основании данных определений, имеет место следующее утверждение.

Утверждение 1.1.1. Если – структурная классификация множества M, то – реляционная систематизация множества M/=* посредством отношения нестрогого частичного порядка R*.

В силу этого факта, распространенности отношения элемент-множество и многочисленности различных отношений эквивалентности, такие реляционные систематизации и структурные классификации переводятся друг в друга, и, имея одну такую систематизацию, можно построить целый спектр связанных с ней систематизаций. Примеры таких переходов приводятся в главе о формальных языках, например, структурную систематизацию классов термов можно интерпретировать как структурную классификацию (по классу термов) языков или как структурную классификацию (по классу термов) формальных теорий. Или, например, структурную систематизацию (отношением ) формальных теорий можно интерпретировать как структурную классификацию (по множеству теорем) исчислений.

В рамках данной работы термином «структурная систематизация» буду обозначать реляционную систематизацию посредством бинарного отношения R, такого, что транзитивное замыкание R, объединенное с диагональным отношением на M, есть отношение нестрогого частичного порядка. Уточнению этого определения посвящен следующий параграф. В качестве отношения частичного порядка выступает отношение быть подмножеством. Для объектов теоретико-множественной природы, которые изучаются в данной работе, это отношение является базовым, естественным упорядочением (терминология по [Драгалин 1979, 78]).

Стоит отметить, что структурные систематизации теорий посредством отношения (строгого или нестрогого) частичного порядка иногда в литературе называют классификациями, что не корректно, поскольку никакого разбиения на классы при этом не производится. Но если систематизация осуществляется посредством отношения предпорядка (не симметричного и не антисимметричного), то такая систематизация уже может называться классификацией. Кроме того, на основании структурной систематизации узком смысле слова), могут быть построены структурные классификации за счет соотнесения каждого из систематизированных объектов с некоторыми объектами из другой группы, как это будет показано в главе, посвященной систематизации формальных языков.

§2. Построение структурных описаний В данном параграфе формулируются основные понятия и методы, необходимые для доказательства основных теорем диссертации – теорем об адекватности построенных систематизаций. Далее, если не оговорено иное, понимается как такая пара объектов, где M – некоторое множество, и RMM.

Пара, где RMM, может рассматриваться не только как упорядоченное множество или реляционная систематизация, но и как ориентированный (направленный) граф, при этом элементы M называются вершинами, а элементы R – дугами (связями) данного графа. Поскольку в данной работе рассматриваются только орграфы, то далее это не оговаривается. В работе понятия теории графов и теории бинарных отношений употребляются обычным образом, но, во избежание путаницы, оговорю основные понятия.

Df.1.2.1. Пусть x, y и z – разные элементы M (попарно не равны).

a) x и y называются ближайшими элементами (вершинами, объектами) в е.т.е. xRy и в M не существует такого z, что xRz и zRy.

b) x непосредственно предшествует y, а y непосредственно следует за x е.т.е. x и y – ближайшие элементы и xRy.

c) Если R, то объекты x и y называются смежными.

d) По отношению к объекту x, пара вида называется входящей дугой (связью), а пара вида – исходящей дугой (связью).

e) Все входящие и исходящие (по отношению к одной и той же вершине) дуги называются смежными.

f) x – минимальный элемент в е.т.е. ни одна пара вида не принадлежит R.

g) x – максимальный элемент в е.т.е. ни одна пара вида не принадлежит R.

Df.1.2.2.

a) Путем S в называется последовательность элементов R следующего вида: S=, где произвольные xi и xj не обязательно отличаются друг от друга.

b) Если S= – путь, то объекты …, x1, x2, x3, …, xn-1, xn называются вершинами пути S.

c) Число пар (число связей), вошедших в путь S (в ), называется длинной пути S в.

d) Если S=, то путь S конечен и называется путем из x1 в xn.

e) Если S= – путь в и xixj при ij, то S называется путем без повторений.

f) Если S=, то путь S называется циклом.

g) Из вершины x (в ) достижима вершина y е.т.е. в существует путь из x в y или из y в x.

h) Вершины x и y называются сравнимыми в е.т.е. в из вершины x достижима вершина y или из y достижима x.

i) x – наименьший элемент (ноль) в е.т.е. для всякого y (yx) в существует путь из x в y.

j) x – наибольший элемент (единица) в е.т.е. для всякого y (yx) в существует путь из y в x.

k) Множество M дискретно относительно R е.т.е. для всякой пары вершин x и y, если R, то существует путь из x в y, проходящий только через ближайшие вершины.

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

Для описания систем вида используются особого вида таблицы, называемые матрицами достижимости и смежности. Зададим пересчет элементов M. Тогда в строке i колонки j стоит 1, если выполняется некоторое условие, между mi и mj из M, и стоит 0, если условие не выполняется. Для матрицы смежности таким условием будет ( R). Для матрицы достижимости – наличие в пути из mi в mj.

В матрицах, используемых в основной части работы, элементы (дополнительный столбец слева) и столбца (дополнительная строка вверху).

Из определения пути в следует, что если R транзитивно и в существует путь, то R.

Соответственно, если R – транзитивно, то матрицы смежности и достижимости R будут совпадать. Если R не транзитивно, то матрица достижимости совпадает с матрицой смежности транзитивного замыкания R. Введем соответствующие понятия.

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

Df.1.2.3. a) Умножение отношений. R1R2 = { / z( R1 & R2)}.

Если некоторое отношение R умножается само на себя, то говорят о возведении этого отношения в степень.

Df.1.2.3. b) Возведение отношения в степень.

1. R1=R;

2. Rn+1=RnR.

Df.1.2.4. Транзитивное замыкание. a) Tr(R) е.т.е. в существует путь из x1 в xn.

Из определений умножения и степени понятно, что наличие в пути (длиной n) равносильно тому, что Rn, а также, что если R транзитивно, то RnR для любого n.

Можно дать другое определение транзитивного замыкания.

Df.1.2.4. b) Tr(R) = i=1Ri.

Свойство транзитивности можно сформулировать через операцию Tr:

множество R транзитивно е.т.е. R = Tr(R). Если множество M бесконечно, то операция Tr(R) может оказаться трансфинитной. Если же в нет бесконечных путей (например, если M конечно и в нет циклов), то операция Tr(R) конечна и существует такое натуральное число n (длина максимального пути), что R1R2…Rn = Tr(R), причем n – меньше мощности M.

Df.1.2.5. Транзитивная редукция.

a) R – транзитивная редукцией R е.т.е. RR и Tr(R) = Tr(R).

b) R – минимальная транзитивная редукцией R е.т.е. не существует такого R, что R – транзитивная редукция R. В этом случае будем говорить, что транзитивная редукция осуществлена полностью.

Обозначим операцию получения минимальной транзитивной редукции R как Tred(R). Если в максимальный путь имеет длину n, то Tred(R) = (R\R2)\R3\…\Rn = R\(R2R3…Rn). Если же R – транзитивно, то Tred(R) = (R\R2).

Поскольку система может быть интерпретирована и как упорядоченное отношением R множество, и как граф (ориентированный), то введенные выше понятия можно применять и к бинарным отношениям, и к графам.

Df.1.2.6. Виды орграфов a) Частичный граф. Граф называется частичным графом относительно е.т.е RR.

b) Подграф. Граф называется подграфом е.т.е MM и R=R(MM).

Из определения видно, что если R – транзитивная редукция R, то – частичный граф относительно.

Одним из центральных методологических понятий работы является понятие диаграммы Хассе. Диаграмма Хассе ([Бронштейн, Семендяев 1986, 383-384; Лисовский, Марков 2004, 103, 265]) – ориентированный граф особого вида, используемый для представления конечных частично упорядоченных множеств. Диаграмма Хассе как графический объект строится следующим образом. Вершины графа соответствуют элементам изображаемого множества, дугами соединяются ближайшие объекты, находящиеся в данном отношении порядка. Направление связей идет от меньшего объекта к большему. Часто для простоты восприятия стрелки на графе опускаются и заменяются простыми линиями, связи при этом считаются направленными снизу вверх или слева направо. Если же мы обратимся к математическому представлению диаграмм Хассе как графов особого вида, то оно определяется следующим образом.

Df.1.2.6. c) Диаграмма Хассе. Граф называется диаграммой Хассе частично упорядоченного множества е.т.е R – минимальная транзитивная редукция R* и R* = R\Em (Em – диагональное отношение на M).

Если (в определении) R – отношение строгого частичного порядка, то R совпадает с R* и, соответственно, R – минимальная транзитивная редукция R. Если же R – нестрогий частичный порядок, то осуществляем полную рефлексивную редукцию (R\Em), в результате чего получаем строгий частичный порядок R*, и уже из него получаем минимальную транзитивную редукцию.

На практике, необходимо различать некоторый мыслимый объект и его описание, с которым мы работаем и посредством которого задаем этот мыслимый объект. Кроме того, удобно допускать (в речи), что если объект задан некоторым образом, то его альтернативное описание может быть неполным и даже некорректным. Тогда, построив некоторое описание теоретического объекта, необходимо показать, что это описание является корректным, адекватным. Поскольку в основной части работы строятся описания (посредством графов) некоторых частично упорядоченных множеств, то конкретизируем представление об адекватном описании применительно к таким множествам.

Df.1.2.5. Описание порядка. Пусть R – частичный порядок, заданный на M, и EM – диагональное отношение на M, тогда:

a) – описание порядка е.т.е. M=M и RR. Т.е.

является частичным (относительно ) графом 1.

b) – полное описание строгого частичного порядка е.т.е.

c) – минимальное полное описание е.т.е. – полное описание и не существует такого R*, что (R*R) и – полное описание.

Поскольку я в рамках данной работы связал понятие полного описания с операцией транзитивнго (в некоторых специально оговоренных случаях, возможно, транзитивного и рефлексивного) замыкания, то получаем, что – минимальное полное описание ЧУ множества е.т.е. граф является диаграммой Хассе ЧУ множества.

Все определения давались до сих пор из предположения, что отношение R задано экстенсионально, т.е. перечислением пар объектов, находящихся Для целей данной работы такого определения описания достаточно, но теоретически можно было бы расширить понятие описания на случай MM. Тогда случай (MM) давал бы пример неполного описания.

Теоретически, можно дать следующее определение – полное описание е.т.е. – описание и задан алгоритм (набор функций и способ их применения), позволяющий из M получить M и из R получить R. Например, – полное описание нестрогого частичного порядка е.т.е. – описание и Tr(R)EM = R. Для целей настоящей работы достаточно понятия полного (относительно транзитивного замыкания) описания.

в этом отношении. Но на практике дело обстоит сложнее. В исследуемых в диссертации случаях отношение R задается интенсионально, т.е. в виде некоторого правила, которое позволяет вычислять, находятся два объекта в отношении R или нет. Кроме того, сами свойства объектов, на основании которых определяется, находятся они в отношении R или нет, заданы также некоторыми правилами и нуждаются в вычислении. В результате, сравнение каждой пары объектов на наличие между ними отношения R – работа достаточно трудоемкая и хотелось бы ее как-то минимизировать. В частности, эта задача решается построением диаграммы Хассе для, а не полным экстенсиональным перечислением множества R. Допустим, построено некоторое описание порядка R, заданного на M. В тех случаях, которые встречаются в диссертации, для проверки минимальности достаточно (при графическом представлении) простого визуального контроля отсутствия путей единичной длины, если имеется путь большей длины. Но контроль полноты описания уже требует более сложных методов. Если бы отношение R было задано перечислением, задача сводилась бы к транзитивному замыканию R (эта процедура конечна для конечного M) и последующему сравнению Tr(R) с R (хотя некоторые из рассматриваемых в диссертации множеств уже достаточно велики, чтобы простой визуальный контроль в такой ситуации перестал быть надежен). Для этого будут использоваться матрицы отождествляться с первым элементом упорядоченной пары, а указанный сверху – со вторым элементом пары; в клетках матрицы стоят единицы, если данная пара элементов находится в отношении R, и ноль, если не находится).

Метод вычисления пар объектов, нуждающихся в проверке на принадлежность R. Пусть – описание частично упорядоченного множества.

1. Строим пустую таблицу (MM).

2. Единицами отмечаем пары, входящие в R.

3. Единицами отмечаем все пары, восстанавливаемые транзитивным замыканием R (помечаем все те и только те пары, которые входят в Tr(R)).

4. Нулями отмечаем все пары, обратные уже помеченным в таблице (исключаем по свойству асимметричности те пары, которые обратны парам из Tr(R)).

5. Нулями отмечаем все пары, входящие в диагональное отношение (исключаем по свойству антирефлексивности).

6. Оставшееся множество клеток как раз и соответствует множеству пар, нуждающихся в проверке на принадлежность R. Если R полно, то во всех оставшихся клетках в итоге будут проставлены нули.

множеству ((MM) \(Tr(R)Tr(R)-1EM))) либо пусто, либо не является подмножеством R. Или, в чуть иной форме, R((MM)\(Tr(R)Tr(R)EM))=. Зафиксирую это в следующем принципе.

Принцип 1.2.1. Пусть – описание и множества M и R не пусты, тогда – полное описание е.т.е.

R((MM)\(Tr(R)Tr(R)-1EM))=.

Основным видом теорем при построении структурных систематизаций по методике диссертанта являются теоремы об адекватности построенных описаний. Ниже приведена формулировка в общем виде такой теоремы и схема ее доказательства. Пусть задано перечислением множество объектов M, естественно упорядоченных отношением.

Схема доказательства теорем об адекватности графов. Граф является диаграммой Хассе (минимальным полным описанием) частично упорядоченного множества.

Схема доказательства.

I. является описанием (частичным графом). Напрямую показываем, что для каждой пары из R верно, что xy.

II. является полным описанием. Для этого используются матрицы смежности или принцип 1.2.1.

III. является минимальным описанием. В разбираемых нами случаях достаточно простого визуального контроля минимальности R, поэтому в доказательствах специально на этом пункте останавливаться не буду. Если бы сложность графа настолько увеличилась, что визуальный контроль минимальности стал бы не надежен, то нужно было бы применить специальные критерии минимальности.

IV. На основании II, III заключаем, что является минимальным полным описанием (диаграммой Хассе).

Конец схемы доказательства теорем об адекватности графов.

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

Построение структурного описания некоторого множества объектов может быть основанием для постановки и решения двух групп дополнительных задач.

1. Уточнение построенного структурного описания самого по себе и в его отношении ко всему классу объектов изучаемого типа. В рамках таких исследований могут решаться следующие виды задач.

а) Дополнительное изучение пар сравнимых объектов, выявление существования между ними не только изучаемого отношения, но и какихлибо более сильных отношений. Например, выявление для некоторой теории и ее расширения, что это расширение является консервативным, не существенным (дефинициально определимым) или каким-либо еще специальным случаем.

б) Дополнительное изучение несравнимых объектов, выявление фактов, что один из объектов изучаемого множества может быть представлен как результат некоторой n-местной операции над n объектами этого же множества. В первую очередь здесь интересны решеточные операции «сложения» и «умножения». В нашем исследовании это как обычные теоретико-множественные операции пересечения и объединения, так и их топологические аналоги.

в) Выявление точных нижней и верхней граней для различных подмножеств изучаемого множества.

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

д) Выяснение, какого типа структуру образует весь класс объектов данного типа. Например, известно ([Tarski 1956; Смирнов 2002, 47]), что класс всех формальных теорий, сформулированных в одном языке на базе классической логики, образует брауэрову (псевдобулеву) решетку, а его подкласс конечно аксиоматизируемых теорий – булеву решетку.

е) Выявление «критических» (минимальных и максимальных) элементов изучаемого множества и их отношения (совпадение или несовпадение) к критическим элементам класса всех объектов данного типа.

ж) Выяснение мощности класса всех объектов данного типа.

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

Пример задачи этого вида см. в [Янков 1968] и в главе 3, §5.

Исследования задач вида а)-е) можно назвать структурным анализом, а задач вида ж)-з) – количественным.

2. Ко второй группе отнесу различные вопросы, которые не относятся к построению структурных систематизаций и их дальнейшему структурному и количественному анализу, но возникают именно в силу этих исследований. Пример задачи из этой группы – построение единообразных семантик для счетного класса расширений силлогистики С4.

§3. Основные понятия теории формальных теорий 3.1. Понятие формальной теории. Предметом рассмотрения в данной работе являются формальные теории. То, что в работе анализируются теории только из одного класса, в данном случае не имеет значения: работа писалась именно в рамках теории формальных теорий, а не в рамках силлогистики. В общем случае понятие формальной теории является относительным, так как некоторое множество формул является формальной теорией не само по себе, а относительно некоторого дедуктивного следования. Можно дать несколько эквивалентных формулировок понятия формальной теории.

Df.1.3.1. Возможные определения формальной теории.

a) Множество формул X является формальной теорией относительно множества функций (операций над формулами языка L) е.т.е. X замкнуто относительно функций из (функции из являются операциями на X).

b) Множество формул X является формальной теорией относительно отношения выводимости |– е.т.е. для всякой формулы A (языка L) X |– c) Множество формул X является формальной теорией относительно оператора дедуктивного замыкания Cn е.т.е. Cn(X) = X.

В ряде случаев, формальную теорию можно задать и через отношение логического следования.

d) Множество формул X является формальной теорией относительно отношения логического следования |= е.т.е. для всякой формулы A Далее, основным буду считать первое определение формальной теории.

Функции из называются при этом правилами вывода. Далее подразумевается (если не оговорено иное), что – множества функций (правил вывода), задающих КЛВ. Исключение – несколько случаев в последней главе, где рассматриваются теории, сформулированные с использованием некоторых дополнительных (т.н. эктетических) правил вывода. Остальные определения могут быть получены из первого. Из множества формул X дедуктивно следует (при фиксированном множестве ) формула A (записываем: X |– A) е.т.е. A может быть получена как результат применения функций из (или суперпозиции таких функций) к формулам множества X. Оператор дедуктивного замыкания можно задать через отношение выводимости: Cn(X)={A / X|–A}. Если задана теория T, то записи (AT), (T|–A) и (|–T A) считаем синонимичными. Если выводимость явно не связана с конкретной теорией, то понимаем ее как классическую выводимость (в рамках КЛВ).

Вообще, множество теорем любого исчисления задает некоторую формальную теорию. Таким образом, формальная теория – то общее, что есть у дедуктивно эквивалентных исчислений; каждая формальная теория является инвариантом бесконечного числа дедуктивно эквивалентных исчислений. Это позволяет говорить об исчислениях как об одном из способов определения формальных теорий. Все исследуемые в работе теории описывались в литературе именно как исчисления. Поэтому, говоря об аксиоматике и правилах вывода формальной теории, я имею в виду некоторое исчисление, лишь задающее данную формальную теорию.

Содержательно и технически важным моментом является то, что формальная теория – это множество формул некоторого формального языка. Поэтому, с одной стороны, мы рассматриваем множества и обычные теоретико-множественные отношения между ними (равернство, строгое и нестрогое включение), а с другой стороны, учитывая содержательную интерпретацию, говорим о «теориях» и их соотношении «по дедуктивной силе».

Во-вторых, существенная связь формальных теорий с тем или иным языком определяет и существенные недостатки понятия формальной теории. Поскольку формулировка одной и той же теории в разных языках дает нам разные формальные теории, то результат сравнения формальных теорий зависит от того, как мы произведем сравнение формальных языков этих теорий (эта тема специально обсуждается в статье, помещенной в приложение). Тем не менее, понятие формальной теории является одним из наиболее эффективных инструментов современных металогических исследований.

3.2. Свойства формальных теорий. Ниже приводятся некоторые свойства формальных теорий, упоминаемые в дальнейших рассмотрениях.

Введем обозначения для ряда семиотических объектов, связанных с указывается ее язык, а при задании языка – его алфавит и класс термов (ППТ); язык отождествляется с классом формул (ППФ)).

Df.1.3.2.

a) A(T) – алфавит теории T.

b) T(T) – класс ППТ теории T.

c) L(T) – язык (класс ППФ) теории T.

Вообще говоря, мы не можем разделить некоторые устойчивые сочетания значимых и технических (синкатегорематических) знаков и не можем в общем случае «породить» алфавит по заданному множеству формул (языку или формальной теории). Эта сложность преодолевается двумя путями. Во-первых, можно постулировать, что в рамках наших рассмотрений скобки являются только самостоятельными буквами, т.е. не входят в качестве графических элементов в состав других букв (рассматриваемых информации и без дополнительных постулатов достаточно для однозначной идентификации алфавита из заданного в главе II множества алфавитов.

Df.1.3.3. Синтаксические свойства теорий.

a) Теория T синтаксически противоречива е.т.е. T=L(T).

противоречива)) 1.

Для доказательства синтаксической полноты будем использовать следующий критерий.

Критерий 1.3.1. Теория синтаксически полна е.т.е. в ней для любой формулы A (языка этой теории) доказуема либо сама формула A, либо ¬A, но не доказуемы одновременно A и ¬A.

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

Утверждение 1.3.1. Пусть T – теория, построенная на базе классической логики высказываний в языке без кванторов, и для всякой элементарной (атомарной) формулы языка этой теории верно, что либо она сама, либо ее отрицание доказуемы в T. Тогда верно, что A L(T) (|– Доказательство.

1. Если A – атомарная формула, то утверждение леммы верно по условию.

2. Допустим, что утверждение леммы верно для B и C.

3. A – формула вида ¬B:

1. |–T B |–T ¬B. – По индуктивному предположению.

4. A – формула вида BC:

1. (|–T B |–T ¬B) & (|–T C |–T ¬C). – По индуктивному T+A – сокращение для Cn(T{A}).

предположению.

2. (|–T B & |–T C) (|–T ¬B & |–T C) (|–T B & |–T ¬C) (|–T ¬B & |–T ¬C). – Из 4.1 по КЛВ.

3. (|–T B & |–T C) (|–T ¬B |–T ¬C). – Из 4.2 по КЛВ.

4. (|–T B & |–T C). – Предположение.

5. |–T BC. – Из 4.4.

6. (|–T B & |–T C) |–T BC. – Из 4.4–4.5; шаги 4.4–4.5 исключены.

7. (|–T ¬B |–T ¬C). – Предположение.

8. |–T (¬B ¬C). – Из 4.7.

9. |–T ¬(BC). – Из 4.8.

10. (|–T ¬B |–T ¬C) |–T ¬(BC). – Из 4.7–4.9; шаги 4.7–4. исключены.

11. |–T BC |–T ¬(BC) – Из 4.3, 4.6, 4.10 по простой конструктивной дилемме.

5. A – формула вида BC:

1. (|–T B |–T ¬B) & (|–T C |–T ¬C). – По индуктивному предположению.

2. (|–T B & |–T C) (|–T ¬B & |–T C) (|–T B & |–T ¬C) (|–T ¬B & |–T ¬C). – Из 5.1 по КЛВ.

3. (|–T B |–T C) (|–T ¬B & |–T ¬C). – Из 5.2 по законам КЛВ.

4. (|–T B |–T C). – Предположение.

5. |–T BC. – Из 5.4.

6. (|–T B |–T C) |–T BC. – Из 5.4–5.5; шаги 5.4–5.5 исключены.

7. (|–T ¬B & |–T ¬C). – Предположение.

8. |–T (¬B ¬C). – Из 5.7.

9. |–T ¬(BC). – Из 5.8.

10. (|–T ¬B & |–T ¬C) |–T ¬(BC). – Из 5.7–5.9; шаги 5.7–5. исключены.

11. |–T BC |–T ¬(BC). – Из 5.3, 5.6, 5.10 по простой конструктивной дилемме.

эквивалентность (BC) и (¬BC).

1. Если для формул D1 и D2 утверждение леммы верно, то оно верно и для (D1D2). – В случай 5.

2. Если утверждение леммы верно для B, то оно верно для ¬B. – Случай 3.

3. Утверждение леммы верно для B и для C. – Индуктивное предположение (случай 2).

4. Утверждение леммы верно для формул вида (¬BC). – Из 1–3.

5. Утверждение леммы верно для формул вида (BC). – Из 4, на основании КЛВ.

7. Случай, что A – формула вида (BC), доказывается аналогично предыдущему. При этом используется эквивалентность в КЛВ выражений вида (BC) и вида (BC)(CB).

8. Индукцией по пунктам определения ППФ показано, что |– A |– ¬A для любой ППФ языка теории T.

Утверждение 1.3.2. Пусть T – теория, построенная на базе классической логики высказываний в языке без кванторов. В качестве используются некоторые элементарные формулы языка этой теории, либо отрицания таких формул (но не формулы и их отрицания непротиворечива.

Доказательство. Допустим что предположение ложно и в T доказуема некоторая формула C и ее отрицание ¬C. Это значит, что в рамках КЛВ можно дать такую интерпретацию элементарным формулам языка теории T, при которой формула C одновременно будет истинной и ложной.

Следовательно, КЛВ является противоречивой. Из ложности вывода непротиворечивой.

Утверждение 1.3.3. Пусть T – теория, построенная на базе классической логики высказываний в языке без кванторов. В качестве отрицания таких формул, причем для всякой элементарной формулы языка этой теории верно, что либо она сама, либо ее отрицание является послулатом, но не формула и ее отрицание одновременно. Тогда верно, что теория T – синтаксически полна.

Доказательство. Утверждение следует из утверждений 1.3.1 и 1.3.2 по критерию 1.3.1.

Теоретическое значение имеют также еще два свойства теорий.

Df.1.3.4. Теория T конечно аксиоматизируема е.т.е. существует такое конечное множество X, что Cn(X)=T.

Df.1.3.5. Теория T разрешима е.т.е. существует эффективная процедура, позволяющая для любой формулы A за конечное число действий определить, имеет место (AT) или имеет место (AT).

3.3.

топологического замыкания имеется следующая теорема.

Теорема 1.3.1 (Биркгофа-Тарского). Если X – некоторое множество и на P(X) задан оператор замыкания Cn, то множество является полной решеткой по отношению включения, где XCn – множество всех замкнутых относительно Cn подмножеств X. [Васюков 1995, 280].

При этом, ноль решетки совпадает с, единица с самим множеством X, решеточная операция «умножения» совпадает с теоретико-множественным пересечением, операция «сложения» определяется следующим образом.

Df.1.3.6. Объединение замкнутых множеств. X1+X2 =Df Cn(X1X2).

Пусть L – некоторый формальный язык (класс всех правильно построенных формул L), на P(L) задана операция замыкания Cn, Theo(L, Cn) – класс всех замкнутых относительно Cn подмножеств L. Операция дополнения определяется следующим образом.

Df.1.3.7. Операция дополнения к формальным теориям. T* =Df AT Cn(¬A).

Класс Theo(L, Cn) относительно, L, операций, + и * образует брауэрову (псевдобулеву) алгебру (и решетку) (см. [Tarski 1956; Смирнов 2002, 46-47]). Пусть FTheo(L, Cn) класс всех конечно аксиоматизируемых теорий из Theo(L, Cn), т.е. T FTheo(L, Cn) (ГL)(Г – конечно & Cn(Г) = T). Все указанные результаты, относящиеся к Theo(L, Cn), имеют место и для FTheo(L, Cn), а некоторые из них можно усилить. Класс FTheo(L, Cn) конечно аксиоматизируемых теорий образует булеву алгебру (и решетку). Это демонстрируется сведением алгебры над теориями к булевой алгебре над формулами [Смирнов 2002; 47].

3.4. Отношения между формальными теориями. Основное отношение между формальными теориями – отношение «быть подмножеством», понимаемое содержательно как соотношение «по дедуктивной силе». Это основной тип отношений, рассматриваемый в данной работе.

Df.1.3.8. Отношения по множеству теорем.

a) Теория T1 называется подтеорией T2, а T2 – расширением T1 е.т.е.

(T1T2).

b) T2 – собственное расширение T1 е.т.е. (T1T2) и L(T1)=L(T2).

c) T2 – консервативное расширение T1, а T1 – точный фрагмент теории T2 в языке L(T1) е.т.е. (T1T2), L(T1)L(T2) и T1=(T2L(T1)). При этом L(T1) буду назувать подъязыком L(T2).

d) T1 и T2 – функционально эквивалентны относительно языка L (LL(T1) и LL(T2)) е.т.е. для всякой формулы A языка L верно, что |–T A |–T2 A, т.е. (T1L)=(T2L). Иначе, е.т.е. существует теория T3 в языке L такая, что T1 и T2 являются консервативными расширениями T3.

e) T1 функционально слабее T2 относительно языка L (LL(T1) и LL(T2)) е.т.е. для всякой формулы A языка L верно, что |–T1 A |–T A, но не наоборот, т.е. (T1L)(T2L).

f) T2 – языковое расширение T1 е.т.е. L(T1)L(T2) и T2=Cn(T1), где T1=Cn(T1) и Cn – расширение Cn на L(T2).

g) T2 – дефинициальное расширение T1 е.т.е. существует теория T3 – языковое расширение T1 (на язык L(T2)) и множество D определений знаков A(T2)\A(T1) через знаки A(T1) такие, что T2=Cn(T3+D).

h) Теории T1 и T2 независимы е.т.е. (T1T2)=.

i) Теории T1 и T2 (в одном языке, при некотором заданном Cn) совместимы е.т.е. Cn(T1T2) – синтаксически непротиворечивая теория.

j) T1 и T2 – функционально несовместимы относительно языка L (LL(T1) и LL(T2)) е.т.е. существует формула A языка L такая, что |–T A и |–T2 ¬A, т.е. теории (T1L) и (T2L) не совместимы.

Следующая группа отношений между формальными теориями связана с их выразительными возможностями и определимостью выражений одной теории через выражения другой.

Df.1.3.9. Отношения по выразительным возможностям.

a) Теория T1 дефинициально выразима (в [Смирнов 2001c, 390] – дефинициально вложима) в T2 е.т.е. существует дефинициальное расширение T2, являющееся консервативным расширением T1.

b) Теории T1 и T2 дефинициально эквивалентны е.т.е. T1 дефинициально выразима в T2 и T2 дефинициально выразима в T1. (Т.е. существует теория, являющаяся минимальным консервативным дефинициальным расширением T1 и T2.) Особый случай дефинициальной эквивалентности – когда одна теории является дефинициальным расширением другой. Понятно, что в любой теории дефинициально выразима она сама и любой ее точный фрагмент в некотором подъязыке. Поэтому обе теории дефинициально выразимы друг в друге и, следовательно, дефинициально эквивалентны.

Еще одна группа отношений между формальными теориями связана с наличием различных функций из языка одной теории в язык другой.

Df.1.3.10.

a) Переводом языка L1 в язык L2 буду называть функцию, сопоставляющую каждой формуле языка L1 некоторую формулу языка L2.

b) Индуктивным буду называть такой перевод из L1 в L2, который сохраняет структуру выражений из следуя соответствующим индуктивным определениям этих выражений. В рамках данной работы рассматриваются только такие индуктивные переводы, для которых дистрибутивными относительно пропозициональных связок):

(AB)=(A)(B); (AB)=(A)(B); (¬A)=¬(A).

(AB)=(A)(B); (AB)=(A)(B);

Df.1.3.11. Соотношения по наличию функций.

a) Функция из L(T1) в L(T2) погружает теорию T1 в T2 е.т.е. для всякой формулы A языка L(T1) верно, что |–T1 A |–T2 (A).

b) Теории T1 и T2 взаимопогружаемы е.т.е. T1 погружается в T2 и T погружается в T1.

В [Смирнов 2001c, 393] предложено усилить понятие погружаемости и введено понятие рекурсивной вложимости теорий друг в друга. «Для стандартных первопорядковых теорий всегда можно найти теорию, сформулированную в терминах одного бинарного отношения, в которую она погружается. Однако это не так для отношения рекурсивной (дефинициальной) вложимости» [Смирнов 2001c, 393].

Df.1.3.11.

c) T1 рекурсивно вложима в T2 е.т.е. существуют функции и такие, что 3. |–T1 A((A)).

d) T1 и T2 рекурсивно эквивалентны е.т.е. T1 рекурсивно вложима в T2 и T рекурсивно вложима в T1.

Утверждение 1.3.4 (о равенстве двух теорий). Если L(T1)=L(T3) и погружает T1 и T3 в T2, то T1=T3.

Доказательство.

1. Для всякой формулы A языка L(T1) верно, что |–T1 A |–T2 (A) и |–T3 A |– (A). – По определению погружающей операции и условию L(T1)=L(T3).

2. Для всякой формулы A языка L(T1) верно |–T1 A |–T3 A. – Из 1 по определению эквиваленции.

3. T1=T3. – Из 2 и условия.

Аналогичный вывод можно провести и опираясь адекватные семантики, (непротиворечивость и полнота) теории T относительно семантики M означает, общезначимых в M (обозначим T=M).

Утверждение 1.3.5 (о равенстве двух теорий). Если T1 и T2 сформулированы в одном языке и имеют одну и ту же адекватную семантику с множеством общезначимых формул M, то T1=T2.

Доказательство. Это очевидно, поскольку, по условию, T1=M и T2=M, то T1=T2.

Из утверждений 1.3.4 и 1.3.5 можно получить более сложное утверждение.

Утверждение 1.3.6. Если теория T1 сформулирована в языке L1, теория T2 – в языке L2, L1 L2, то если (1) функция, погружающая T2 в T3, погружает T1 в T или (2) функция, приписывающая значения формулам в адекватной T семантике, дает адекватную семантику для T1, то T1=T2L1.

Доказательство. Поскольку (T2L1) – подтеория T2 в языке L1, то ограничивая рассмотрение погружающих функций или семантик только формулами языка L1, получаем случай теоремы 1.3.4 или 1.3.5.

Df.1.3.12. Пусть L(T1)L(T2) и – индуктивная функция из L(T2) в L(T1) такая, что для всякой формулы A языка L(T1) верно, что (A)=A.

a) T2 рекурсивно определяется в T1 е.т.е. |–T2 A(A).

b) T2 – несущественное расширение T1 е.т.е. T2 консервативное расширение T и T2 рекурсивно определяется в T1.

c) T2 – погружаемое расширение T1 е.т.е. |–T2 A |–T1 (A).

устранимости по Клини [Смирнов 2001c, 391]. Иначе несущественность расширения и устранимость по Клини можно определить так: T2 рекурсивно определяется в T1 и |–T2 A |–T1 (A).

Df.3.1.13. Относительная непротиворечивость.

a) Теория T1 непротиворечива относительно T2 е.т.е. из непротиворечивости T2 следует непротиворечивость T1.

b) Теории T1 и T2 равнонепротиворечивы е.т.е. T1 непротиворечива относительно T2 и T2 непротиворечива относительно T1.

Можно сформулировать следующие критерии относительной непротиворечивости.

Утверждение 1.3.6. Теории T1 и T2 равнонепротиворечивы, если T погружается в T2. (Для классического замыкания и индуктивного перевода.) Доказательство.

1) T1 погружается в T2 функцией. – Предположение.

2) Для всякой формулы A языка L(T1) верно, что |–T1 A |–T2 (A). – Из 1 по определению погружающей операции.

3) T1 синтаксически противоречива. – Предположение.

4) Для всякой формулы A языка L(T1) верно, что |–T2 (A) и |–T2 (¬A). – Из 2 и 3 по определению синтаксической противоречивости.

5) (¬A)=¬(A). – По условию индуктивности.

6) |–T2 (A) и |–T2 ¬(A). – Из 4 и 5.

7) T2 синтаксически противоречива. – Из 6 по определению синтаксической противоречивости.

8) Если T1 противоречива, то T2 противоречива. – Из 3–7 (шаги 3–7 исключены из дальнейшего рассмотрения).

9) T2 синтаксически противоречива. – Предположение.

10) Для всякой формулы A языка L(T1) верно, что |–T2 (A) и |–T2 ¬(A). – Из 2 и 9 по определению синтаксической противоречивости.

11) ¬(A)=(¬A). – По условию индуктивности.

12) |–T2 (A) и |–T2 (¬A). – Из 10 и 11.

13) |–T1 A и |–T1 ¬A. – Из 12 и 2.

14) T1 синтаксически противоречива. – Из 13 по определению синтаксической противоречивости.

15) Если T2 противоречива, то T1 противоречива. – Из 9–14 (шаги 9– исключены из дальнейшего рассмотрения).

16) Теория T1 противоречива е.т.е. противоречива T2. – Из 8 и 15.

17) T1 и T2 равнонепротиворечивы. – Из 16.

18) Если T1 погружается в T2, то T1 и T2 равнонепротиворечивы. – Из 1–17 (шаги 1–17 исключены из дальнейшего рассмотрения).

§4. Сравнение формальных теорий В наше время в литературе непосредственно описаны сотни формальных теорий, известны их бесконечные (и даже континуальные) классы. Поэтому все более актуальным становится вопрос о систематизации уже открытых теорий.

Использование языка графов дает возможность наглядного представления результатов подобных компаративных исследований.

Если в сравнительном анализе силлогистик автор существенным образом опирался на работы В.И. Маркина ([Маркин 1991] и др.), то идеей графического представления соотношений теорий автор обязан работам А.С. Карпенко [Карпенко 1993; 1995; 1997a-b; 1999a-b; 2001]. Причем, именно под влиянием Карпенко сформировалась установка автора, что получение (и обоснование) графа теорий может быть целью и основным результатом подобного рода сравнительных исследований.

Помимо графов из работ Карпенко, к началу собственных исследований (2000 г.) автору были известны еще несколько графов, представляющих соотношение теорий по дедуктивной силе. Во-первых, это граф соотношения пяти нормальных модальных систем K, T, Br, S4, S5 (поскольку они хорошо известны и никак не связаны с дальнейшим анализом, я не привожу их описаний). В 2005 г. коллеги указали автору на статью Томаса Шнайдера [Schneider 2005] в Интернете, в которой строился граф (соотношения по дедуктивной силе) 25 нормальных модальных систем.

Во-вторых, автору был известен граф, представляющий соотношения силлогистик С1, С2, С3, С4, приводимый В.А. Смирновым в [Смирнов 1983b, 4;

Смирнов 2002, 155] (описание этих теорий приводится в таблица 3.1.1).

Недостаток некоторых подобных систематизаций состоит в следующем. Вопервых, систематизируемые теории a priori считаются дедуктивно не эквивалентными. Их не совпадение может быть и кажется очевидным, но в рамках подобного исследования тем не менее нуждается в явном обосновании.

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

На взгляд диссертанта, строго проведенная методика анализа должна показывать, что построенный граф является диаграммой Хассе исследуемого частично упорядоченного множества формальных теорий. В ведении (раздел «Методологические основания») была описана сумма фактов, необходимых для доказательства этого. Именно так строится доказательства адекватности графов алфавитов, классов термов и классов формул в следующей главе.

Доказательство адекватности графов теорий в большинстве случаев выстраивается мной иначе. Граф строится как визуализация (диаграмма Хассе) уже описанного матрицей смежности частично упорядоченного множества теорий. Единственная не механическая работа при этом – осуществляемый визуально контроль минимальности графа (отсутствия единичных путей между вершинами, которые уже соединены путями большей длинны). Матрица смежности рассматриваемого множества теорий строится чисто механически на основе специальной таблицы выводимости для этого множества.

Таблица выводимости имеет следующий вид. Все теории формулируются со схемами аксиом (другой вариант – с аксиомами) и одним и тем же множеством правил вывода. Вверху таблицы указываются теории, слева – формулы, используемые нами для аксиоматического определения теорий. Знак “+” в таблице означает, что формула данной строки используется нами в качестве аксиомы для определения указанной в столбце теории; знак “|–” означает, что формула не используется нами в качестве аксиомы, но доказуема в данной теории; “–” – что формула не доказуема в теории. Рассматриваемые теории – это множества формул указанного формального языка, включающие формулы помеченные в таблице плюсом и замкнутые относительно указанных правил вывода. Поскольку все рассматриваемые в последующих главах силлогистические теории строятся на базе классической логики высказываний, то их формулировки в виде исчислений включают (помимо указанных в таблицах силлогистических схем аксиом) схемы аксиом или правила вывода классической логики высказываний, правило modus ponens. Сами же теории как множества формул замкнуты относительно КЛВ и операции подстановки термов.

Основное доказательство при таком подходе к построению графа теорий приходится на обоснование адекватности построенной таблицы выводимости.

Одна теория является подтеорией другой е.т.е. все ее аксиомы являются теоремами (или аксиомами) этой второй теории. Если хотя бы одна теорема теории не доказуема во второй теории, то первая теория не является подтеорией второй. При таком сравнении теорий необходимо уметь показывать не только доказуемость формул в теории, но и недоказуемость формул. Показать доказуемость формулы в теории можно непосредственно построением доказательства данной формулы в исчислении, задающем данную теорию. Но показать невыводимость формулы гораздо сложней и необходимо прибегать к различным дополнительным средствам.

1) Если для данной теории известны разрешающие процедуры, то можно использовать их.

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

3) Может использоваться погружение данной теории в другую теорию, для которой имеет место условие 1) или 2).

4) Если доказано, что данная теория может быть получена операцией пересечения из других формальных теорий, для которых выполняется одно из условий 1)–3), то можно свести проверку формулы на недоказуемость (доказуемость) в данной теории к проверке ее на недоказуемость (доказуемость) в теориях, из которых она получена.

5) Если не применимы случаи 1)–4), но есть уверенность, что формула не доказуема в данной теории, то можно к этой теории присоединить отрицание данной формулы и попытаться показать, что получившаяся теория синтаксически непротиворечива.

По возможности, в качестве способа проверки формулы на доказуемость буду использовать проверку ее на общезначимость в адекватной семантике. Но в отдельных случаях придется пользоваться и другими из указанных способов.

В частности, понадобится следующее утверждение.

Утверждение 1.4.1. Если теория T1 погружается в T2 отображением и для T2 построена адекватная семантика MT2, то для всякой формулы A языка L(T1) верно, что T1|–A MT2|=(A).

Доказательство.

1. T1|–A T2|–(A). – Условие погружаемости T1 в T2.

2. T2|–B MT2|=B. – Условие адекватности семантики для T2.

3. T2|–A MT2|=(A). – Результат подстановки в 2.

4. T1|–A MT2|=(A). – Из 1 и 3.

5. (AL(T1))(T1|–A MT2|=(A)). – из 4.

Принцип 1.4.1. На основании утверждения 1.4.1, для теории T1 можно построить адекватную семантику, построив функцию, означивающую формулы теории T1, как суперпозицию погружающей операции и функции, означивающей формулы теории T2, т.е. A ( |A|MT1=1 |(A)|MT2=1 ).