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

Диаграмма Венна из . Симметрично отличием является объединением без на пересечении :${\ Displaystyle A \ треугольник B}$ ${\ Displaystyle ~ \ setminus ~}$ ${\ Displaystyle ~ = ~}$

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

Симметричная разность наборов A и B обычно обозначается или ^{[1] [2] [3] [ необходим лучший источник ]}${\ displaystyle A \ ominus B,}$${\ Displaystyle A \ OperatorName {\ треугольник} B.}$

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

Свойства [ править ]

Диаграмма Венна ${\ Displaystyle ~ А \ треугольник В \ треугольник С}$ ${\ Displaystyle ~ \ треугольник ~}$ ${\ Displaystyle ~ = ~}$

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

${\ Displaystyle А \, \ треугольник \, В = \ влево (А \ setminus B \ right) \ чашка \ влево (B \ setminus A \ right),}$

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

${\ Displaystyle A \, \ треугольник \, B = \ {x: (x \ in A) \ oplus (x \ in B) \}.}$

Тот же факт может быть заявлен как индикаторная функция (обозначенная здесь ) симметричной разности, являющаяся XOR (или сложением по модулю 2 ) индикаторных функций двух ее аргументов: или с использованием обозначения скобок Айверсона .${\displaystyle \chi }$${\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}}}$

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

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

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

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

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

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

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

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

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

• ${\displaystyle A\triangle B=\emptyset }$если и только если .${\displaystyle A=B}$
• ${\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}$${\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.}$

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

n -арная симметричная разность [ править ]

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

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

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

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

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

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

Если мы имеем: . В самом деле,${\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]}$iff почти везде .${\displaystyle \left|\mathbf {1} _{F}-\mathbf {1} _{G}\right|=0}$ ${\displaystyle \left[{\mathcal {A}},\mu \right]}$

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

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

См. Также [ править ]

Ссылки [ править ]

Библиография [ править ]

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