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

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

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

Основы

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

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

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

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

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

⁠ $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$ ⁠ .

Ссылки

^ Пол Р. Халмос (1968). Наивная теория множеств . Принстон: Ностранд. Здесь: Раздел 4
^ Многие математики ^[1] предположим, что все операции набора имеют одинаковый приоритет , и полностью используйте круглые скобки. Как и эта статья.

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

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

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

[1] Пол Р. Халмос (1968). Наивная теория множеств . Принстон: Ностранд. Здесь: Раздел 4

[2] Многие математики ^[1] предположим, что все операции набора имеют одинаковый приоритет , и полностью используйте круглые скобки. Как и эта статья.

[2]

[1]

v т и Теория множеств
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo