Алгебра множеств - 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 чашка 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: Для любого подмножества А и 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 А крышка В = А setminus (A setminus B)}$

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

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

ПРЕДЛОЖЕНИЕ 4: Позволять А и 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: Позволять А и B быть подмножествами вселенной U, тогда:

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

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

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

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

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