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

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

Симметричная разность множеств A и B обычно обозначается как или${\ displaystyle A \ ominus B,}$${\ Displaystyle A \ OperatorName {\ треугольник} B.}$

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

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

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

${\ 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 \ чи _ {(А \, \ треугольник \, В)} = \ чи _ {А} \ oplus \ чи _ {B}}$${\ Displaystyle [х \ в А \, \ треугольник \, В] = [х \ в А] \ oplus [х \ в В]}$

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

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

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

${\ Displaystyle А \, \ чашка \, В = (А \, \ треугольник \, В) \, \ треугольник \, (А \ крышка В)}$.

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

${\ Displaystyle {\ begin {выровненный} A \, \ треугольник \, B & = B \, \ треугольник \, A, \\ (A \, \ треугольник \, B) \, \ треугольник \, C & = A \, \ треугольник \, (В \, \ треугольник \, C). \ end {align}}}$

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

${\ Displaystyle {\ begin {align} A \, \ треугольник \, \ varnothing & = A, \\ A \, \ треугольник \, A & = \ varnothing. \ end {align}}}$

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

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

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

${\ Displaystyle (А \, \ треугольник \, В) \, \ треугольник \, (В \, \ треугольник \, С) = А \, \ треугольник \, С.}$

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

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

${\ Displaystyle А \ крышка (В \, \ треугольник \, С) = (А \ крышка В) \, \ треугольник \, (А \ крышка С),}$

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

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

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

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

${\ Displaystyle х \, \ треугольник \, Y = (х \ лор у) \ земля \ lnot (х \ земля у) = (х \ земля \ lnot у) \ лор (у \ земля \ lnot х) = х \ oplus y.}$

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

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

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

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

${\ Displaystyle \ треугольник M = \ left \ {a \ in \ bigcup M: \ left | \ {A \ in M: a \ in A \} \ right | {\ mbox {нечетное}} \ right \}}$.

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

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

${\ Displaystyle | \ треугольник M | = \ сумма _ {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 , и это максимальное расстояние для любой пары подмножеств.

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

${\ Displaystyle d _ {\ mu} (X, Y) = \ mu (X \, \ треугольник \, Y)}$

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

Если мы имеем: . Действительно, ${\ Displaystyle \ му (Х), \ му (Y) <\ infty}$${\ Displaystyle | \ му (Х) - \ му (Y) | \ Leq \ му (X \, \ треугольник \, Y)}$

${\ displaystyle {\ begin {align} | \ 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) \ \ & = \ му \ left (\ left (X \ setminus Y \ right) \ cup \ left (Y \ setminus X \ right) \ right) \\ & = \ mu \ left (X \, \ треугольник \, Y \ right) \ end {выровнен}}}$

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

Учитывая , пишут если каждому есть такое что . Отношение " " является частичным порядком в семействе подмножеств . ${\ Displaystyle {\ mathcal {D}}, {\ mathcal {E}} \ substeq {\ mathcal {A}}}$${\ Displaystyle {\ mathcal {D}} \ substeq {\ 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 \ substeq \ left [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle {\ mathcal {A}}}$

Пишем если и . Отношение " " - это отношение эквивалентности между подмножествами . ${\ displaystyle {\ mathcal {D}} = {\ mathcal {E}} \ left [{\ mathcal {A}}, \ mu \ right]}$${\ Displaystyle {\ mathcal {D}} \ substeq {\ mathcal {E}} \ left [{\ mathcal {A}}, \ mu \ right]}$${\ Displaystyle {\ mathcal {E}} \ substeq {\ 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 .
• Симметричная разность множеств . В энциклопедии математики