Symmetrisk forskjell - Symmetric difference

I matematikk er den symmetriske forskjellen mellom to sett , også kjent som den disjunktive foreningen , settet med elementer som er i et av settene, men ikke i krysset. For eksempel den symmetriske forskjellen mellom settene og er . ${\ displaystyle \ {1,2,3 \}}$${\ displaystyle \ {3,4 \}}$${\ displaystyle \ {1,2,4 \}}$

Den symmetriske forskjellen mellom settene A og B er vanligvis betegnet med eller${\ displaystyle A \ ominus B,}$${\ displaystyle A \ operatorname {\ triangle} B.}$

Den kraft sett av et sett blir en abelsk gruppe under drift av symmetriske forskjell, med det tomme settet som det nøytrale element av gruppen og hvert element i denne gruppe er sin egen inverse . Kraftsettet til ethvert sett blir en boolsk ring , med symmetrisk forskjell som tillegg av ringen og kryss som multiplikasjon av ringen.

Egenskaper

Den symmetriske forskjellen tilsvarer foreningen av begge relative komplementene , det vil si:

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

Den symmetriske forskjellen kan også uttrykkes ved bruk av XOR- operasjonen ⊕ på predikatene som beskriver de to settene i set-builder-notasjon :

${\ displaystyle A \, \ triangel \, B = \ {x: (x \ i A) \ oplus (x \ i B) \}.}$

Det samme faktum kan angis som den indikator funksjon (angitt her ved ) av den symmetriske forskjell, blir den XOR (eller tilsetning mod 2 ) av indikator funksjoner av sine to argumenter: eller ved hjelp av Iverson braketten notasjon . ${\ displaystyle \ chi}$${\ displaystyle \ chi _ {(A \, \ triangel \, B)} = \ chi _ {A} \ oplus \ chi _ {B}}$${\ displaystyle [x \ i A \, \ triangel \, B] = [x \ i A] \ oplus [x \ i B]}$

Den symmetriske forskjellen kan også uttrykkes som foreningen av de to settene, minus deres skjæringspunkt :

${\ displaystyle A \, \ triangel \, B = (A \ cup B) \ setminus (A \ cap B),}$

Spesielt ; likestillingen i denne ikke-strenge inkluderingen skjer hvis og bare hvis og er usammenhengende sett . Videre angir og , da og er alltid usammenhengende, så og partisjon . Ved å anta kryss og symmetrisk forskjell som primitive operasjoner, kan foreningen av to sett være godt definert når det gjelder symmetrisk forskjell på høyre side av likestillingen ${\ displaystyle A \ triangel B \ subseteq A \ cup B}$ ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle D = A \ triangel B}$${\ displaystyle I = A \ cap B}$${\ displaystyle D}$${\ displaystyle I}$${\ displaystyle D}$${\ displaystyle I}$ ${\ displaystyle A \ cup B}$

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

Den symmetriske forskjellen er kommutativ og assosiativ :

${\ displaystyle {\ begynne {justert} A \, \ trekant \, B & = B \, \ trekant \, A, \\ (A \, \ trekant \, B) \, \ trekant \, C & = A \, \ trekant \, (B \, \ trekant \, C). \ ende {justert}}}$

Det tomme settet er nøytralt , og hvert sett er sitt eget omvendte:

${\ displaystyle {\ begynne {justert} A \, \ trekant \, \ varnothing & = A, \\ A \, \ triangel \, A & = \ varnothing. \ end {justert}}}$

Dermed blir innstilt effekt av et sett X blir en abelsk gruppe under symmetriske forskjell operasjonen. (Mer generelt danner alle sett med grupper en gruppe med den symmetriske forskjellen som operasjon.) En gruppe der hvert element er sitt eget inverse (eller, tilsvarende, der hvert element har rekkefølge 2) noen ganger kalles en boolsk gruppe ; den symmetriske forskjellen gir et prototypisk eksempel på slike grupper. Noen ganger er den boolske gruppen faktisk definert som den symmetriske differensoperasjonen på et sett. I tilfellet der X bare har to elementer, er den således oppnådde gruppen Klein-fire-gruppen .

Tilsvarende er en boolsk gruppe en elementær abelsk 2-gruppe . Følgelig er gruppen indusert av den symmetriske forskjellen faktisk et vektorrom over feltet med 2 elementer Z ₂ . Hvis X er begrenset, da de enkelts danner en basis av denne vektorrommet, og dens dimensjon er derfor lik antallet av elementer i X . Denne konstruksjonen brukes i grafteori for å definere syklusrommet til en graf.

Fra egenskapen til inversene i en boolsk gruppe følger det at den symmetriske forskjellen på to gjentatte symmetriske forskjeller tilsvarer den gjentatte symmetriske forskjellen på sammenføyningen til de to multisettet, hvor begge dobbeltsett kan fjernes for hvert dobbeltsett. Spesielt:

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

Dette innebærer trekant ulikheten: den symmetriske forskjell fra A og C er inneholdt i foreningen av den symmetriske forskjell fra A og B og som i B og C .

Krysset fordeler seg over symmetrisk forskjell:

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

og dette viser at kraftsettet til X blir en ring , med symmetrisk forskjell som tillegg og kryss som multiplikasjon. Dette er det prototypiske eksemplet på en boolsk ring .

Ytterligere egenskaper ved den symmetriske forskjellen inkluderer:

• ${\ displaystyle A \ triangel B = \ emptyset}$hvis og bare hvis .${\ displaystyle A = B}$
• ${\ displaystyle A \ triangel B = A^{c} \ trekant B^{c}}$Der , er komplement, komplement, henholdsvis, i forhold til hvilken som helst (fast) sett som inneholder begge deler.${\ displaystyle A^{c}}$${\ displaystyle B^{c}}$${\ displaystyle A}$${\ displaystyle B}$
• ${\ displaystyle \ left (\ bigcup _ {\ alpha \ in {\ mathcal {I}}} A _ {\ alpha} \ right) \ triangel \ venstre (\ bigcup _ {\ alpha \ i {\ mathcal {I}} } B _ {\ alpha} \ høyre) \ subseteq \ bigcup _ {\ alpha \ i {\ mathcal {I}}} \ venstre (A _ {\ alpha} \ trekant B _ {\ alpha} \ høyre)}$, hvor er et vilkårlig ikke-tomt indekssett.${\ displaystyle {\ mathcal {I}}}$
• Hvis er en funksjon og er noen sett i kodedomenet, så${\ displaystyle f: S \ høyre pil T}$${\ displaystyle A, B \ subseteq T}$${\ displaystyle f}$${\ displaystyle f^{-1} \ venstre (A \ trekant B \ høyre) = f^{-1} \ venstre (A \ høyre) \ trekant f^{-1} \ venstre (B \ høyre).}$

Den symmetriske forskjellen kan defineres i hvilken som helst boolsk algebra , ved å skrive

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

Denne operasjonen har de samme egenskapene som den symmetriske forskjellen mellom sett.

n -ary symmetrisk forskjell

Den gjentatte symmetrisk forskjell er på en måte som tilsvarer en operasjon på en multiset av settene som gir sett av elementer som er i et odde antall sett.

Som ovenfor inneholder den symmetriske forskjellen til en samling sett bare elementer som er i et oddetall av settene i samlingen:

${\ displaystyle \ triangel M = \ venstre \ {a \ i \ bigcup M: \ venstre | \ {A \ i M: a \ i A \} \ høyre | {\ mbox {er odd}} \ høyre \}}$.

Tydeligvis er dette veldefinert bare når hvert element i forbundet er bidratt med et begrenset antall elementer av . ${\ displaystyle \ bigcup M}$${\ displaystyle M}$

Anta at det er et multisett og . Så er det en formel for antall elementer i , gitt utelukkende når det gjelder skjæringspunktene mellom elementer av : ${\ displaystyle M = \ left \ {M_ {1}, M_ {2}, \ ldots, M_ {n} \ right \}}$${\ displaystyle n \ geq 2}$${\ displaystyle | \ trekant M |}$${\ displaystyle \ triangel M}$${\ displaystyle M}$

${\ displaystyle | \ triangel M | = \ sum _ {l = 1}^{n} (-2)^{l-1} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {l} \ leq n} \ venstre | M_ {i_ {1}} \ cap M_ {i_ {2}} \ cap \ ldots \ cap M_ {i_ {l}} \ høyre |}$.

Symmetrisk forskjell på målrom

Så lenge det er en forestilling om "hvor stort" et sett er, kan den symmetriske forskjellen mellom to sett betraktes som et mål på hvor "langt fra hverandre" de er.

Vurder først et begrenset sett S og tellemålet på delsett gitt av størrelsen. Vurder nå to undergrupper av S og sett avstanden fra hverandre som størrelsen på deres symmetriske forskjell. Denne avstanden er faktisk en metrisk , som gjør at kraften som er satt på S til et metrisk mellomrom . Hvis S er n elementer, blir avstanden fra den tomme settet til S er n , og dette er den maksimale avstand for en hvilken som helst par av delmengder.

Ved hjelp av ideene om tiltaksteori kan separasjonen av målbare sett defineres som mål på deres symmetriske forskjell. Hvis μ er et σ-endelig mål definert på et σ-algebra Σ, er funksjonen

${\ displaystyle d _ {\ mu} (X, Y) = \ mu (X \, \ triangel \, Y)}$

er en pseudometrisk på Σ. d _μ blir en metrisk hvis Σ regnes som modulo ekvivalensforholdet X ~ Y hvis og bare hvis . Det kalles noen ganger Fréchet - Nikodym metric. Det resulterende metriske rommet kan skilles hvis og bare hvis L ² (μ) kan skilles. ${\ displaystyle \ mu (X \, \ triangel \, Y) = 0}$

Hvis , har vi: . Faktisk, ${\ displaystyle \ mu (X), \ mu (Y) <\ infty}$${\ displaystyle | \ mu (X)-\ mu (Y) | \ leq \ mu (X \, \ triangel \, 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 |+\ venstre | \ mu \ venstre (Y \ setminus X \ right) \ right | \\ & = \ mu \ left (X \ setminus Y \ right)+\ mu \ left (Y \ setminus X \ right) \ \ & = \ mu \ venstre (\ venstre (X \ settminus Y \ høyre) \ kopp \ venstre (Y \ settminus X \ høyre) \ høyre) \\ & = \ mu \ venstre (X \, \ trekant \, Y \ høyre) \ ende {justert}}}$

Dersom er et mål plass og er målbare sett, da deres symmetriske forskjell er også målbar: . Man kan definere et ekvivalensforhold på målbare sett ved å la og være relatert hvis . Dette forholdet er angitt . ${\ displaystyle S = \ left (\ Omega, {\ mathcal {A}}, \ mu \ right)}$${\ displaystyle F, G \ in {\ mathcal {A}}}$${\ displaystyle F \ triangel G \ i {\ mathcal {A}}}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle \ mu \ venstre (F \ trekant G \ høyre) = 0}$${\ displaystyle F = G \ venstre [{\ mathcal {A}}, \ mu \ right]}$

Gitt , skriver man om det er noen slike til hver . Forholdet " " er en delvis ordre på familien av undergrupper av . ${\ displaystyle {\ mathcal {D}}, {\ mathcal {E}} \ subseteq {\ mathcal {A}}}$${\ displaystyle {\ mathcal {D}} \ subseteq {\ mathcal {E}} \ left [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle D \ i {\ mathcal {D}}}$${\ displaystyle E \ i {\ mathcal {E}}}$${\ displaystyle D = E \ venstre [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle \ subseteq \ left [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle {\ mathcal {A}}}$

Vi skriver om og . Forholdet " " er et ekvivalensforhold mellom undersettene til . ${\ displaystyle {\ mathcal {D}} = {\ mathcal {E}} \ venstre [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle {\ mathcal {D}} \ subseteq {\ mathcal {E}} \ left [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle {\ mathcal {E}} \ subseteq {\ mathcal {D}} \ venstre [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle = \ left [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle {\ mathcal {A}}}$

Den symmetriske nedleggelsen av er samlingen av alle målbare sett som er for noen . Den symmetriske lukkingen av inneholder . Hvis er en subalgebra av , så er den symmetriske nedleggelsen av . ${\ displaystyle {\ mathcal {D}}}$${\ displaystyle {\ mathcal {A}}}$${\ displaystyle = \ left [{\ mathcal {A}}, \ mu \ right]}$${\ displaystyle D \ i {\ mathcal {D}}}$${\ displaystyle {\ mathcal {D}}}$${\ displaystyle {\ mathcal {D}}}$${\ displaystyle {\ mathcal {D}}}$${\ displaystyle \ sigma}$${\ displaystyle {\ mathcal {A}}}$${\ displaystyle {\ mathcal {D}}}$

${\ displaystyle F = G \ venstre [{\ mathcal {A}}, \ mu \ right]}$iff nesten overalt . ${\ displaystyle \ left | \ mathbf {1} _ {F}-\ mathbf {1} _ {G} \ right | = 0}$ ${\ displaystyle \ left [{\ mathcal {A}}, \ mu \ right]}$

Hausdorff avstand kontra symmetrisk forskjell

Den hausdorffavstand og (område av den) symmetrisk forskjellen er begge pseudo-beregninger på settet av målbare geometriske former. Imidlertid oppfører de seg ganske annerledes. Figuren til høyre viser to sekvenser av former, "Rød" og "Rød ∪ Grønn". Når Hausdorff -avstanden mellom dem blir mindre, blir området til den symmetriske forskjellen mellom dem større, og omvendt. Ved å fortsette disse sekvensene i begge retninger, er det mulig å få to sekvenser slik at Hausdorff -avstanden mellom dem konvergerer til 0 og den symmetriske avstanden mellom dem divergerer, eller omvendt.

Se også

Referanser

Bibliografi

• Halmos, Paul R. (1960). Naiv settteori . University Series in Undergraduate Mathematics. van Nostrand Company. Zbl  0087.04403 .
• Symmetrisk forskjell i sett . I Encyclopaedia of Mathematics