View source for Symmetric difference

{{short description|Elements in exactly one of two sets}}
{{Infobox mathematical statement
| name = Symmetric difference
| image = Venn0110.svg
| caption = [[Venn diagram]] of <math>A  \vartriangle B</math>.  The symmetric difference is the [[Union (set theory)|union]] [[Complement (set theory)#Relative complement|without]] the [[Intersection (set theory)|intersection]]:
{{nowrap|[[File:Venn0111.svg|30px]] <math>~\setminus~</math> 30px <math>~=~</math> [[File:Venn0110.svg|30px]]}}
| type = [[Set (mathematics)#Basic operations|Set operation]]
| field = [[Set (mathematics)|Set theory]]
| statement = The symmetric difference is the set of elements that are in either set, but not in the intersection.
| symbolic statement = <math>A\, \vartriangle\,B = \left(A \setminus B\right) \cup \left(B \setminus A\right)</math>
}}

In [[Mathematics|mathematics]], the '''symmetric difference''' of two [[Set (mathematics)|sets]], also known as the '''disjunctive union''' and '''set sum''', is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets <math>\{1,2,3\}</math> and <math>\{3,4\}</math> is <math>\{1,2,4\}</math>.

The symmetric difference of the sets ''A'' and ''B'' is commonly denoted by <math>A \operatorname\vartriangle B</math> (traditionally, <math>A\ \Delta\ B</math>), <math>A \oplus B</math>, or <math>A \ominus B</math>.
It can be viewed as a form of [[Modular arithmetic|addition modulo 2]].

The [[Power set|power set]] of any set becomes an [[Abelian group|abelian group]] under the operation of symmetric difference, with the [[Empty set|empty set]] as the neutral element of the group and every element in this group being its own [[Inverse element|inverse]]. The power set of any set becomes a [[Boolean ring]], with symmetric difference as the addition of the ring and [[Intersection (set theory)|intersection]] as the multiplication of the ring.

== Properties ==
[[File:Venn 0110 1001.svg|thumb|
Venn diagram of <math>~(A  \vartriangle B)  \vartriangle C</math>

{{nowrap|[[File:Venn 0110 0110.svg|40px]] <math>~ \vartriangle~</math> 40px}} <math>~=~</math> [[File:Venn 0110 1001.svg|40px]]
]]

The symmetric difference is equivalent to the [[Union (set theory)|union]] of both [[Complement (set theory)|relative complement]]s, that is:<ref name=":0">{{Cite web |last=Taylor |first=Courtney |date=March 31, 2019 |title=What Is Symmetric Difference in Math? |url=https://www.thoughtco.com/what-is-the-symmetric-difference-3126594 |access-date=2020-09-05 |website=ThoughtCo |language=en}}</ref>

:<math>A\, \vartriangle\,B = \left(A \setminus B\right) \cup \left(B \setminus A\right),</math>

The symmetric difference can also be expressed using the [[Exclusive or|XOR]] operation ⊕ on the [[Predicate (mathematical logic)|predicates]] describing the two sets in [[Set-builder notation|set-builder notation]]:

:<math>A\mathbin{ \vartriangle}B = \{x : (x \in A) \oplus (x \in B)\}.</math>

The same fact can be stated as the [[Indicator function|indicator function]] (denoted here by <math>\chi</math>) of the symmetric difference, being the XOR (or addition [[Modular arithmetic|mod 2]]) of the indicator functions of its two arguments: <math>\chi_{(A\, \vartriangle\,B)} = \chi_A \oplus \chi_B</math> or using the [[Iverson bracket]] notation <math>[x \in A\, \vartriangle\,B] = [x \in A] \oplus [x \in B]</math>.

The symmetric difference can also be expressed as the union of the two sets, minus their [[Intersection (set theory)|intersection]]:

:<math>A\, \vartriangle\,B = (A \cup B) \setminus (A \cap B),</math><ref name=":0" />

In particular, <math>A \mathbin{ \vartriangle} B\subseteq A\cup B</math>; the equality in this non-strict [[Subset|inclusion]] occurs [[If and only if|if and only if]] <math>A</math> and <math>B</math> are [[Disjoint sets|disjoint sets]]. Furthermore, denoting <math>D = A \mathbin{ \vartriangle} B</math> and <math>I = A \cap B</math>, then <math>D</math> and <math>I</math> are always disjoint, so <math>D</math> and <math>I</math> [[Partition of a set|partition]] <math>A \cup B</math>. Consequently, assuming intersection and symmetric difference as primitive operations, the union of two sets can be well ''defined'' in terms of symmetric difference by the right-hand side of the equality

:<math>A\,\cup\,B = (A\, \vartriangle\,B)\, \vartriangle\,(A \cap B)</math>.

The symmetric difference is commutative and associative:

:<math>\begin{align}
                  A\, \vartriangle\,B &= B\, \vartriangle\,A, \\
  (A\, \vartriangle\,B)\, \vartriangle\,C &= A\, \vartriangle\,(B\, \vartriangle\,C).
\end{align}</math>

The [[Empty set|empty set]] is [[Identity element|neutral]], and every set is its own inverse:
:<math>\begin{align}
  A\, \vartriangle\,\varnothing &= A, \\
            A\, \vartriangle\,A &= \varnothing.
\end{align}</math>

Thus, the [[Power set|power set]] of any set ''X'' becomes an [[Abelian group|abelian group]] under the symmetric difference operation. (More generally, any [[Field of sets|field of sets]] forms a group with the symmetric difference as operation.) A group in which every element is its own inverse (or, equivalently, in which every element has [[Order (group theory)|order]] 2) is sometimes called a Boolean group;<ref name="GivantHalmos2009">{{cite book |last1=Givant |first1=Steven |last2=Halmos |first2=Paul |year=2009 |title=Introduction to Boolean Algebras |publisher=Springer Science & Business Media |isbn=978-0-387-40293-2 |page=6}}</ref><ref name="Humberstone2011">{{cite book |last=Humberstone |first=Lloyd |year=2011 |title=The Connectives |url=https://archive.org/details/connectives00humb |url-access=limited |publisher=MIT Press |isbn=978-0-262-01654-4 |page=[https://archive.org/details/connectives00humb/page/n800 782]}}</ref> the symmetric difference provides a prototypical example of such groups. Sometimes the Boolean group is actually defined as the symmetric difference operation on a set.<ref name="Rotman2010">{{cite book |last=Rotman |first=Joseph J. |year=2010 |title=Advanced Modern Algebra |publisher=American Mathematical Soc. |isbn=978-0-8218-4741-1 |page=19}}</ref> In the case where ''X'' has only two elements, the group thus obtained is the [[Klein four-group]].

Equivalently, a Boolean group is an [[Elementary abelian group|elementary abelian 2-group]]. Consequently, the group induced by the symmetric difference is in fact a [[Vector space|vector space]] over the [[Finite field|field with 2 elements]] '''Z'''<sub>2</sub>. If ''X'' is finite, then the [[Singleton (mathematics)|singleton]]s form a [[Basis (linear algebra)|basis]] of this vector space, and its dimension is therefore equal to the number of elements of ''X''. This construction is used in [[Graph theory|graph theory]], to define the [[Cycle space|cycle space]] of a graph.

From the property of the inverses in a Boolean group, it follows that the symmetric difference of two repeated symmetric differences is equivalent to the repeated symmetric difference of the [[Multiset#Operations|join]] of the two multisets, where for each double set both can be removed. In particular:

:<math>(A\, \vartriangle\,B)\, \vartriangle\,(B\, \vartriangle\,C) = A\, \vartriangle\,C.</math>

This implies triangle inequality:<ref>{{cite book |last1=Rudin |first1=Walter |date=January 1, 1976 |title=Principles of Mathematical Analysis |url=https://archive.org/details/principlesofmath00rudi |url-access=registration |edition=3rd |publisher=McGraw-Hill Education |isbn=978-0070542358 |page=[https://archive.org/details/principlesofmath00rudi/page/306 306]}}</ref> the symmetric difference of ''A'' and ''C'' is contained in the union of the symmetric difference of ''A'' and ''B'' and that of ''B'' and ''C''.

Intersection distributes over symmetric difference:
:<math>A \cap (B\, \vartriangle\,C) = (A \cap B)\, \vartriangle\,(A \cap C),</math>

and this shows that the power set of ''X'' becomes a [[Ring (mathematics)|ring]], with symmetric difference as addition and intersection as multiplication. This is the prototypical example of a [[Boolean ring]].

Further properties of the symmetric difference include:

* <math>A \mathbin{ \vartriangle} B = \emptyset</math> if and only if <math>A = B</math>.
* <math>A \mathbin{ \vartriangle} B = A^c \mathbin{ \vartriangle} B^c</math>, where <math>A^c</math>, <math>B^c</math> is <math>A</math>'s complement, <math>B</math>'s complement, respectively, relative to any (fixed) set that contains both.
* <math>\left(\bigcup_{\alpha\in\mathcal{I}}A_\alpha\right) \vartriangle\left(\bigcup_{\alpha\in\mathcal{I}}B_\alpha\right)\subseteq\bigcup_{\alpha\in\mathcal{I}}\left(A_\alpha \mathbin{ \vartriangle} B_\alpha\right)</math>, where <math>\mathcal{I}</math> is an arbitrary non-empty index set.
* If <math>f : S \rightarrow T</math> is any function and <math>A, B \subseteq T</math> are any sets in <math>f</math>'s codomain, then <math>f^{-1}\left(A \mathbin{ \vartriangle} B\right) = f^{-1}\left(A\right) \mathbin{ \vartriangle} f^{-1}\left(B\right).</math>

The symmetric difference can be defined in any [[Boolean algebra (structure)|Boolean algebra]], by writing
:<math> x\, \vartriangle\,y = (x \lor y) \land \lnot(x \land y) = (x \land \lnot y) \lor (y \land \lnot x) = x \oplus y.</math>

This operation has the same properties as the symmetric difference of sets.

==''n''-ary symmetric difference==
Repeated symmetric difference is in a sense equivalent to an operation on a multitude of sets (possibly with multiple appearances of the same set) giving the set of elements which are in an odd number of sets.

The symmetric difference of a collection of sets contains just elements which are in an odd number of the sets in the collection:
<math display="block"> \vartriangle M = \left\{ a \in \bigcup M: \left|\{A \in M:a \in A\}\right| \text{ is odd}\right\}.</math>

Evidently, this is well-defined only when each element of the union <math display="inline">\bigcup M</math> is contributed by a finite number of elements of <math>M</math>.

Suppose <math>M = \left\{M_1, M_2, \ldots, M_n\right\}</math> is a [[Multiset|multiset]] and <math>n \ge 2</math>. Then there is a formula for <math>| \vartriangle M|</math>, the number of elements in <math> \vartriangle M</math>, given solely in terms of intersections of elements of <math>M</math>:
<math display="block">| \vartriangle 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|.</math>

==Symmetric difference on measure spaces==
As long as there is a notion of "how big" a set is, the symmetric difference between two sets can be considered a measure of how "far apart" they are.

First consider a finite set ''S'' and the [[Counting measure|counting measure]] on subsets given by their size. Now consider two subsets of ''S'' and set their distance apart as the size of their symmetric difference. This distance is in fact a [[Metric (mathematics)|metric]], which makes the [[Power set|power set]] on ''S'' a [[Metric space|metric space]]. If ''S'' has ''n'' elements, then the distance from the [[Empty set|empty set]] to ''S'' is ''n'', and this is the maximum distance for any pair of subsets.<ref>Claude Flament (1963) ''Applications of Graph Theory to Group Structure'', page 16, Prentice-Hall {{mr|id=0157785}}</ref>

Using the ideas of measure theory, the separation of measurable sets can be defined to be the measure of their symmetric difference. If μ is a σ-finite [[Measure space|measure]] defined on a [[Sigma-algebra|σ-algebra]] Σ, the function
:<math>d_\mu(X, Y) = \mu(X\, \vartriangle\,Y)</math>

is a [[Pseudometric space|pseudometric]] on Σ. ''d<sub>μ</sub>'' becomes a [[Metric space|metric]] if Σ is considered modulo the [[Equivalence relation|equivalence relation]] ''X'' ~ ''Y'' if and only if <math>\mu(X\, \vartriangle\,Y) = 0</math>. It is sometimes called Fréchet-Nikodym metric. The resulting metric space is [[Separable space|separable]] if and only if L<sup>2</sup>(μ) is separable.

If <math>\mu(X), \mu(Y) < \infty</math>, we have: <math>|\mu(X) - \mu(Y)| \leq \mu(X\, \vartriangle\,Y)</math>. Indeed,
:<math>\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) \\
    &=    \mu\left(\left(X \setminus Y\right) \cup \left(Y \setminus X\right)\right) \\
    &=    \mu\left(X\,  \vartriangle \, Y\right)
\end{align}</math>

If <math>S = \left(\Omega, \mathcal{A},\mu\right)</math> is a measure space and <math>F, G \in \mathcal{A}</math> are measurable sets, then their symmetric difference is also measurable: <math>F  \vartriangle G \in \mathcal{A}</math>. One may define an equivalence relation on measurable sets by letting <math>F</math> and <math>G</math> 
be related if <math>\mu\left(F  \vartriangle G\right) = 0</math>. This relation is denoted <math>F = G\left[\mathcal{A}, \mu\right]</math>.

Given <math>\mathcal{D}, \mathcal{E} \subseteq \mathcal{A}</math>, one writes <math>\mathcal{D}\subseteq\mathcal{E}\left[\mathcal{A}, \mu\right]</math> if to each <math>D\in\mathcal{D}</math> there's some <math>E \in \mathcal{E}</math> such that <math>D = E\left[\mathcal{A}, \mu\right]</math>. The relation "<math>\subseteq\left[\mathcal{A}, \mu\right]</math>" is a partial order on the family of subsets of <math>\mathcal{A}</math>.

We write <math>\mathcal{D} = \mathcal{E}\left[\mathcal{A}, \mu\right]</math> if <math>\mathcal{D}\subseteq\mathcal{E}\left[\mathcal{A}, \mu\right]</math> and <math>\mathcal{E} \subseteq \mathcal{D}\left[\mathcal{A}, \mu\right]</math>. The relation "<math>= \left[\mathcal{A}, \mu\right]</math>" is an equivalence relationship between the subsets of <math>\mathcal{A}</math>.

The ''symmetric closure'' of <math>\mathcal{D}</math> is the collection of all <math>\mathcal{A}</math>-measurable sets that are <math>= \left[\mathcal{A}, \mu\right]</math> to some <math>D \in \mathcal{D}</math>. The symmetric closure of <math>\mathcal{D}</math> contains <math>\mathcal{D}</math>. If <math>\mathcal{D}</math> is a sub-<math>\sigma</math>-algebra of <math>\mathcal{A}</math>, so is the symmetric closure of <math>\mathcal{D}</math>.

<math>F = G\left[\mathcal{A}, \mu\right]</math> iff <math>\left|\mathbf{1}_F - \mathbf{1}_G\right| = 0</math> <math>\left[\mathcal{A}, \mu\right]</math> [[Almost everywhere|almost everywhere]].

== Hausdorff distance vs. symmetric difference ==
[[File:HausdorffVsSymmetric.png|thumb|right]]
The [[Hausdorff distance]] and the (area of the) symmetric difference are both pseudo-metrics on the set of measurable geometric shapes. However, they behave quite differently. The figure at the right shows two sequences of shapes, "Red" and "Red ∪ Green". When the Hausdorff distance between them becomes smaller, the area of the symmetric difference between them becomes larger, and vice versa. By continuing these sequences in both directions, it is possible to get two sequences such that the Hausdorff distance between them converges to 0 and the symmetric distance between them diverges, or vice versa.

== See also ==
{{div col|colwidth=22em}}
* [[Algebra of sets]]
* [[Boolean function]]
* [[Complement (set theory)]]
* Difference (set theory)
* [[Exclusive or]]
* [[Fuzzy set]]
* [[Intersection (set theory)]]
* [[Jaccard index]]
* [[List of set identities and relations]]
* [[Logical graph]]
* [[Sigma-algebra#Separable .CF.83-algebras|Separable sigma algebras]]
* [[Set theory]]
* [[Symmetry]]
* [[Union (set theory)]]
* [[Inclusion–exclusion principle|inclusion–exclusion principle]]
{{div col end}}

==References==
{{Reflist}}

== Bibliography ==
*{{cite book |last=Halmos |first=Paul R. |year=1960 |title=Naive set theory |series=The University Series in Undergraduate Mathematics |publisher=van Nostrand Company |zbl=0087.04403}}
*[http://www.encyclopediaofmath.org/index.php/Symmetric_difference_of_sets ''Symmetric difference of sets'']. In Encyclopaedia of Mathematics


[[Category:Basic concepts in set theory]]

{{Sourceattribution|Symmetric difference}}