Różnica symetryczna - Symmetric difference

W matematyce The symetryczne różnice z dwóch zestawów , znane również jako rozłącznego jedności , jest zestawem elementów, które są w każdym z odbiorników, a nie na ich przecięciu. Na przykład symetryczna różnica zbiorów i jest . ${\ Displaystyle \ {1,2,3 \}}$${\ Displaystyle \ {3,4\}}$${\ Displaystyle \ {1,2,4 \}}$

Symetryczna różnica zbiorów A i B jest powszechnie oznaczana przez lub${\ Displaystyle A \ ominus B}$${\ Displaystyle A \ nazwa operatora {\ trójkąt} B.}$

Zestaw moc każdego przewodu staje się grupa przemienna ramach operacji różnicy symetrycznej, z pustego zestawu jako element neutralny grupy i każdego elementu w tej grupy jest jej własny odwrotny . Zbiór potęgowy dowolnego zbioru staje się pierścieniem logicznym , z symetryczną różnicą jako dodaniem pierścienia i przecięciem jako pomnożeniem pierścienia.

Nieruchomości

Symetryczna różnica jest równoważna połączeniu obu względnych dopełnień , czyli:

${\ Displaystyle A \, \ trójkąt \ B = \ lewo (A \ setminus B \ po prawej) \ filiżanka \ po lewej (B \ setminus A \ po prawej),}$

Symetryczną różnicę można również wyrazić za pomocą operacji XOR ⊕ na predykatach opisujących dwa zbiory w notacji konstruktora zbiorów :

${\ Displaystyle A \ \ trójkąt \ B = \ {x: (x \ w A) \ oplus (x \ w B) \}.}$

Ten sam fakt można określić jako funkcję wskaźnikową (oznaczoną tutaj przez ) różnicy symetrycznej, będącą XOR (lub addycją mod 2 ) funkcji wskaźnikowych jej dwóch argumentów: lub używając notacji nawiasów Iversona . ${\ Displaystyle \ chi}$${\ Displaystyle \ chi _ {(A \ \ trójkąt \ B)} = \ chi _ {A} \ oplus \ chi _ {B}}$${\ Displaystyle [x \ w A \, \ trójkąt \, B] = [x \ w A] \ oplus [x \ w B]}$

Symetryczną różnicę można również wyrazić jako sumę dwóch zbiorów minus ich przecięcie :

${\ Displaystyle A \, \ trójkąt \, B = (A \ filiżanka B) \ setminus (A \ czapka B),}$

W szczególności ; równość w tym nieścisłym włączeniu występuje wtedy i tylko wtedy, gdy i są zbiorami rozłącznymi . Ponadto oznaczające i , wtedy i są zawsze rozłączne, więc i partycja . W konsekwencji, zakładając przecięcie i różnicę symetryczną jako operacje pierwotne, połączenie dwóch zbiorów może być dobrze zdefiniowane pod względem różnicy symetrycznej po prawej stronie równości ${\ Displaystyle A \ trójkąt B \ podseteq A \ filiżanka B}$ ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle D = A \ trójkąt B}$${\ Displaystyle I = A \ czapka B}$${\ Displaystyle D}$${\ Displaystyle I}$${\ Displaystyle D}$${\ Displaystyle I}$ ${\ Displaystyle A \ filiżanka B}$

${\ Displaystyle A \ \ filiżanka \ B = (A \ \ trójkąt \ B) \ \ trójkąt \ (A \ czapka B)}$.

Symetryczna różnica jest przemienna i asocjacyjna :

${\ Displaystyle {\ zacząć {wyrównany} A \ \ trójkąt \ B & = B \ \ trójkąt \ A \ \ (A \ \ trójkąt \ B) \ \ trójkąt \ C & = A \, \triangle \,(B\,\triangle \,C).\end{aligned}}}$

Zbiór pusty jest neutralny , a każdy zbiór jest swoim własnym odwrotny:

${\ Displaystyle {\ zacząć {wyrównany} A \, \ trójkąt \ \ \ varnothing = A \ \ A \ \ trójkąt \ A & = \ varnothing \ koniec {wyrównany}}}$

W ten sposób zbiór potęgowy dowolnego zbioru X staje się grupą abelową w operacji symetrycznej różnicy. (Bardziej ogólnie, każde pole zbiorów tworzy grupę z symetryczną różnicą jako operacją.) Grupa, w której każdy element jest swoją własną odwrotnością (lub równoważnie, w której każdy element ma porządek 2) jest czasami nazywana grupą Boole'a ; symetryczna różnica stanowi prototypowy przykład takich grup. Czasami grupa Boole'a jest faktycznie definiowana jako operacja symetrycznej różnicy na zbiorze. W przypadku, gdy X ma tylko dwa elementy, otrzymaną w ten sposób grupą jest czterogrupa Kleina .

Równoważnie grupa Boole'a jest elementarną grupą abelową . W konsekwencji grupa indukowana przez różnicę symetryczną jest w rzeczywistości przestrzenią wektorową nad polem z 2 elementami Z ₂ . Jeżeli X jest skończone, to singletony tworzą bazę tej przestrzeni wektorowej, a jej wymiar jest więc równy liczbie elementów X . Ta konstrukcja jest stosowana w teorii grafów do określenia przestrzeni cyklicznej grafu.

Z własności odwrotności w grupie Boole'a wynika, że ​​symetryczna różnica dwóch powtórzonych różnic symetrycznych jest równoważna powtórzonej symetrycznej różnicy złączenia dwóch multizbiorów, gdzie dla każdego podwójnego zbioru można usunąć oba. W szczególności:

${\ Displaystyle (A \ \ trójkąt \ B) \ \ trójkąt \ (B \ \ trójkąt \ C) = A \ \ trójkąt \ C.}$

To implikuje nierówność trójkąta: symetryczna różnica A i C jest zawarta w połączeniu symetrycznej różnicy A i B oraz B i C .

Przecięcie rozkłada się na różnicę symetryczną:

${\ Displaystyle A \ czapka (B \, \ trójkąt \, C) = (A \ czapka B) \, \ trójkąt \, (A \ czapka C),}$

a to pokazuje, że zbiór potęg X staje się pierścieniem , z symetryczną różnicą jako dodawaniem i przecięciem jako mnożeniem. To jest prototypowy przykład pierścienia Boole'a .

Dalsze właściwości różnicy symetrycznej obejmują:

• ${\displaystyle A\trójkąt B=\pusty zestaw}$wtedy i tylko wtedy, gdy .${\ Displaystyle A = B}$
• ${\ Displaystyle A \ trójkąt B = A ^ {c} \ trójkąt B ^ {c}}$Gdzie , to jest uzupełnienie, jest dopełnieniem, odpowiednio, w odniesieniu do każdego zestawu (stałe), który zawiera zarówno.${\ Displaystyle A ^ {c}}$${\ Displaystyle B ^ {c}}$${\ Displaystyle A}$${\ Displaystyle B}$
• ${\ Displaystyle \ lewo (\ bigcup _ {\ alfa \ w {\ mathcal {ja}}} A_ {\ alfa} \ prawej) \ trójkąt \ lewo (\ bigcup _ {\ alfa \ w {\ mathcal {ja}} }B_{\alpha }\right)\subseteq \bigcup _{\alpha \in {\mathcal {I}}}\left(A_{\alpha }\triangle B_{\alpha }\right)}$, gdzie jest dowolnym niepustym zestawem indeksów.${\displaystyle {\mathcal {I}}}$
• Jeśli jest dowolną funkcją i są dowolnymi zestawami w kodziedzinie , to${\displaystyle f:S\rightarrow T}$${\displaystyle A,B\subseteq T}$${\displaystyle f}$${\ Displaystyle f ^ {-1} \ po lewej (A \ trójkąt B \ po prawej) = f ^ {-1} \ po lewej (A \ po prawej) \ trójkąt f ^ {-1} \ po lewej (B \ po prawej).}$

Symetryczną różnicę można zdefiniować w dowolnej algebrze Boole'a , pisząc

${\ Displaystyle x \, \ trójkąt \, y = (x \ lor y) \ ziemia \ nie (x \ ziemia y) = (x \ ziemia \ nie y) \ lor (y \ ziemia \ nie x) = x \ plus y.}$

Ta operacja ma takie same właściwości jak symetryczna różnica zbiorów.

n -aryczna różnica symetryczna

Powtarzające się różnica symetryczna jest w ekwiwalencie sens operacji na MultiSet zestawów dających zbiór elementów, które są w nieparzystej liczby zestawów.

Jak wyżej, symetryczna różnica zbioru zbiorów zawiera tylko elementy, które są w nieparzystej liczbie zbiorów w zbiorze:

${\ Displaystyle \ trójkąt M = \ lewo \ {a \ w \ bigcup M: \ lewo | \ {A \ w M: a \ w A \} \ po prawej | {\ mbox {jest dziwny}} \ po prawej \}}$.

Najwyraźniej jest to dobrze zdefiniowane tylko wtedy, gdy do każdego elementu unii przyczynia się skończona liczba elementów . ${\ Displaystyle \ bigcup M}$${\ Displaystyle M}$

Załóżmy, że jest to multiset i . Następnie istnieje wzór na , liczba elementów w , podana wyłącznie jako przecięcia elementów : ${\ Displaystyle M = \ lewo \ {M_ {1}, M_ {2}, \ ldots, M_ {n} \ prawo \}}$${\displaystyle n\geq 2}$${\displaystyle |\trójkąt M|}$${\ Displaystyle \ trójkąt M}$${\ Displaystyle M}$

${\ Displaystyle | \ trójkąt M | = \ suma _ {l = 1} ^ {n} (-2) ^ {l-1} \ suma _ {1 \ równoważnik i_ {1} <i_ {2} < \ ldots <i_{l}\leq n}\left|M_{i_{1}}\cap M_{i_{2}}\cap \ldots \cap M_{i_{l}}\right|}$.

Symetryczna różnica w przestrzeniach miar

Dopóki istnieje pojęcie „jak duży” jest zbiór, symetryczną różnicę między dwoma zestawami można uznać za miarę tego, jak „daleko się od siebie” znajdują.

Najpierw rozważmy zbiór skończony S i miarę obliczeniową na podzbiorach podaną przez ich rozmiar. Rozważmy teraz dwa podzbiory S i ustaw ich odległość jako wielkość ich symetrycznej różnicy. Odległość ta jest w rzeczywistości metryką , co sprawia, że moc ustawiona na S jest przestrzenią metryczną . Jeśli S ma n elementów, to odległość od pustego zbioru do S wynosi n i jest to maksymalna odległość dla dowolnej pary podzbiorów.

Wykorzystując idee teorii miary , oddzielenie zbiorów mierzalnych można zdefiniować jako miarę ich symetrycznej różnicy. Jeżeli μ jest miarą σ-skończoną określoną w σ-algebrze Σ, funkcja

${\ Displaystyle d_ {\ mu} (X, Y) = \ mu (X \ \ trójkąt \ Y)}$

to pseudometryka na Σ. d _μ staje się metryką, jeśli Σ jest uważane za modulo relacji równoważności X ~ Y wtedy i tylko wtedy, gdy . Czasami nazywa się to metryką Fréchet - Nikodym . Wynikowa przestrzeń metryczna jest rozdzielna wtedy i tylko wtedy, gdy L ² (μ) jest rozdzielne. ${\ Displaystyle \ mu (X \ \ trójkąt \ Y) = 0}$

Jeśli , mamy: . W rzeczy samej, ${\ Displaystyle \ mu (X), \ mu (Y) <\ infty}$${\ Displaystyle | \ mu (X) - \ mu (Y) | \ leq \ mu (X \ \ trójkąt \ Y)}$

${\ Displaystyle {\ zacząć {wyrównany} | \ mu (X) - \ mu (Y) | i = \ lewo | \ lewo (\ mu \ lewo (X \ setminus Y \ po prawej) + \ mu \ lewo (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\,\trójkąt \,Y \right)\end{wyrównany}}}$

Jeżeli jest przestrzenią miary i są zbiorami mierzalnymi, to mierzalna jest również ich symetryczna różnica: . Relację równoważności można zdefiniować na zbiorach mierzalnych przez przyzwolenie i powiązanie jeśli . Ta relacja jest oznaczona . ${\ Displaystyle S = \ lewo (\ Omega, {\ mathcal {A}}, \ mu \ prawej)}$${\ Displaystyle F, G \ w {\ Mathcal {A}}}$${\ Displaystyle F \ trójkąt G \ w {\ mathcal {A}}}$${\ Displaystyle F}$${\ Displaystyle G}$${\ Displaystyle \ mu \ lewo (F \ trójkąt G \ prawy) = 0}$${\ Displaystyle F = G \ lewo [{\ mathcal {A}} \ mu \ prawo]}$

Biorąc pod uwagę , pisze się, czy do każdego jest takie, że . Relacja " " jest porządkiem częściowym w rodzinie podzbiorów . ${\ Displaystyle {\ mathcal {D}}, {\ mathcal {E}} \ subseteq {\ mathcal {A}}}$${\ Displaystyle {\ mathcal {D}} \ subseteq {\ mathcal {E}} \ lewo [{\ mathcal {A}}, \ mu \ prawej]}$${\ Displaystyle D \ w {\ Mathcal {D}}}$${\ Displaystyle E \ w {\ Mathcal {E}}}$${\ Displaystyle D = E \ lewo [{\ matematyka {A}} \ mu \ prawo]}$${\ Displaystyle \ subseteq \ lewo [{\ mathcal {A}} \ mu \ prawo]}$${\ Displaystyle {\ Mathcal {A}}}$

Piszemy jeśli i . Relacja „ ” jest relacją równoważności między podzbiorami . ${\ Displaystyle {\ mathcal {D}} = {\ mathcal {E}} \ lewo [{\ mathcal {A}} \ mu \ prawej]}$${\ Displaystyle {\ mathcal {D}} \ subseteq {\ mathcal {E}} \ lewo [{\ mathcal {A}}, \ mu \ prawej]}$${\ Displaystyle {\ mathcal {e}} \ subseteq {\ mathcal {D}} \ lewo [{\ mathcal {A}}, \ mu \ prawej]}$${\ Displaystyle = \ lewo [{\ mathcal {A}}, \ mu \ prawo]}$${\ Displaystyle {\ Mathcal {A}}}$

Symetryczny zamknięcie stanowi to zbiór wszystkich -measurable zestawów, które są dla niektórych . Symetryczne zamknięcie zawiera . If jest pod- algebrą , podobnie jak domknięcie symetryczne . ${\displaystyle {\mathcal {D}}}$${\ Displaystyle {\ Mathcal {A}}}$${\ Displaystyle = \ lewo [{\ mathcal {A}}, \ mu \ prawo]}$${\ Displaystyle D \ w {\ Mathcal {D}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle \sigma}$${\ Displaystyle {\ Mathcal {A}}}$${\displaystyle {\mathcal {D}}}$

${\ Displaystyle F = G \ lewo [{\ mathcal {A}} \ mu \ prawo]}$jeśli prawie wszędzie . ${\ Displaystyle \ lewo | \ mathbf {1} _ {F} - \ mathbf {1} _ {G} \ po prawej | = 0}$ ${\ Displaystyle \ lewo [{\ mathcal {A}}, \ mu \ prawo]}$

Odległość Hausdorffa a różnica symetryczna

Odległość Hausdorff i (obszar) różnicy symetrycznej są zarówno pseudo-metryki zestawu mierzalnych kształtów geometrycznych. Zachowują się jednak zupełnie inaczej. Rysunek po prawej pokazuje dwie sekwencje kształtów, „Czerwony” i „Czerwony ∪ Zielony”. Gdy odległość Hausdorffa między nimi zmniejsza się, obszar symetrycznej różnicy między nimi staje się większy i odwrotnie. Kontynuując te sekwencje w obu kierunkach, można uzyskać dwie sekwencje takie, że odległość Hausdorffa między nimi zbiega się do 0, a odległość symetryczna między nimi jest rozbieżna lub odwrotnie.

Zobacz też

Bibliografia

Bibliografia

• Halmos, Paul R. (1960). Teoria zbiorów naiwnych . Seria uniwersytecka w matematyce licencjackiej. Firma van Nostrand. Zbl  0087.04403 .
• Symetryczna różnica zbiorów . W Encyklopedii Matematyki