WikiDer > Алгебра множеств
В математика, алгебра множеств, не путать с математическая структура из ан алгебра множеств, определяет свойства и законы наборытеоретико-множественная операции из союз, пересечение, и дополнение и связи набора равенство и установить включение. Он также предоставляет систематические процедуры для оценки выражений и выполнения вычислений, включающих эти операции и отношения.
Любой набор множеств, замкнутый относительно теоретико-множественных операций, образует Булева алгебра с оператором соединения, являющимся союз, оператор встречи пересечение, оператор дополнения набор дополнений, нижнее существо и вершина вселенная поставлен на рассмотрение.
Основы
Алгебра множеств - теоретико-множественный аналог алгебры чисел. Так же как арифметика добавление и умножение находятся ассоциативный и коммутативный, так установлены объединение и пересечение; так же, как арифметическое соотношение "меньше или равно" рефлексивный, антисимметричный и переходный, так это отношение множества "подмножества".
Это алгебра теоретико-множественных операций объединения, пересечения и дополнения, а также отношений равенства и включения. Базовое введение в наборы см. В статье о наборы, для более полного описания см. наивная теория множеств, а для полного строгого аксиоматический лечение см. аксиоматическая теория множеств.
Основные свойства алгебры множеств
В бинарные операции набора союз () и пересечение () удовлетворить многие идентичности. Некоторые из этих идентичностей или «законов» имеют хорошо известные названия.
Объединение и пересечение множеств можно рассматривать как аналог сложения и умножения чисел. Подобно сложению и умножению, операции объединения и пересечения бывают коммутативными и ассоциативными, а операции пересечения распределяет над союзом. Однако, в отличие от сложения и умножения, объединение также распределяет по пересечению.
Две дополнительные пары свойств включают специальные наборы, называемые пустой набор Ø и набор вселенной ; вместе с дополнять оператор ( обозначает дополнение . Это также можно записать как , читается как простое число). Пустой набор не имеет элементов, а набор юниверсов имеет все возможные элементы (в определенном контексте).
- Личность :
- Дополнение:
Выражения идентичности (вместе с коммутативными выражениями) говорят, что, как и 0 и 1 для сложения и умножения, Ø и U являются элементы идентичности для объединения и пересечения соответственно.
В отличие от сложения и умножения, объединение и пересечение не имеют обратные элементы. Однако законы дополнения дают фундаментальные свойства несколько обратных унарная операция комплектации.
Предыдущие пять пар формул - коммутативная, ассоциативная, дистрибутивная, тождественная и дополнительная - охватывают всю алгебру множеств в том смысле, что каждое действительное предложение в алгебре множеств может быть выведено из них.
Обратите внимание, что если формулы дополнения ослаблены до правила , то это и есть алгебра пропозициональных линейная логика[требуется разъяснение].
Принцип двойственности
Каждое из указанных выше тождеств является одним из пары тождеств, каждое из которых может быть преобразовано в другое путем замены и ∩, а также Ø и U.
Это примеры чрезвычайно важного и мощного свойства алгебры множеств, а именно: принцип двойственности для множеств, который утверждает, что для любого истинного утверждения о множествах двойной заявление, полученное путем перестановки союзов и перекрестков, перестановки U и Ø и реверсивные включения тоже верны. Утверждение называется самодвойственный если он равен своему дуалу.
Некоторые дополнительные законы для союзов и пересечений
Следующее предложение устанавливает шесть более важных законов алгебры множеств, включающих объединения и пересечения.
ПРЕДЛОЖЕНИЕ 3: Для любого подмножества А и B набора вселенной U, выполняются следующие тождества:
- идемпотент законы:
- законы господства:
- законы поглощения:
Как отмечалось выше, каждый из законов, изложенных в предложении 3, может быть выведен из пяти основных пар законов, указанных выше. В качестве иллюстрации ниже приводится доказательство идемпотентного закона для союза.
Доказательство:
по тождественному закону пересечения | ||
согласно закону о дополнительном союзе | ||
по распределительному закону объединения по пересечению | ||
по закону дополнения для пересечения | ||
по закону идентичности для союза |
Следующее доказательство показывает, что двойственное к приведенному выше доказательству является доказательством двойственного идемпотентного закона для объединения, а именно идемпотентного закона для пересечения.
Доказательство:
по закону идентичности для союза | ||
по закону дополнения для пересечения | ||
по распределительному закону пересечения по объединению | ||
согласно закону о дополнительном союзе | ||
по закону тождества для пересечения |
Пересечение можно выразить через разность множеств:
Некоторые дополнительные законы для дополнений
Следующее предложение устанавливает еще пять важных законов алгебры множеств, включая дополнения.
ПРЕДЛОЖЕНИЕ 4: Позволять А и B быть подмножества Вселенной U, тогда:
- Законы де Моргана:
- двойное дополнение или инволюция закон:
- законы дополнения для множества вселенной и пустого множества:
Обратите внимание, что закон двойного дополнения самодвойственен.
Следующее предложение, которое также является самодуальным, говорит, что дополнение набора - это единственный набор, который удовлетворяет законам дополнения. Другими словами, дополнение характеризуется законами дополнения.
ПРЕДЛОЖЕНИЕ 5: Позволять А и B быть подмножествами вселенной U, тогда:
- уникальность дополнений:
- Если , и , тогда
Алгебра включения
Следующее предложение говорит, что включение, это бинарное отношение одного набора, являющегося подмножеством другого, является частичный заказ.
ПРЕДЛОЖЕНИЕ 6: Если А, B и C - множества, то справедливы следующие условия:
- антисимметрия:
- и если и только если
- транзитивность:
- Если и , тогда
Следующее предложение говорит, что для любого множества S, то набор мощности из S, упорядоченный по включению, является ограниченная решетка, и, следовательно, вместе с законами распределения и дополнения, приведенными выше, показывают, что это Булева алгебра.
ПРЕДЛОЖЕНИЕ 7: Если А, B и C являются подмножествами множества S то имеет место следующее:
- наличие наименьший элемент и величайший элемент:
- Существование присоединяется:
- Если и , тогда
- Существование встречает:
- Если и , тогда
Следующее предложение говорит, что утверждение эквивалентно различным другим операторам, включающим объединения, пересечения и дополнения.
ПРЕДЛОЖЕНИЕ 8: Для любых двух наборов А и B, следующие эквиваленты:
Вышеприведенное предложение показывает, что отношение включения множеств может быть охарактеризовано либо операцией объединения множеств, либо пересечением множеств, что означает, что понятие включения множеств аксиоматически излишне.
Алгебра относительных дополнений
В следующем предложении перечислены несколько тождеств, касающихся относительные дополнения и теоретико-множественные различия.
ПРЕДЛОЖЕНИЕ 9: Для любой вселенной U и подмножества А, B, и C из U, выполняются следующие тождества:
Смотрите также
- σ-алгебра представляет собой алгебру множеств, дополненную счетным числом операций.
- Аксиоматическая теория множеств
- Изображение (математика) #Properties
- Поле наборов
- Список установленных идентичностей и отношений
- Наивная теория множеств
- Набор (математика)
- Топологическое пространство - подмножество , набор мощности , замкнутая относительно произвольного объединения, конечное пересечение и содержащая и .
Рекомендации
- Столл, Роберт Р .; Теория множеств и логика, Минеола, Нью-Йорк: Dover Publications (1979) ISBN 0-486-63829-4. «Алгебра множеств», стр. 16–23..
- Курант, Ричард, Герберт Роббинс, Ян Стюарт, Что такое математика?: Элементарный подход к идеям и методам, Oxford University Press, США, 1996. ISBN 978-0-19-510519-3. «ДОБАВЛЕНИЕ К ГЛАВЕ II. АЛГЕБРА МНОЖЕСТВ».