Алгебра множеств - Algebra of sets

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

Любой набор множеств, замкнутый под действием теоретико-множественных операций, образует булеву алгебру с оператором соединения , являющимся объединением , оператором встречи является пересечение , оператором дополнения является набор дополнений , нижний и верхний являются рассматриваемым множеством вселенной . ${\ 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 \ чашка A ^ {C} = U}$
• ${\ Displaystyle A \ cap A ^ {C} = \ varnothing}$

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

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

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

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

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

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

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

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

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

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

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

• ${\ Displaystyle A \ чашка A = A}$
• ${\ Displaystyle A \ cap A = A}$

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

• ${\ Displaystyle A \ чашка U = U}$
• ${\ displaystyle A \ cap \ varnothing = \ varnothing}$

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

• ${\ Displaystyle A \ чашка (A \ крышка B) = A}$
• ${\ Displaystyle A \ крышка (A \ чашка B) = A}$

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

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

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

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

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

${\ displaystyle A \ cap A}$	${\ Displaystyle = (A \ крышка A) \ чашка \ varnothing}$	по закону тождества для союза
	${\ Displaystyle = (A \ крышка A) \ чашка (A \ крышка 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 \ чашка B) ^ {C} = A ^ {C} \ cap B ^ {C}}$
• ${\ Displaystyle (A \ крышка B) ^ {C} = A ^ {C} \ чашка B ^ {C}}$

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

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

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

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

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

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

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

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

• Если , и , то${\ Displaystyle A \ чашка B = U}$${\ Displaystyle A \ cap B = \ varnothing}$${\ displaystyle B = A ^ {C}}$

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

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

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

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

• ${\ displaystyle A \ substeq A}$

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

• ${\ displaystyle A \ substeq B}$и если и только если${\ Displaystyle B \ substeq A}$${\ displaystyle A = B}$

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

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

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

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

наличие наименьшего элемента и наибольшего элемента :

• ${\ displaystyle \ varnothing \ substeq A \ substeq S}$

наличие стыков :

• ${\ Displaystyle A \ substeq A \ чашка B}$
• Если и , то${\ displaystyle A \ substeq C}$${\ Displaystyle B \ substeq C}$${\ Displaystyle A \ чашка B \ substeq C}$

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

• ${\ Displaystyle A \ cap B \ substeq A}$
• Если и , то${\ Displaystyle C \ substeq A}$${\ Displaystyle C \ substeq B}$${\ Displaystyle C \ substeq A \ cap B}$

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

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

• ${\ displaystyle A \ substeq B}$
• ${\ Displaystyle A \ cap B = A}$
• ${\ Displaystyle A \ чашка B = B}$
• ${\ displaystyle A \ setminus B = \ varnothing}$
• ${\ displaystyle B ^ {C} \ substeq A ^ {C}}$

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

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

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

Предложение 9 : Для любой вселенной U и подмножества A , B и C из U , следующие тождества:

• ${\ Displaystyle С \ setminus (A \ cap B) = (C \ setminus A) \ чашка (C \ setminus B)}$
• ${\ Displaystyle С \ setminus (A \ чашка B) = (C \ setminus A) \ cap (C \ setminus B)}$
• ${\ Displaystyle С \ setminus (B \ setminus A) = (A \ cap C) \ чашка (C \ setminus B)}$
• ${\ Displaystyle (В \ setminus A) \ cap C = (B \ cap C) \ setminus A = B \ cap (C \ setminus A)}$
• ${\ Displaystyle (В \ setminus A) \ чашка C = (B \ cup C) \ setminus (A \ setminus C)}$
• ${\ Displaystyle (В \ setminus A) \ setminus C = B \ setminus (A \ чашка 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 \ чашка 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