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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особенно, ${ 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}}}$

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

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

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

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

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

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

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

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

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

• ${ 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}$codomain, тогда ${ Displaystyle е ^ {- 1} влево (А треугольник В вправо) = е ^ {- 1} влево (А вправо) треугольник е ^ {- 1} влево (В вправо)}$.

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

${ Displaystyle х , треугольник , Y = (x lor y) land lnot (x land y) = (x land lnot y) lor (y land lnot x) = x oplus y.}$

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

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

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

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

${ 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 | треугольник М | = сумма _ {l = 1} ^ {n} (- 2) ^ {l-1} sum _ {1 leq i_ {1}$.

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

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

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

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

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

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

Если ${ Displaystyle му (X), му (Y) < infty}$, у нас есть: ${ Displaystyle | му (X) - му (Y) | Leq му (X , треугольник , Y)}$. В самом деле,

${ Displaystyle { begin {align} | му (X) - му (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]}$ если только ${ displaystyle left | mathbf {1} _ {F} - mathbf {1} _ {G} right | = 0}$ ${ displaystyle left [{ mathcal {A}}, mu right]}$ почти всюду.

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

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

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

Рекомендации

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

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