Алгебра множеств (по Куранту и Роббинсу)

Эта статья — об алгебраической системе, независимой от теории множеств. О поле множеств см. Алгебра множеств.

Алгебра множеств — это математическая система, подобная элементарной арифметике, в которой вместо операций с числами (умножение, сложение и разность) используются операции c множествами пересечение (${\displaystyle \cap }$), объединение (${\displaystyle \cup }$) и дополнение (${\displaystyle {\overline {A}}}$), а вместо отношения меньше или равно (${\displaystyle \leq }$) — отношение включение (${\displaystyle \subseteq }$).

Данное определение, предложенное в книге Куранта и Роббинса «Что такое математика?»^[1], позволяет рассматривать понятие множество независимо от аксиоматической теории множеств. В книге приведены 26 законов алгебры множеств, которые соответствуют законам классической логики и которые, как утверждают авторы книги, можно доказать без аксиом. В англоязычной Википедии содержится этот же вариант определения алгебры множеств.

Основные понятия

• Множество, элемент. Совокупность объектов, объединенных общим свойством или несколькими свойствами, будем называть множествами, а сами объекты – элементами. Если известно, что множество ${\displaystyle D}$ состоит из элементов ${\displaystyle a,c}$ и ${\displaystyle f}$ и только из них, то используется запись ${\displaystyle D=\{a,c,f\}}$. Порядок элементов у множеств несущественен. Например, ${\displaystyle D=\{c,f,a\}}$ тоже правильно.

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

• Отношение принадлежности. Отношение между элементом и множеством называется отношением принадлежности и обозначается символом (${\displaystyle \in }$). Запись ${\displaystyle a\in D}$ означает, что элемент ${\displaystyle a}$ принадлежит множеству ${\displaystyle D}$. В то же время запись ${\displaystyle b\notin D}$ означает, что элемент ${\displaystyle b}$ не принадлежит множеству ${\displaystyle D}$.
• Отношение включения множеств. Пусть даны множества ${\displaystyle A}$ и ${\displaystyle B}$. Тогда ${\displaystyle A\subseteq B}$ (понимается как «${\displaystyle A}$ включено в ${\displaystyle B}$ или равно ему»), если в множестве ${\displaystyle A}$ не существует элементов, не принадлежащих множеству ${\displaystyle B}$.

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

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

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

Во многих случаях предполагается, что анализ соотношений между множествами выполняется в рамках некоторого универсального множества, называемого универсумом. Обозначим его ${\displaystyle {\bf {\it {U}}}}$.

• Дополнение множества. Если задан универсум ${\displaystyle {\bf {\it {U}}}}$, то дополнением множества ${\displaystyle A}$ (обозначается ${\displaystyle {\overline {A}}}$) является операция, в результате которой образуется множество, содержащее все элементы универсума ${\displaystyle {\bf {\it {U}}}}$ за исключением всех тех элементов, которые содержатся в ${\displaystyle A}$.

Например, если ${\displaystyle {\bf {\it {U}}}}$ ${\displaystyle =\{a,b,c,d\}}$, а ${\displaystyle S=\{a,c,d\}}$, то ${\displaystyle {\overline {S}}=\{b\}}$.

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

Например, если ${\displaystyle K=\{b,d\}}$, ${\displaystyle L=\{b,c,d\}}$ и ${\displaystyle M=\{a,c\}}$, то ${\displaystyle K\cap L=\{b,d\}}$, ${\displaystyle K\cap M=\varnothing }$.

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

Например, если ${\displaystyle K=\{b,d\}}$, ${\displaystyle L=\{a,c,d\}}$, то ${\displaystyle K\cup L=\{a,b,c,d\}}$.

Законы алгебры множеств, указанные в книге Куранта и Роббинса

Ниже приведены законы алгебры множеств, которые содержатся в книге Куранта и Роббинса^[1].

1. ${\displaystyle A\subseteq A.}$
2. Если ${\displaystyle A\subseteq B}$ и ${\displaystyle B\subseteq A,}$ то ${\displaystyle A=B.}$
3. Если ${\displaystyle A\subseteq B}$ и ${\displaystyle B\subseteq C,}$ то ${\displaystyle A\subseteq C.}$
4. ${\displaystyle \varnothing \subseteq A.\qquad \qquad \qquad \qquad \qquad \qquad }$
5. ${\displaystyle A\subseteq {\bf {{\it {U}}.}}}$
6. ${\displaystyle A\cup B=B\cup A.\qquad \qquad \qquad \qquad }$
7. ${\displaystyle A\cap B=B\cap A.}$
8. ${\displaystyle A\cup (B\cup C)=(A\cup B)\cup C.\qquad \quad \;}$
9. ${\displaystyle A\cap (B\cap C)=(A\cap B)\cap C.}$
10. ${\displaystyle A\cup A=A.\qquad \qquad \qquad \qquad \qquad }$
11. ${\displaystyle A\cap A=A.}$
12. ${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C).}$
13. ${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C).}$
14. ${\displaystyle A\cup \varnothing =A.\qquad \qquad \qquad \qquad \qquad }$
15. ${\displaystyle A\cap {\bf {\it {U}}}}$ ${\displaystyle =A.}$
16. ${\displaystyle A\cup {\bf {{\it {U}}={\bf {{\it {U}}.\qquad \qquad \qquad \;\qquad \quad \;}}}}}$
17. ${\displaystyle A\cap \varnothing =\varnothing .}$
18. ${\displaystyle A\subseteq B}$ эквивалентно ${\displaystyle A\cup B=B}$ и эквивалентно ${\displaystyle A\cap B=A.}$
19. ${\displaystyle A\cup {\overline {A}}={\bf {{\it {U}}.\qquad \qquad \qquad \qquad \qquad }}}$
20. ${\displaystyle A\cap {\overline {A}}=\varnothing .}$
21. ${\displaystyle {\overline {\varnothing }}={\bf {{\it {U}}.\qquad \quad \qquad \qquad \qquad \qquad \quad }}}$
22. ${\displaystyle {\overline {\bf {\it {U}}}}=\varnothing .}$
23. ${\displaystyle {\overline {\overline {A}}}=A.}$
24. ${\displaystyle A\subseteq B}$ эквивалентно ${\displaystyle {\overline {B}}\subseteq {\overline {A}}.}$
25. ${\displaystyle {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}.\qquad \qquad \qquad \qquad }$
26. ${\displaystyle {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}.}$

Для доказательства этих законов Курант и Роббинс предложили^[2] использовать рисунки в виде некоторых фигур на плоскости (по сути это диаграммы Эйлера) и быть очень внимательными при рассмотрении, «чтобы не упустить ни одной из возникающих логических возможностей, когда речь идет о наличии общих элементов двух множеств или, напротив, наличии в одном множестве элементов, которые не содержатся в другом».

Более подробно о доказательстве законов алгебры множеств без аксиом содержится в книге Кулика ^[3]. Схема доказательства с использованием всех возможных соотношений между двумя множествами (16 вариантов) приведена в статье в Хабре^[4].

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

Эти законы впервые были сформулированы и обоснованы в Хабре^[5][6]. Два из тр1х новых законов были сформулированы и обоснованы в статье, опубликованной в 2024 году^[7].

• Закон парадокса: если доказано, что ${\displaystyle X\subseteq {\overline {X}}}$, то ${\displaystyle X=\varnothing }$.

К закону парадокса приводит ситуация, когда некоторый объект ${\displaystyle X}$ обладает свойством ${\displaystyle Y}$ и в то же время не обладает им. Выразим эту ситуацию в виде соотношения между множествами: 1) ${\displaystyle X\subseteq Y}$; 2) ${\displaystyle X\subseteq {\overline {Y}}}$.

Вычислим контрапозиции этих суждений: 3) ${\displaystyle {\overline {Y}}\subseteq {\overline {X}}}$; 4) ${\displaystyle Y\subseteq {\overline {X}}}$. Из суждений ${\displaystyle X\subseteq Y}$ и ${\displaystyle Y\subseteq {\overline {X}}}$ по закону транзитивности следует ${\displaystyle X\subseteq {\overline {X}}}$. Таким образом, данная ситуация равносильна закону парадокса.

• Закон непустого пересечения: если ${\displaystyle \alpha \neq \varnothing }$, ${\displaystyle \alpha \subseteq A}$ и ${\displaystyle \alpha \subseteq B}$, то ${\displaystyle A\cap B\neq \varnothing }$.

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

• Закон существования множества : если ${\displaystyle X\neq \varnothing }$ и ${\displaystyle X\subseteq Y}$, то ${\displaystyle Y\neq \varnothing }$.

Этот закон интересен тем, что он по форме соответствует давно известному в логике правилу вывода modus ponens (${\displaystyle MP}$): если выводимы формулы ${\displaystyle A}$ и ${\displaystyle A\supset B}$, то выводима формула ${\displaystyle B}$ (${\displaystyle \supset }$ – обозначение логической связки импликации). По сути, закон существования – это ${\displaystyle MP}$ применительно к множествам.

Примеры использования этих законов можно найти в статье ^[6].

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

1. В алгебре множеств основным (системообразующим) является не отношение принадлежности (${\displaystyle \in }$), а отношение включения (${\displaystyle \subseteq }$), для которого самоприменимость (${\displaystyle A\subseteq A}$) не влечет парадоксов.
2. Законы алгебры множеств можно доказать без аксиом.

Примечания

1. Курант, Роббинс, 2015, с. 134-142.
2. Курант, Роббинс, 2015, с. 137-138.
3. Кулик, 2020, с. 20-23.
4. На чем основана логика? Часть 1. Алгебра множеств без аксиом / Хабр
5. Закон парадокса в логике и математике / Хабр
6. На чем основана логика? Часть 2. Математическая модель полисиллогистики / Хабр
7. Kulik B.A., Fridman A.Ya., 2024, с. 59-71.

Литература

• Курант Р., Роббинс Г. Что такое математика?. — изд. 7-е, стереотипное. — М.: МЦНМО, 2015. — 568 с.
• Кулик Б.А. Логика и математика: просто о сложных методах логического анализа. — СПб.: Политехника, 2020. — 141 с.
• Kulik B.A., Fridman A.Ya. New Methods for Recognizing and Resolving Contradictions // Tarasova, I.L., Kulik, B.A. (eds) Smart Electromechanical Systems. Studies in Systems, Decision and Control. — Springer, Cham, 2024. — Vol. 544. — P. 59—71.