Симметричная разница

Элементы ровно в одном из двух наборов

В математике симметричная разность двух множеств , также известная как дизъюнктивное объединение и сумма множеств , — это набор элементов, которые находятся в любом из множеств, но не в их пересечении. Например, симметричная разность множеств и равна . ${\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-группа . Следовательно, группа, индуцированная симметричной разностью, на самом деле является векторным пространством над полем с двумя элементами Z ₂ . Если X конечно, то синглтоны образуют основу этого векторного пространства, и поэтому его размерность равна количеству элементов X . Эта конструкция используется в теории графов для определения пространства циклов графа.

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

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

Отсюда следует неравенство треугольника: ^[5] симметричная разность А и С содержится в объединении симметричной разности А и В и разности В и С.

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

${\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.}$

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

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

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

Симметричная разность коллекции множеств содержит только элементы, находящиеся в нечетном количестве множеств в коллекции: $${\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. Тейлор, Кортни (31 марта 2019 г.). «Что такое симметричная разница в математике?». МысльКо . Проверено 05 сентября 2020 г.
2. Гивант, Стивен; Халмос, Пол (2009). Введение в булеву алгебру . Springer Science & Business Media. п. 6. ISBN 978-0-387-40293-2.
3. Хамберстон, Ллойд (2011). Соединения . МТИ Пресс. п. 782. ИСБН 978-0-262-01654-4.
4. Ротман, Джозеф Дж. (2010). Продвинутая современная алгебра . Американское математическое соц. п. 19. ISBN 978-0-8218-4741-1.
5. Рудин, Уолтер (1 января 1976 г.). Принципы математического анализа (3-е изд.). Макгроу-Хилл Образование. п. 306. ИСБН 978-0070542358.
6. Клод Фламан (1963) Применение теории графов к групповой структуре , страница 16, Prentice-Hall MR 0157785

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

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