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

Диаграмма Венна из ${\displaystyle A\triangle B}$. Симметричная разница - это союз без в пересечение: ${\displaystyle ~\setminus ~}$ ${\displaystyle ~=~}$

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

Симметричная разность множеств А и B обычно обозначается как ${\displaystyle A\,\triangle \,B,}$ или же ${\displaystyle A\ominus B}$ или же ${\displaystyle A\oplus B.}$^[1][2][3]

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

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

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

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

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

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

${\displaystyle A\,\triangle \,B=\{x:(x\in A)\oplus (x\in B)\}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К другим свойствам симметричной разницы относятся:

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

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

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

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

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

Повторяющаяся симметричная разность в некотором смысле эквивалентна операции над мультимножество наборов, дающих набор элементов, которые находятся в нечетном количестве наборов.^{[требуется разъяснение ]}

Как и выше, симметричная разность набора наборов содержит только элементы, которые находятся в нечетном количестве наборов в коллекции:

${\displaystyle \triangle M=\left\{a\in \bigcup M:\left|\{A\in M:a\in A\}\right|{\mbox{ is odd}}\right\}}$.

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

Предполагать ${\displaystyle M=\left\{M_{1},M_{2},\ldots ,M_{n}\right\}}$ это мультимножество и ${\displaystyle n\geq 2}$. Тогда есть формула для ${\displaystyle |\triangle M|}$, количество элементов в ${\displaystyle \triangle M}$, заданные исключительно в терминах пересечений элементов ${\displaystyle M}$:

${\displaystyle |\triangle 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 имеет п элементов, то расстояние от пустой набор к S является п, и это максимальное расстояние для любой пары подмножеств.^[8]

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

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

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

Если ${\displaystyle \mu (X),\mu (Y)<\infty }$, у нас есть: ${\displaystyle |\mu (X)-\mu (Y)|\leq \mu (X\,\triangle \,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\,\triangle \,Y\right)\end{aligned}}}$

Если ${\displaystyle S=\left(\Omega ,{\mathcal {A}},\mu \right)}$ пространство меры и ${\displaystyle F,G\in {\mathcal {A}}}$ являются измеримыми множествами, то измерима и их симметричная разность: ${\displaystyle F\triangle G\in {\mathcal {A}}}$. Можно определить отношение эквивалентности на измеримых множествах, положив ${\displaystyle F}$ и ${\displaystyle G}$ быть связанным, если ${\displaystyle \mu \left(F\triangle 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. «Исчерпывающий список символов теории множеств». Математическое хранилище. 2020-04-11. Получено 2020-09-05.
2. Тейлор, Кортни (31 марта 2019 г.). "Что такое симметричная разница в математике?". ThoughtCo. Получено 2020-09-05.
3. Вайсштейн, Эрик В. «Симметричная разница». mathworld.wolfram.com. Получено 2020-09-05.
4. Гивант, Стивен; Халмос, Пол (2009). Введение в булевы алгебры. Springer Science & Business Media. п. 6. ISBN  978-0-387-40293-2.
5. Хамберстон, Ллойд (2011). Связки. MIT Press. п.782. ISBN  978-0-262-01654-4.
6. Ротман, Джозеф Дж. (2010). Продвинутая современная алгебра. American Mathematical Soc. п. 19. ISBN  978-0-8218-4741-1.
7. Рудин, Вальтер (1 января 1976 г.). Принципы математического анализа (3-е изд.). McGraw-Hill Education. п.306. ISBN  978-0070542358.
8. Клод Фламент (1963) Приложения теории графов к структуре группы, стр. 16, Prentice-Hall МИСТЕР0157785

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

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