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

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

Данное определение, предложенное в книге Куранта и Роббинса «Что такое математика?»Шаблон:Sfn, позволяет рассматривать понятие множество независимо от аксиоматической теории множеств. В книге приведены 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$. Этот метод доказательства основан на одном из законов алгебры множеств.

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

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

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

Например, если $𝑈$ $=\{a,b,c,d\}$, а $S=\{a,c,d\}$, то $\bar{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\}$.

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

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

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.$
5. $A\subseteq 𝑈\mathbf{.}$
6. $A\cup B=B\cup A.$
7. $A\cap B=B\cap A.$
8. $A\cup (B\cup C)=(A\cup B)\cup C.$
9. $A\cap (B\cap C)=(A\cap B)\cap C.$
10. $A\cup A=A.$
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.$
15. $A\cap 𝑈$ $=A.$
16. $A\cup 𝑈\mathbf{=}𝑈\mathbf{.}$
17. $A\cap \varnothing =\varnothing .$
18. $A\subseteq B$ эквивалентно $A\cup B=B$ и эквивалентно $A\cap B=A.$
19. $A\cup \bar{A}=𝑈\mathbf{.}$
20. $A\cap \bar{A}=\varnothing .$
21. $\bar{\varnothing }=𝑈\mathbf{.}$
22. $\overline{𝑈}=\varnothing .$
23. $\overline{\stackrel{‾}{A}}=A.$
24. $A\subseteq B$ эквивалентно $\bar{B}\subseteq \bar{A}.$
25. $\overline{A\cup B}=\bar{A}\cap \bar{B}.$
26. $\overline{A\cap B}=\bar{A}\cup \bar{B}.$

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

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

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

Эти законы впервые были сформулированы и обоснованы в Хабре. Также они были сформулированы и обоснованы в рецезируемых публикациях Шаблон:Sfn и Шаблон:Sfn.

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

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

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

Соотношение $X\subseteq \bar{X}$ возникает и в том случае, когда объекту $X$ присущи не только контрадикторные ($P$ и $\bar{P}$) , но и контрарные свойства $P$ и $Q$, такие, что $P\subseteq \bar{Q}$, но при этом $P\ne \bar{Q}$. Тогда наличие свойств $P$ и $Q$ у объекта $X$ выражается в виде двух посылок 1) $X\subseteq P$ и 2) $X\subseteq Q$.

Свойство контрарности добавляется в качестве третьей посылки: 3) $P\subseteq \bar{Q}$.

Тогда по закону транзитивности из $X\subseteq P$ и $P\subseteq \bar{Q}$ следует $X\subseteq \bar{Q}$, а из соотношений $X\subseteq \bar{Q}$ и $X\subseteq Q$ — соотношение $X\subseteq \bar{X}$.

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

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья