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

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

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

Основы [ править ]

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

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

Основные свойства алгебры множеств [ править ]

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

Коммутативная собственность :

• ${\ 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 \ крышка (B \ чашка C) = (A \ cap B) \ чашка (A \ cap C)}$

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

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

Личность :

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

Дополнение:

• ${\displaystyle A\cup A^{C}=U}$
• ${\displaystyle A\cap A^{C}=\varnothing }$

Выражения идентичности (вместе с коммутативными выражениями) говорят, что, как и 0 и 1 для сложения и умножения, Ø и U являются элементами идентичности для объединения и пересечения, соответственно.

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

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

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

Принцип двойственности [ править ]

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

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

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

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

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

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

• ${\displaystyle A\cup A=A}$
• ${\displaystyle A\cap A=A}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРЕДЛОЖЕНИЕ 4. Пусть A и B - подмножества вселенной U , тогда:

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

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

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

• ${\displaystyle {(A^{C})}^{C}=A}$

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

• ${\displaystyle \varnothing ^{C}=U}$
• ${\displaystyle U^{C}=\varnothing }$

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

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

ПРЕДЛОЖЕНИЕ 5 : Пусть A и B - подмножества вселенной U , тогда:

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

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

Алгебра включения [ править ]

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

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

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

• ${\displaystyle A\subseteq A}$

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

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

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

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

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

ПРЕДЛОЖЕНИЕ 7. Если A , B и C являются подмножествами множества 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 : Для любых двух наборов A и B следующие условия эквивалентны:

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

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

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

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

Предложение 9 : Для любой вселенной U и подмножества A , B и C из 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=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^{C}\cap B}$
• ${\displaystyle (B\setminus A)^{C}=A\cup B^{C}}$
• ${\displaystyle U\setminus A=A^{C}}$
• ${\displaystyle A\setminus U=\varnothing }$

См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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