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

Эта статья посвящена алгебраическим свойствам операций над множествами в целом. Для булевой алгебры множеств см. Поле множеств .

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

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

Основы

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

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

Фундаментальные свойства алгебры множеств

Бинарные операции объединения множеств ( $\cup$) и пересечение ( $\cap$) удовлетворяют многим тождествам . Некоторые из этих личностей или «законов» имеют хорошо известные названия.

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

• $A\cup B=B\cup A$
• $A\cap B=B\cap A$

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

• $(A\cup B)\cup C=A\cup (B\cup C)$
• $(A\cap B)\cap C=A\cap (B\cap C)$

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

• $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
• $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

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

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

Личность:

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

Дополнение:

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

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

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

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

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

Принцип двойственности

Смотрите также: Двойственность (теория порядка)

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

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

Некоторые дополнительные законы для союзов и пересечений

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

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

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

• $A\cup A=A$
• $A\cap A=A$

законы доминирования:

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

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

• $A\cup (A\cap B)=A$
• $A\cap (A\cup B)=A$

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

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

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

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

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

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

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

$A\cap B=A\setminus (A\setminus B)$

Некоторые дополнительные законы для дополнений

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

ПРЕДЛОЖЕНИЕ 4. Пусть $A$ и $B$ быть подмножествами вселенной ${\boldsymbol {U}}$, затем:

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

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

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

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

законы дополнения для множества юниверсов и пустого множества:

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

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

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

ПРЕДЛОЖЕНИЕ 5. Пусть $A$ и $B$ быть подмножествами вселенной ${\boldsymbol {U}}$, затем:

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

• Если $A\cup B={\boldsymbol {U}}$, и $A\cap B=\varnothing$, затем $B=A^{\complement }$

Алгебра включения

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

ПРЕДЛОЖЕНИЕ 6 : Если $A$, $B$ и $C$ являются множествами, то выполняются следующие условия:

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

• $A\subseteq A$

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

• $A\subseteq B$ и $B\subseteq A$ тогда и только тогда, когда $A=B$

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

• Если $A\subseteq B$ и $B\subseteq C$, затем $A\subseteq C$

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

ПРЕДЛОЖЕНИЕ 7 : Если $A$, $B$ и $C$ являются подмножествами множества $S$ тогда имеет место следующее:

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

• $\varnothing \subseteq A\subseteq S$

наличие объединений :

• $A\subseteq A\cup B$
• Если $A\subseteq C$ и $B\subseteq C$, затем $A\cup B\subseteq C$

наличие встреч :

• $A\cap B\subseteq A$
• Если $C\subseteq A$ и $C\subseteq B$, затем $C\subseteq A\cap B$

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

ПРЕДЛОЖЕНИЕ 8. Для любых двух наборов $A$ и $B$, следующие эквивалентны:

• $A\subseteq B$
• $A\cap B=A$
• $A\cup B=B$
• $A\setminus B=\varnothing$
• $B^{\complement }\subseteq A^{\complement }$

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

Алгебра относительных дополнений

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

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

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

См. также

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

Ссылки

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

Внешние ссылки

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