Алгебра множеств

Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Апрель 2023 ) ( Узнайте, как и когда удалять это сообщение )

В математике алгебра множеств , не путать с математической структурой алгебры множеств , определяет свойства и законы множеств , теоретико-множественные операции объединения , пересечения и дополнения , а также отношения равенства множеств и включения множеств. Она также предоставляет систематические процедуры для оценки выражений и выполнения вычислений , включающих эти операции и отношения.

Любой набор множеств, замкнутый относительно теоретико-множественных операций, образует булеву алгебру , в которой оператором соединения является объединение , оператором встречи — пересечение , оператором дополнения — дополнение множества , основанием является ⁠ ⁠,${\displaystyle \varничего_не_существующего }$ а вершиной — рассматриваемое универсумное множество.

Алгебра множеств — это теоретико-множественный аналог алгебры чисел. Так же, как арифметическое сложение и умножение ассоциативны и коммутативны , так же и объединение и пересечение множеств; так же, как арифметическое отношение «меньше или равно» рефлексивно , антисимметрично и транзитивно , так же и отношение множеств «подмножество».

Это алгебра теоретико-множественных операций объединения, пересечения и дополнения, а также отношений равенства и включения. Для базового введения в множества см. статью о множествах , для более полного изложения см. наивную теорию множеств , а для полного строгого аксиоматического рассмотрения см. аксиоматическую теорию множеств .

Бинарные операции объединения множеств ( ⁠ ⁠ )${\displaystyle \чашка}$ и пересечения ( ⁠ ⁠${\displaystyle \cap}$ ) удовлетворяют многим тождествам . Некоторые из этих тождеств или «законов» имеют устоявшиеся названия. ^[2]

Коммутативное свойство :

• ⁠ ⁠${\displaystyle A\чашка B=B\чашка A}$
• ⁠ ⁠${\displaystyle A\cap B=B\cap A}$

Ассоциативное свойство :

• ⁠ ⁠${\displaystyle (A\чашка B)\чашка C=A\чашка (B\чашка C)}$
• ⁠ ⁠${\displaystyle (A\cap B)\cap C=A\cap (B\cap C)}$

Распределительное свойство :

• ⁠ ⁠${\displaystyle A\чашка (B\крышка C)=(A\чашка B)\крышка (A\чашка C)}$
• ⁠ ⁠${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$

Объединение и пересечение множеств можно рассматривать как аналоги сложения и умножения чисел. Подобно сложению и умножению, операции объединения и пересечения являются коммутативными и ассоциативными, а пересечение распределяется по объединению. Однако, в отличие от сложения и умножения, объединение также распределяется по пересечению.

Две дополнительные пары свойств включают специальные множества, называемые пустым множеством ⁠ ⁠${\displaystyle \varничего_не_существующего }$ и универсумным множеством ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ ; вместе с оператором дополнения ( ⁠ ⁠${\displaystyle A^{\complement}}$ обозначает дополнение ⁠ ⁠${\displaystyle А}$ . Это также можно записать как ⁠ ⁠${\displaystyle А'}$ , читать как «A prime»). Пустое множество не имеет членов, а универсум имеет всех возможных членов (в определенном контексте).

Личность:

• ⁠ ⁠${\displaystyle A\cup \varnothing =A}$
• ⁠ ⁠${\displaystyle A\cap {\boldsymbol {U}}=A}$

Дополнение:

• ⁠ ⁠${\displaystyle A\cup A^{\complement }={\boldsymbol {U}}}$
• ⁠ ⁠${\displaystyle A\cap A^{\complement }=\varnothing }$

Выражения тождественности (вместе с коммутативными выражениями) говорят, что, как и 0 и 1 для сложения и умножения, ⁠ ⁠${\displaystyle \varничего_не_существующего }$ и ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ являются элементами тождественности для объединения и пересечения соответственно.

В отличие от сложения и умножения, объединение и пересечение не имеют обратных элементов . Однако законы дополнения дают фундаментальные свойства несколько обратной унарной операции дополнения множеств.

Предыдущие пять пар формул — коммутативная, ассоциативная, дистрибутивная, тождественная и дополнительная — охватывают всю алгебру множеств в том смысле, что каждое допустимое предложение в алгебре множеств может быть выведено из них.

Обратите внимание, что если формулы дополнения ослабить до правила ⁠ ⁠${\displaystyle (A^{\complement})^{\complement}=A}$ , то это будет в точности алгебра пропозициональной линейной логики ^{[ требуется пояснение ]} .

Каждая из указанных выше идентичностей является одной из пары идентичностей, каждая из которых может быть преобразована в другую путем замены ⁠ ⁠${\displaystyle \чашка}$ и ⁠ ⁠${\displaystyle \cap}$ , а также путем замены ⁠ ⁠${\displaystyle \varничего_не_существующего }$ и ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ .

Это примеры чрезвычайно важного и мощного свойства алгебры множеств, а именно принципа двойственности для множеств, который утверждает, что для любого истинного утверждения о множествах, двойственное утверждение, полученное путем перестановки объединений и пересечений, перестановки ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ и ⁠ ⁠${\displaystyle \varничего_не_существующего }$ и обращения включений, также является истинным. Говорят, что утверждение является самодвойственным, если оно равно своему собственному двойственному.

Следующее предложение формулирует еще шесть важных законов алгебры множеств, касающихся объединений и пересечений.

ПРЕДЛОЖЕНИЕ 3 : Для любых подмножеств ⁠ ⁠${\displaystyle А}$ и ⁠ ⁠${\displaystyle Б}$ множества универсума ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ справедливы следующие тождества:

идемпотентные законы:

• ⁠ ⁠${\displaystyle A\чашка A=A}$
• ⁠ ⁠${\displaystyle А\cap А=А}$

Законы господства:

• ⁠ ⁠${\displaystyle A\cup {\boldsymbol {U}}={\boldsymbol {U}}}$
• ⁠ ⁠${\displaystyle A\cap \varnothing =\varnothing }$

Законы поглощения :

• ⁠ ⁠${\displaystyle A\чашка (A\чашка B)=A}$
• ⁠ ⁠${\displaystyle A\cap (A\cup B)=A}$

Как отмечено выше, каждый из законов, указанных в предложении 3, может быть выведен из пяти основных пар законов, указанных выше. В качестве иллюстрации ниже приведено доказательство для идемпотентного закона для объединения.

Доказательство:

⁠ ⁠${\displaystyle A\чашка A}$	⁠ ⁠${\displaystyle =(A\cup A)\cap {\boldsymbol {U}}}$	по закону тождества пересечения
	⁠ ⁠${\displaystyle =(A\cup A)\cap (A\cup A^{\complement })}$	по закону о дополнительном союзе
	⁠ ⁠${\displaystyle =A\cup (A\cap A^{\complement })}$	по распределительному закону объединения по пересечению
	⁠ ⁠${\displaystyle =A\cup \varnothing }$	по закону дополнения для пересечения
	⁠ ⁠${\displaystyle =А}$	законом об идентичности для союза

Следующее доказательство показывает, что двойственное доказательству вышеприведенного доказательства является доказательством двойственного закона идемпотентности для объединения, а именно идемпотентного закона для пересечения.

Доказательство:

⁠ ⁠${\displaystyle А\cap А}$	⁠ ⁠${\displaystyle =(A\cap A)\cup \varnothing }$	законом об идентичности для союза
	⁠ ⁠${\displaystyle =(A\cap A)\cup (A\cap A^{\complement })}$	по закону дополнения для пересечения
	⁠ ⁠${\displaystyle =A\cap (A\cup A^{\complement })}$	по распределительному закону пересечения по объединению
	⁠ ⁠${\displaystyle =A\cap {\boldsymbol {U}}}$	по закону о дополнительном союзе
	⁠ ⁠${\displaystyle =А}$	по закону тождества для пересечения

Пересечение можно выразить через разность множеств:

⁠ ⁠${\displaystyle A\cap B=A\setminus (A\setminus B)}$

Следующее предложение формулирует еще пять важных законов алгебры множеств, связанных с дополнениями.

ПРЕДЛОЖЕНИЕ 4 : Пусть ⁠ ⁠${\displaystyle А}$ и ⁠ ⁠${\displaystyle Б}$ будут подмножествами вселенной ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ , тогда:

Законы де Моргана :

• ⁠ ⁠${\displaystyle (A\cup B)^{\complement}=A^{\complement}\cap B^{\complement}}$
• ⁠ ⁠${\displaystyle (A\cap B)^{\complement}=A^{\complement}\cup B^{\complement}}$

Закон двойного дополнения или инволюции :

• ⁠ ⁠${\displaystyle (A^{\complement})^{\complement}=A}$

Законы дополнения для множества вселенной и пустого множества:

• ⁠ ⁠${\displaystyle \varnothing ^{\complement }={\boldsymbol {U}}}$
• ⁠ ⁠${\displaystyle {\boldsymbol {U}}^{\complement }=\varnothing }$

Обратите внимание, что закон двойного дополнения является самодвойственным.

Следующее предложение, которое также является самодвойственным, утверждает, что дополнение множества — это единственное множество, которое удовлетворяет законам дополнения. Другими словами, дополнение характеризуется законами дополнения.

ПРЕДЛОЖЕНИЕ 5 : Пусть ⁠ ⁠${\displaystyle А}$ и ⁠ ⁠${\displaystyle Б}$ будут подмножествами вселенной ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ , тогда:

уникальность дополнений:

• Если ⁠ ⁠${\displaystyle A\cup B={\boldsymbol {U}}}$ , и ⁠ ⁠${\displaystyle A\cap B=\varnothing}$ , то ⁠ ⁠${\displaystyle B=A^{\complement}}$

Следующее предложение утверждает, что включение , то есть бинарное отношение одного множества, являющегося подмножеством другого, является частичным порядком .

ПРЕДЛОЖЕНИЕ 6 : Если ⁠ ⁠${\displaystyle А}$ , ⁠ ⁠${\displaystyle Б}$ и ⁠ ⁠${\displaystyle С}$ являются множествами, то выполняется следующее:

рефлексивность :

• ⁠ ⁠${\displaystyle A\subseteq A}$

антисимметрия :

• ⁠ ⁠${\displaystyle A\subseteq B}$ и ⁠ ⁠${\displaystyle B\subseteq A}$ тогда и только тогда, когда ⁠ ⁠${\displaystyle А=Б}$

транзитивность :

• Если ⁠ ⁠${\displaystyle A\subseteq B}$ и ⁠ ⁠${\displaystyle B\subseteq C}$ , то ⁠ ⁠${\displaystyle A\subseteq C}$

Следующее предложение утверждает, что для любого множества S множество элементов S , упорядоченное по включению , является ограниченной решеткой и, следовательно, вместе с приведенными выше законами дистрибутивности и дополнения, показывает, что оно является булевой алгеброй .

ПРЕДЛОЖЕНИЕ 7 : Если ⁠ ⁠${\displaystyle А}$ , ⁠ ⁠${\displaystyle Б}$ и ⁠ ⁠${\displaystyle С}$ являются подмножествами множества ⁠ ⁠,${\displaystyle S}$ то выполняется следующее:

существование наименьшего элемента и наибольшего элемента :

• ⁠ ⁠${\displaystyle \varnothing \subseteq A\subseteq S}$

существование соединений :

• ⁠ ⁠${\displaystyle A\subseteq A\cup B}$
• Если ⁠ ⁠${\displaystyle A\subseteq C}$ и ⁠ ⁠${\displaystyle B\subseteq C}$ , то ⁠ ⁠${\displaystyle A\cup B\subseteq C}$

существование встречается :

• ⁠ ⁠${\displaystyle A\cap B\subseteq A}$
• Если ⁠ ⁠${\displaystyle C\subseteq A}$ и ⁠ ⁠${\displaystyle C\subseteq B}$ , то ⁠ ⁠${\displaystyle C\subseteq A\cap B}$

Следующее предложение утверждает, что утверждение ⁠ ⁠${\displaystyle A\subseteq B}$ эквивалентно различным другим утверждениям, включающим объединения, пересечения и дополнения.

ПРЕДЛОЖЕНИЕ 8 : Для любых двух множеств ⁠ ⁠${\displaystyle А}$ и ⁠ ⁠${\displaystyle Б}$ следующие условия эквивалентны:

• ⁠ ⁠${\displaystyle A\subseteq B}$
• ⁠ ⁠${\displaystyle A\cap B=A}$
• ⁠ ⁠${\displaystyle A\чашка B=B}$
• ⁠ ⁠${\displaystyle A\setminus B=\varnothing}$
• ⁠ ⁠${\displaystyle B^{\complement }\subseteq A^{\complement }}$

Приведенное выше предложение показывает, что отношение включения множеств может быть охарактеризовано либо с помощью операции объединения множеств, либо с помощью операции пересечения множеств, что означает, что понятие включения множеств аксиоматически излишне.

В следующем предложении перечислены несколько тождеств, касающихся относительных дополнений и теоретико-множественных различий.

ПРЕДЛОЖЕНИЕ 9 : Для любой вселенной ⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ и подмножеств ⁠ ⁠${\displaystyle A}$ , ⁠ ⁠${\displaystyle B}$ и ⁠ ⁠ ${\displaystyle C}$⁠ ⁠${\displaystyle {\boldsymbol {U}}}$ , справедливы следующие тождества :

• ⁠ ⁠${\displaystyle C\setminus (A\cap B)=(C\setminus A)\cup (C\setminus B)}$
• ⁠ ⁠${\displaystyle C\setminus (A\cup B)=(C\setminus A)\cap (C\setminus B)}$
• ⁠ ⁠${\displaystyle C\setminus (B\setminus A)=(A\cap C)\cup (C\setminus B)}$
• ⁠ ⁠${\displaystyle (B\setminus A)\cap C=(B\cap C)\setminus (A\cap C)=(B\cap C)\setminus A=B\cap (C\setminus A)}$
• ⁠ ⁠${\displaystyle (B\setminus A)\cup C=(B\cup C)\setminus (A\setminus C)}$
• ⁠ ⁠${\displaystyle (B\setminus A)\setminus C=B\setminus (A\cup C)}$
• ⁠ ⁠${\displaystyle A\setminus A=\varnothing }$
• ⁠ ⁠${\displaystyle \varnothing \setminus A=\varnothing }$
• ⁠ ⁠${\displaystyle A\setminus \varnothing =A}$
• ⁠ ⁠${\displaystyle B\setminus A=A^{\complement }\cap B}$
• ⁠ ⁠${\displaystyle (B\setminus A)^{\complement }=A\cup B^{\complement }}$
• ⁠ ⁠${\displaystyle {\boldsymbol {U}}\setminus A=A^{\complement }}$
• ⁠ ⁠${\displaystyle A\setminus {\boldsymbol {U}}=\varnothing }$

• σ-алгебра — алгебра множеств, дополненная включением счетно бесконечных операций.
• Аксиоматическая теория множеств
• Изображение (математика) § Свойства
• Поле множеств
• Список установленных тождеств и отношений
• Наивная теория множеств
• Множество (математика)
• Топологическое пространство — подмножество ⁠ ⁠${\displaystyle \wp (X)}$ , множество степеней ⁠ ⁠${\displaystyle X}$ , замкнутое относительно произвольного объединения, конечного пересечения и содержащее ⁠ ⁠${\displaystyle \varnothing }$ и ⁠ ⁠${\displaystyle X}$ .

• Столл, Роберт Р.; Теория множеств и логика , Минеола, Нью-Йорк: Dover Publications (1979) ISBN 0-486-63829-4 . «Алгебра множеств», стр. 16—23. 
• Курант, Ричард, Герберт Роббинс, Ян Стюарт, Что такое математика?: Элементарный подход к идеям и методам , Oxford University Press, США, 1996. ISBN 978-0-19-510519-3 . «ДОПОЛНЕНИЕ К ГЛАВЕ II АЛГЕБРА МНОЖЕСТВ». 

• Операции над множествами в ProvenMath