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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Курант Р., Роббинс Г. Что такое математика?. — изд. 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.