Симметричная разность

Элементы ровно в одном из двух множеств

В математике симметрическая разность двух множеств , также известная как дизъюнктивное объединение и сумма множеств , — это множество элементов, которые находятся в любом из множеств, но не в их пересечении. Например, симметрическая разность множеств и равна . ${\displaystyle \{1,2,3\}}$ ${\displaystyle \{3,4\}}$ ${\displaystyle \{1,2,4\}}$

Симметрическая разность множеств A и B обычно обозначается (альтернативно, ), , или . Ее можно рассматривать как форму сложения по модулю 2 . ${\displaystyle A\operatorname {\Delta } B}$ ${\displaystyle A\operatorname {\vartriangle } B}$ ${\displaystyle A\oplus B}$ ${\displaystyle A\ominus B}$

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

Характеристики

Диаграмма Венна ${\displaystyle ~(A\Delta B)\Delta C}$ ${\displaystyle ~\Delta ~}$ ${\displaystyle ~=~}$

Симметричная разность эквивалентна объединению обоих относительных дополнений , то есть: ^[1]

${\displaystyle A\,\Delta \,B=\left(A\setminus B\right)\cup \left(B\setminus A\right),}$

Симметричную разность можно также выразить с помощью операции XOR ⊕ над предикатами, описывающими два множества в нотации конструктора множеств :

${\displaystyle A\mathbin {\Delta } B=\{x:(x\in A)\oplus (x\in B)\}.}$

Тот же факт можно сформулировать как индикаторную функцию (обозначаемую здесь как ) симметричной разности, являющуюся XOR (или сложением по модулю 2 ) индикаторных функций ее двух аргументов: или используя обозначение скобок Айверсона . ${\displaystyle \chi }$ ${\displaystyle \chi _{(A\,\Delta \,B)}=\chi _{A}\oplus \chi _{B}}$ ${\displaystyle [x\in A\,\Delta \,B]=[x\in A]\oplus [x\in B]}$

Симметричную разность можно также выразить как объединение двух множеств за вычетом их пересечения :

${\displaystyle A\,\Delta \,B=(A\cup B)\setminus (A\cap B),}$^[1]

В частности, ; равенство в этом нестрогом включении имеет место тогда и только тогда, когда и являются непересекающимися множествами . Кроме того, обозначая и , то и всегда непересекаются, поэтому и разбиение . Следовательно, предполагая пересечение и симметрическую разность как примитивные операции, объединение двух множеств может быть хорошо определено в терминах симметрической разности правой частью равенства ${\displaystyle A\mathbin {\Delta } B\subseteq A\cup B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle D=A\mathbin {\Delta } B}$ ${\displaystyle I=A\cap B}$ ${\displaystyle D}$ ${\displaystyle I}$ ${\displaystyle D}$ ${\displaystyle I}$ ${\displaystyle A\cup B}$

${\displaystyle A\,\cup \,B=(A\,\Delta \,B)\,\Delta \,(A\cap B)}$.

Симметричная разность коммутативна и ассоциативна :

${\displaystyle {\begin{aligned}A\,\Delta \,B&=B\,\Delta \,A,\\(A\,\Delta \,B)\,\Delta \,C&=A\,\Delta \,(B\,\Delta \,C).\end{aligned}}}$

Пустое множество нейтрально , и каждое множество является своим собственным обратным :

${\displaystyle {\begin{aligned}A\,\Delta \,\varnothing &=A,\\A\,\Delta \,A&=\varnothing .\end{aligned}}}$

Таким образом, множество мощности любого множества X становится абелевой группой при операции симметрической разности. (В более общем смысле, любое поле множеств образует группу с симметрической разностью в качестве операции.) Группа, в которой каждый элемент является своим собственным обратным (или, что эквивалентно, в которой каждый элемент имеет порядок 2), иногда называется булевой группой ; ^{[2] [3]} симметрическая разность дает прототипический пример таких групп. Иногда булеву группу фактически определяют как операцию симметрической разности на множестве. ^[4] В случае, когда X имеет только два элемента, полученная таким образом группа является четверной группой Клейна .

Эквивалентно, булева группа является элементарной абелевой 2-группой . Следовательно, группа, индуцированная симметрической разностью, на самом деле является векторным пространством над полем с 2 элементами Z ₂ . Если X конечно, то синглтоны образуют базис этого векторного пространства, и его размерность , следовательно, равна числу элементов X . Эта конструкция используется в теории графов для определения пространства циклов графа.

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

${\displaystyle (A\,\Delta \,B)\,\Delta \,(B\,\Delta \,C)=A\,\Delta \,C.}$

Это подразумевает неравенство треугольника: ^[5] симметрическая разность A и C содержится в объединении симметрической разности A и B и симметрической разности B и C.

Пересечение распределяется по симметричной разности:

${\displaystyle A\cap (B\,\Delta \,C)=(A\cap B)\,\Delta \,(A\cap C),}$

и это показывает, что множество степеней X становится кольцом , с симметричной разностью как сложение и пересечением как умножение. Это прототипический пример булевого кольца .

Дополнительные свойства симметричной разности включают в себя:

• ${\displaystyle A\mathbin {\Delta } B=\emptyset }$тогда и только тогда, когда . ${\displaystyle A=B}$
• ${\displaystyle A\mathbin {\Delta } B=A^{c}\mathbin {\Delta } B^{c}}$, где , является дополнением , дополнением , соответственно, относительно любого (фиксированного) множества, содержащего оба. ${\displaystyle A^{c}}$ ${\displaystyle B^{c}}$ ${\displaystyle A}$ ${\displaystyle B}$
• ${\displaystyle \left(\bigcup _{\alpha \in {\mathcal {I}}}A_{\alpha }\right)\Delta \left(\bigcup _{\alpha \in {\mathcal {I}}}B_{\alpha }\right)\subseteq \bigcup _{\alpha \in {\mathcal {I}}}\left(A_{\alpha }\mathbin {\Delta } B_{\alpha }\right)}$, где — произвольный непустой набор индексов. ${\displaystyle {\mathcal {I}}}$
• Если — любая функция и — любые множества в области значений , то ${\displaystyle f:S\rightarrow T}$ ${\displaystyle A,B\subseteq T}$ ${\displaystyle f}$ ${\displaystyle f^{-1}\left(A\mathbin {\Delta } B\right)=f^{-1}\left(A\right)\mathbin {\Delta } f^{-1}\left(B\right).}$

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

${\displaystyle x\,\Delta \,y=(x\lor y)\land \lnot (x\land y)=(x\land \lnot y)\lor (y\land \lnot x)=x\oplus y.}$

Эта операция имеет те же свойства, что и симметричная разность множеств.

н-арная симметричная разность

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

Симметричная разность набора множеств содержит только элементы, которые находятся в нечетном числе множеств в наборе: $${\displaystyle \Delta M=\left\{a\in \bigcup M:\left|\{A\in M:a\in A\}\right|{\text{ is odd}}\right\}.}$$

Очевидно, это хорошо определено только тогда, когда каждый элемент объединения вносится конечным числом элементов . ${\textstyle \bigcup M}$ ${\displaystyle M}$

Предположим, что есть мультимножество и . Тогда существует формула для , количества элементов в , заданная исключительно в терминах пересечений элементов : ${\displaystyle M=\left\{M_{1},M_{2},\ldots ,M_{n}\right\}}$ ${\displaystyle n\geq 2}$ ${\displaystyle |\Delta M|}$ ${\displaystyle \Delta M}$ ${\displaystyle M}$ $${\displaystyle |\Delta M|=\sum _{l=1}^{n}(-2)^{l-1}\sum _{1\leq i_{1}<i_{2}<\ldots <i_{l}\leq n}\left|M_{i_{1}}\cap M_{i_{2}}\cap \ldots \cap M_{i_{l}}\right|.}$$

Симметричная разность на мерных пространствах

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

Сначала рассмотрим конечное множество S и счетную меру на подмножествах, заданную их размером. Теперь рассмотрим два подмножества S и установим их расстояние друг от друга как размер их симметрической разности. Это расстояние на самом деле является метрикой , которая делает множество мощности на S метрическим пространством . Если S имеет n элементов, то расстояние от пустого множества до S равно n , и это максимальное расстояние для любой пары подмножеств. ^[6]

Используя идеи теории меры , разделение измеримых множеств можно определить как меру их симметрической разности. Если μ — σ-конечная мера , определенная на σ-алгебре Σ, то функция

${\displaystyle d_{\mu }(X,Y)=\mu (X\,\Delta \,Y)}$

является псевдометрикой на Σ. d _μ становится метрикой , если Σ рассматривается по модулю отношения эквивалентности X ~ Y тогда и только тогда, когда . Иногда ее называют метрикой Фреше - Никодима . Полученное метрическое пространство сепарабельно тогда и только тогда, когда L 2 (μ) сепарабельно. ${\displaystyle \mu (X\,\Delta \,Y)=0}$

Если , то имеем: . Действительно, ${\displaystyle \mu (X),\mu (Y)<\infty }$ ${\displaystyle |\mu (X)-\mu (Y)|\leq \mu (X\,\Delta \,Y)}$

${\displaystyle {\begin{aligned}|\mu (X)-\mu (Y)|&=\left|\left(\mu \left(X\setminus Y\right)+\mu \left(X\cap Y\right)\right)-\left(\mu \left(X\cap Y\right)+\mu \left(Y\setminus X\right)\right)\right|\\&=\left|\mu \left(X\setminus Y\right)-\mu \left(Y\setminus X\right)\right|\\&\leq \left|\mu \left(X\setminus Y\right)\right|+\left|\mu \left(Y\setminus X\right)\right|\\&=\mu \left(X\setminus Y\right)+\mu \left(Y\setminus X\right)\\&=\mu \left(\left(X\setminus Y\right)\cup \left(Y\setminus X\right)\right)\\&=\mu \left(X\,\Delta \,Y\right)\end{aligned}}}$

Если — пространство с мерой и — измеримые множества, то их симметрическая разность также измерима: . Можно определить отношение эквивалентности на измеримых множествах, положив и связанными, если . Это отношение обозначается . ${\displaystyle S=\left(\Omega ,{\mathcal {A}},\mu \right)}$ ${\displaystyle F,G\in {\mathcal {A}}}$ ${\displaystyle F\Delta G\in {\mathcal {A}}}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle \mu \left(F\Delta G\right)=0}$ ${\displaystyle F=G\left[{\mathcal {A}},\mu \right]}$

При условии , записывается , если для каждого существует такое , что . Отношение " " является частичным порядком на семействе подмножеств . ${\displaystyle {\mathcal {D}},{\mathcal {E}}\subseteq {\mathcal {A}}}$ ${\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left[{\mathcal {A}},\mu \right]}$ ${\displaystyle D\in {\mathcal {D}}}$ ${\displaystyle E\in {\mathcal {E}}}$ ${\displaystyle D=E\left[{\mathcal {A}},\mu \right]}$ ${\displaystyle \subseteq \left[{\mathcal {A}},\mu \right]}$ ${\displaystyle {\mathcal {A}}}$

Запишем , если и . Отношение " " является отношением эквивалентности между подмножествами . ${\displaystyle {\mathcal {D}}={\mathcal {E}}\left[{\mathcal {A}},\mu \right]}$ ${\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left[{\mathcal {A}},\mu \right]}$ ${\displaystyle {\mathcal {E}}\subseteq {\mathcal {D}}\left[{\mathcal {A}},\mu \right]}$ ${\displaystyle =\left[{\mathcal {A}},\mu \right]}$ ${\displaystyle {\mathcal {A}}}$

Симметричное замыкание — это совокупность всех -измеримых множеств, которые являются некоторыми . Симметричное замыкание содержит . Если — подалгебра , то симметричное замыкание — . ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle =\left[{\mathcal {A}},\mu \right]}$ ${\displaystyle D\in {\mathcal {D}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle \sigma }$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {D}}}$

${\displaystyle F=G\left[{\mathcal {A}},\mu \right]}$если почти везде . ${\displaystyle \left|\mathbf {1} _{F}-\mathbf {1} _{G}\right|=0}$ ${\displaystyle \left[{\mathcal {A}},\mu \right]}$

Расстояние Хаусдорфа против симметричной разности

Расстояние Хаусдорфа и (площадь) симметричной разности являются псевдометриками на множестве измеримых геометрических фигур. Однако они ведут себя совершенно по-разному. На рисунке справа показаны две последовательности фигур: «Красный» и «Красный ∪ Зеленый». Когда расстояние Хаусдорфа между ними становится меньше, площадь симметричной разности между ними становится больше, и наоборот. Продолжая эти последовательности в обоих направлениях, можно получить две последовательности, такие, что расстояние Хаусдорфа между ними сходится к 0, а симметричное расстояние между ними расходится, или наоборот.

Смотрите также

• Алгебра множеств
• Булева функция
• Дополнение (теория множеств)
• Разница (теория множеств)
• Эксклюзивный или
• Нечеткий набор
• Пересечение (теория множеств)
• индекс Жаккара
• Список установленных тождеств и отношений
• Логический граф
• Разделимые сигма-алгебры
• Теория множеств
• Симметрия
• Объединение (теория множеств)
• принцип включения–исключения

Ссылки

1. Taylor, Courtney (31 марта 2019 г.). «Что такое симметричная разность в математике?». ThoughtCo . Получено 05.09.2020 .
2. Givant, Steven; Halmos, Paul (2009). Введение в булевы алгебры . Springer Science & Business Media. стр. 6. ISBN 978-0-387-40293-2.
3. Хамберстоун, Ллойд (2011). Связующие . MIT Press. стр. 782. ISBN 978-0-262-01654-4.
4. Ротман, Джозеф Дж. (2010). Advanced Modern Algebra . Американское математическое общество. стр. 19. ISBN 978-0-8218-4741-1.
5. Рудин, Уолтер (1 января 1976 г.). Принципы математического анализа (3-е изд.). McGraw-Hill Education. стр. 306. ISBN 978-0070542358.
6. Клод Фламан (1963) Приложения теории графов к структуре групп , стр. 16, Prentice-Hall MR 0157785

Библиография

• Халмош, Пол Р. (1960). Наивная теория множеств . Университетская серия по математике для студентов. Компания van Nostrand. Zbl  0087.04403.
• Симметрическая разность множеств. В Энциклопедии математики