Сразу начну с гипотезы, положенной в основу данной статьи: вся классическая логика основана на множествах, точнее, на алгебре множеств. Должен сказать, что в современной логике и математике эта гипотеза считается ошибочной, так как еще на рубеже XIX и XX столетий сложилось убеждение (точнее, заблуждение), что понятие «множество» противоречиво. Мне представляется, что настала пора избавляться от этого и некоторых других заблуждений, связанных с логикой.

Вступление

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

Чтобы выполнить эти задачи, пришлось взять за основу не абстрактный и труднопонимаемый вариант теории множеств (Цермело – Френкеля, Неймана – Бернайса – Геделя, Тарского – Гротендика и др.), а «примитивный» вариант, который был предложен в книге, вышедшей впервые в 1941 году и до сих пор еще не утратившей своей популярности. Речь идет о книге Р. Куранта и Г. Роббинса «Что такое математика?». А «примитивный» вариант – это математическая система, которая в этой книге названа «Алгеброй множеств» (см. стр. 134 - 142 цитируемого издания). Система достаточно проста – ее легко могут усвоить школьники младших классов.

В Части 1 показано обоснование законов алгебры множеств без аксиом на основе определений операций и отношений.

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

В Части 3 будет показано, что при подключении к алгебре множеств некоторых малоизвестных свойств декартова произведения множеств мы получим все законы и методы исчисления высказываний, а также значительную часть законов и методов исчисления предикатов. Для «примитивного» варианта, согласитесь, это немало.

А чтобы наслаждаться сложностями и парадоксами, без которых не мыслят математику многие профессионалы (актуальная бесконечность, гипотеза континуума, парадокс Банаха – Тарского о равновеликом удвоении шара и др.), достаточно продолжить эту «примитивную» теорию, добавив в нее соответствующие аксиомы теории множеств.

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

Что понимается под алгеброй множеств

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

Такое «однобокое» и невнятное определение соответствует определению «алгебры множеств» в Математической энциклопедии, выпущенной в 1977 – 1985 годах издательством «Советская энциклопедия». Это определение остается без изменения и в современной русской Википедии (см. вариант статьи «Алгебра множеств» до даты публикации этой моей статьи).

Мне кажется, что такая «однобокость» обусловлена тем, что термин «алгебра» с точки зрения разработанной академиком А.И. Мальцевым теории алгебраических систем подразумевает систему объектов, в которой определены только операции. Что касается отношений, то с точки зрения этой теории в алгебре их не должно быть. Курант и Роббинс в своей книге не учли этот «запрет». Это можно объяснить тем, что книга «Что такое математика?», в которой определена алгебра множеств, была впервые издана в 1941 году, когда теория алгебраических систем еще не была известна!

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

Иногда алгебру множеств отождествляют с «наивной теорией множеств», ставшей широко известной после публикации в 1960 году книги Пола Халмоша». Однако эта отождествление не вполне корректно. В своей книге Халмош излагает понятным для студентов языком один из вариантов аксиоматической теории множеств. А в книге «Что такое математика?» алгебра множеств – это математическая система с определенными операциями и отношениями, законы которой, как считают авторы книги, можно обосновать без аксиом.

Алгебра множеств как альтернатива аксиоматическим системам

Современную математику невозможно представить без термина «множество» – он прочно укрепился практически во всех ее основных разделах, включая математическую логику. Есть веские основания полагать, что законы алгебры множеств можно использовать в качестве математической модели семантики.

На рубеже XIX и XX столетий были попытки положить «множество» в основу всей математики, но не получилось, так как примерно в то же время были обнаружены многочисленные парадоксы, многие из которых тесно связаны с понятием «множество». Чтобы оберечься от этого кошмара, была придумана и безоговорочно принята в качестве оснований логики и математики Теория формальных систем, а также ее детище – Язык первого порядка, который лежит в основе современной математической логики.

Результатом этих событий стало то, что слово «множество» в основаниях современной логики оказалось под запретом. Хотя на самом деле под запретом оказалось не понятие «множество», а термин «множество», поскольку в многочисленных современных учебниках по логике используются для обоснований диаграммы Венна, модельные схемы, семантические схемы, круги Эйлера и т.д., которые, по сути, являются ничем иным, как наглядными отображениями соотношений между множествами.

В математической логике помимо аксиом предусмотрены правила вывода, причем и те, и другие никак не обоснованы. Мы просто должны поверить, что так надо. А что тогда нам мешает изменить эти аксиомы и правила вывода и получить бесчисленные варианты неклассических логик? В принципе так и получилось в современной науке, в результате чего «строгая» наука пришла к тому, что теперь у нас нет четких критериев выбора правильной логики для анализа рассуждений и обоснований.

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

Основные понятия и законы алгебры множеств

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

• Множество, элемент. Совокупность объектов, объединенных общим свойством или несколькими свойствами, будем называть множествами, а сами объекты – элементами. Если известно, что множество состоит из элементов , и и только из них, то используется запись . Порядок элементов у множеств несущественен. Например, тоже правильно.

Отношения в алгебре множеств

• Отношение принадлежности. Отношение между элементом и множеством называется отношением принадлежности и обозначается символом (). Запись означает, что элемент принадлежит множеству . В то же время запись означает, что элемент не принадлежит множеству .

• Отношение включения множеств. Пусть даны множества и . Тогда (понимается как « включено в или равно ему»), если в множестве не существует элементов, не принадлежащих множеству .

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

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

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

Основным (системообразущим) в алгебре множеств является отношение включения. Его «самоприменимость» () является одним из законов алгебры множеств и не влечет парадоксов.

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

Операции алгебры множеств

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

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

Например, если , а , то .

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

Например, если , и , то ,
.

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

Например, если , , то .

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

Законы алгебры множеств

В книге «Что такое математика?» перечислено 26 законов алгебры множеств. Все они приведены ниже. Пусть , и – произвольные множества, – универсум рассуждения и – пустое множество.
1 )
2 ) Если и то
3 ) Если и то
4 ) 5)
6 ) 7)
8) 9)
10) 11)
12) 13)
14) 15)
16) 17)
18) эквивалентно и эквивалентно
19) 20)
21) 22)
23)
24) эквивалентно
25) 26)

В литературе закон 3 называют законом транзитивности включения множеств, законы 12 и 13 – законами дистрибутивности, закон 23 – законом инволюции дополнения, закон 24 – законом контрапозиции, а законы 25 и 26 – законами де Моргана. В логике закону 19 соответствует закон исключенного третьего, а закону 20 – закон непротиворечия.

Обоснование законов алгебры множеств без аксиом

В книге Куранта и Роббинса говорится о том, что проверить справедливость этих законов можно с помощью «самой элементарной логики». Под этим понимается перебор вариантов соотношений между множествами. Эти соотношения можно отобразить с помощью диаграмм Венна. Рассмотрим этот способ на примере вывода некоторых законов алгебры множеств. На рисунке ниже показана диаграмма Венна, с помощью которой можно выразить все возможные соотношения между двумя множествами и с учетом их общего универсума .

Выделим на рисунке области , , и , не имеющие внутренних границ. Ясно, что эти области не пересекаются друг с другом, а их объединение равно . Тем самым они образуют разбиение универсума. Это означает, что полученные в результате разбиения множества никак не связаны между собой. К тому же с их помощью можно единственным способом представить множества , и , поэтому их можно использовать в качестве элементов этих множеств. Тогда для доказательства законов алгебры множеств можно взять за основу следующие исходные данные: ; ; .

Здесь можно избежать сомнительного использования множеств в качестве элементов. Для этого достаточно представить, что , , и – это просто обозначения соответствующих множеств (кавычки в обозначениях подразумеваются). Тогда все последующие операции с ними в качестве элементов будут уже не с множествами, а с обозначениями.

Для этих исходных данных докажем один из законов де Моргана: . Для этого в соответствии с определениями операций последовательно выполним следующие вычисления.

1. ;

2. ;

3. ;

4. ;

5. ;

6. Сравним 2 и 5. В результате получим: .

Вычисления подтверждают справедливость закона де Моргана. Однако этого недостаточно, так как необходимо проверить этот закон для всех возможных вариантов соотношений между множествами и . Эти варианты можно получить, если последовательно исключать элементы , , и и их сочетания из универсума . Нетрудно убедиться, что таких вариантов 16. Для ясности перечислим их.

1. ; ; .

2. ; ; .

3. ; ; .

4. ; ; .

5. ; ; .

6. ; ; .

7. ; ; .

8. ; ; .

9. ; ; .

10. ; ; .

11. ; ; .

12. ; ; .

13. ; ; .

14. ; ; .

15. ; ; .

16. ; ; .

Например, докажем справедливость закона де Моргана для варианта 8:
; ; .

1. ;

2. ;

3. ;

4. ;

5. ;

6. Сравним 2 и 5. В результате получим: .

Рассмотрим некоторые варианты доказательства закона контрапозиции (номер 24). В этом законе соотношение является обязательным условием, поэтому необходимо рассматривать только те варианты соотношений между множествами и , в которых соблюдается это соотношение. К ним относятся следующие 8 вариантов
5) ; ; .
9) ; ; .
10) ; ; .
11) ; ; .
13) ; ; .
14) ; ; .
15) ; ; .
16) ; ; .

Докажем этот закон для варианта 5.

1. Убедимся, что : ;

2. ;

3. ;

4. проверка показывает, что .

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

Разумеется, предложенный метод доказательства, в котором используется «тупой» перебор вариантов, многим может показаться весьма трудоемким. Например, чтобы доказать законы дистрибутивности, в которых участвуют 3 множества, потребуется рассмотреть 256 вариантов в каждом случае. Можно сократить число вариантов, если для доказательства этого закона воспользоваться другими, менее трудоемкими при обосновании, законами алгебры множеств. Идею такого доказательства законов дистрибутивности можно найти в книге Роберта Р. Столла «Множества. Логика. Аксиоматические теории» (стр. 29).

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

Дизайн баннера выполнен Анной Горской