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

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

Алгебра множеств — это математическая система, подобная элементарной арифметике, в которой вместо операций с числами (умножение, сложение и разность) используются операции 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 вариантов) приведена в статье в Хабре.

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

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

2. Законы алгебры множеств можно доказать без аксиом.

Литература

• Курант Р., Роббинс Г. Что такое математика?. — изд. 7-е, стереотипное. — М.: МЦНМО, 2015. — 568 с.
• Кулик Б.А. Логика и математика: просто о сложных методах логического анализа. — СПб.: Политехника, 2020. — 141 с.

[[Категория:Алгебра]