Сразу начну с гипотезы, положенной в основу данной статьи: вся классическая логика основана на множествах, точнее, на алгебре множеств. Должен сказать, что в современной логике и математике эта гипотеза считается ошибочной, так как еще на рубеже 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 – закон непротиворечия.
Обоснование законов алгебры множеств без аксиом
В книге Куранта и Роббинса говорится о том, что проверить справедливость этих законов можно с помощью «самой элементарной логики». Под этим понимается перебор вариантов соотношений между множествами. Эти соотношения можно отобразить с помощью диаграмм Венна. Рассмотрим этот способ на примере вывода некоторых законов алгебры множеств. На рисунке ниже показана диаграмма Венна, с помощью которой можно выразить все возможные соотношения между двумя множествами и
с учетом их общего универсума
.
![Диаграмма Венна для двух множеств](https://habrastorage.org/webt/ti/ib/nb/tiibnb27rb_6aac0vtbkjcrteua.jpeg)
Выделим на рисунке области ,
,
и
, не имеющие внутренних границ. Ясно, что эти области не пересекаются друг с другом, а их объединение равно
. Тем самым они образуют разбиение универсума. Это означает, что полученные в результате разбиения множества никак не связаны между собой. К тому же с их помощью можно единственным способом представить множества
,
и
, поэтому их можно использовать в качестве элементов этих множеств. Тогда для доказательства законов алгебры множеств можно взять за основу следующие исходные данные:
;
;
.
Здесь можно избежать сомнительного использования множеств в качестве элементов. Для этого достаточно представить, что ,
,
и
– это просто обозначения соответствующих множеств (кавычки в обозначениях подразумеваются). Тогда все последующие операции с ними в качестве элементов будут уже не с множествами, а с обозначениями.
Для этих исходных данных докажем один из законов де Моргана: . Для этого в соответствии с определениями операций последовательно выполним следующие вычисления.
;
;
;
;
;
Сравним 2 и 5. В результате получим:
.
Вычисления подтверждают справедливость закона де Моргана. Однако этого недостаточно, так как необходимо проверить этот закон для всех возможных вариантов соотношений между множествами и
. Эти варианты можно получить, если последовательно исключать элементы
,
,
и
и их сочетания из универсума
. Нетрудно убедиться, что таких вариантов 16. Для ясности перечислим их.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
;
;
.
Например, докажем справедливость закона де Моргана для варианта 8:
;
;
.
;
;
;
;
;
Сравним 2 и 5. В результате получим:
.
Рассмотрим некоторые варианты доказательства закона контрапозиции (номер 24). В этом законе соотношение является обязательным условием, поэтому необходимо рассматривать только те варианты соотношений между множествами
и
, в которых соблюдается это соотношение. К ним относятся следующие 8 вариантов
5)
;
;
.
9)
;
;
.
10)
;
;
.
11)
;
;
.
13)
;
;
.
14)
;
;
.
15)
;
;
.
16)
;
;
.
Докажем этот закон для варианта 5.
Убедимся, что
:
;
;
;
проверка показывает, что
.
Нетрудно убедиться, что закон контрапозиции подтверждается и для всех других перечисленных вариантов.
Разумеется, предложенный метод доказательства, в котором используется «тупой» перебор вариантов, многим может показаться весьма трудоемким. Например, чтобы доказать законы дистрибутивности, в которых участвуют 3 множества, потребуется рассмотреть 256 вариантов в каждом случае. Можно сократить число вариантов, если для доказательства этого закона воспользоваться другими, менее трудоемкими при обосновании, законами алгебры множеств. Идею такого доказательства законов дистрибутивности можно найти в книге Роберта Р. Столла «Множества. Логика. Аксиоматические теории» (стр. 29).
Однако, несмотря на большой объем вычислений, несомненное преимущество этого метода в том, что он ясно показывает возможность строгого доказательства законов алгебры множеств без аксиом. Тем самым мы получаем систему, в которой можно не сомневаться.
Дизайн баннера выполнен Анной Горской