2.3.12 Symmetric Differences

Let $A$ and $B$ be sets.

The symmetric difference of $A$ and $B$ is the set $A\mathbin {\triangle }B$ defined by

\[ A\mathbin {\triangle }B \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft (A\setminus B\webright )\cup \webleft (B\setminus A\webright ). \]

Let $X$ be a set.

  1. Lack of Functoriality. The assignment $\webleft (U,V\webright )\mapsto U\mathbin {\triangle }V$ need not define functors
    \begin{gather*} \begin{aligned} U\mathbin {\triangle }- & \colon \webleft (\mathcal{P}\webleft (X\webright ),\subset \webright )\to \webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ),\\ -\mathbin {\triangle }V & \colon \webleft (\mathcal{P}\webleft (X\webright ),\subset \webright )\to \webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ),\\ \end{aligned}\\ -_{1}\mathbin {\triangle }-_{2} \colon \webleft (\mathcal{P}\webleft (X\webright )\times \mathcal{P}\webleft (X\webright ),\subset \times \subset \webright )\to \webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ).\end{gather*}
  2. Via Unions and Intersections. We have[1]
    \[ U\mathbin {\triangle }V = \webleft (U\cup V\webright )\setminus \webleft (U\cap V\webright ) \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V\in \mathcal{P}\webleft (X\webright )$.

  3. Associativity. We have[2]
    \[ \webleft (U\mathbin {\triangle }V\webright )\mathbin {\triangle }W = U\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright ) \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V,W\in \mathcal{P}\webleft (X\webright )$.

  4. Commutativity. We have
    \[ U\mathbin {\triangle }V = V\mathbin {\triangle }U \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V\in \mathcal{P}\webleft (X\webright )$.

  5. Unitality. We have
    \begin{align*} U\mathbin {\triangle }\emptyset & = U,\\ \emptyset \mathbin {\triangle }U & = U \end{align*}

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U\in \mathcal{P}\webleft (X\webright )$.

  6. Invertibility. We have
    \[ U\mathbin {\triangle }U = \emptyset \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U\in \mathcal{P}\webleft (X\webright )$.

  7. Interaction With Unions. We have
    \[ \webleft (U\mathbin {\triangle }V\webright )\cup \webleft (V\mathbin {\triangle }T\webright ) = \webleft (U\cup V\cup W\webright )\setminus \webleft (U\cap V\cap W\webright ) \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V,W\in \mathcal{P}\webleft (X\webright )$.

  8. Interaction With Complements I. We have
    \[ U\mathbin {\triangle }U^{\textsf{c}}= X \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U\in \mathcal{P}\webleft (X\webright )$.

  9. Interaction With Complements II. We have
    \begin{align*} U\mathbin {\triangle }X & = U^{\textsf{c}},\\ X\mathbin {\triangle }U & = U^{\textsf{c}}\end{align*}

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U\in \mathcal{P}\webleft (X\webright )$.

  10. Interaction With Complements III. We have
    \[ U^{\textsf{c}}\mathbin {\triangle }V^{\textsf{c}}=U\mathbin {\triangle }V \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V\in \mathcal{P}\webleft (X\webright )$.

  11. “Transitivity”. We have
    \[ \webleft (U\mathbin {\triangle }V\webright )\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )=U\mathbin {\triangle }W \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V,W\in \mathcal{P}\webleft (X\webright )$.

  12. The Triangle Inequality for Symmetric Differences. We have
    \[ U\mathbin {\triangle }W\subset U\mathbin {\triangle }V\cup V\mathbin {\triangle }W \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V,W\in \mathcal{P}\webleft (X\webright )$.

  13. Distributivity Over Intersections. We have
    \begin{align*} U\cap \webleft (V\mathbin {\triangle }W\webright ) & = \webleft (U\cap V\webright )\mathbin {\triangle }\webleft (U\cap W\webright ),\\ \webleft (U\mathbin {\triangle }V\webright )\cap W & = \webleft (U\cap W\webright )\mathbin {\triangle }\webleft (V\cap W\webright ) \end{align*}

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V,W\in \mathcal{P}\webleft (X\webright )$.

  14. Interaction With Characteristic Functions. We have
    \[ \chi _{U\mathbin {\triangle }V}=\chi _{U}+\chi _{V}-2\chi _{U\cap V} \]

    and thus, in particular, we have

    \[ \chi _{U\mathbin {\triangle }V}\equiv \chi _{U}+\chi _{V}\mod {2} \]

    for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V\in \mathcal{P}\webleft (X\webright )$.

  15. Bijectivity. Given $A,B\subset \mathcal{P}\webleft (X\webright )$, the maps
    \begin{align*} A\mathbin {\triangle }- & \colon \mathcal{P}\webleft (X\webright ) \to \mathcal{P}\webleft (X\webright ),\\ -\mathbin {\triangle }B & \colon \mathcal{P}\webleft (X\webright ) \to \mathcal{P}\webleft (X\webright ) \end{align*}

    are bijections with inverses given by

    \begin{align*} \webleft (A\mathbin {\triangle }-\webright )^{-1} & = -\cup \webleft (A\cap -\webright ),\\ \webleft (-\mathbin {\triangle }B\webright )^{-1} & = -\cup \webleft (B\cap -\webright ). \end{align*}

    Moreover, the map

    \[ C\mapsto C\mathbin {\triangle }\webleft (A\mathbin {\triangle }B\webright ) \]

    is a bijection of $\mathcal{P}\webleft (X\webright )$ onto itself sending $A$ to $B$ and $B$ to $A$.

  16. Interaction With Powersets and Groups. Let $X$ be a set.
    1. The quadruple $\webleft (\mathcal{P}\webleft (X\webright ),\mathbin {\triangle },\emptyset ,\text{id}_{\mathcal{P}\webleft (X\webright )}\webright )$ is an abelian group.[3]
    2. Every element of $\mathcal{P}\webleft (X\webright )$ has order $2$ with respect to $\mathbin {\triangle }$, and thus $\mathcal{P}\webleft (X\webright )$ is a Boolean group (i.e. an abelian $2$-group).
  17. Interaction With Powersets and Vector Spaces I. The pair $\webleft (\mathcal{P}\webleft (X\webright ),\alpha _{\mathcal{P}\webleft (X\webright )}\webright )$ consisting of
    • The group $\mathcal{P}\webleft (X\webright )$ of ;
    • The map $\alpha _{\mathcal{P}\webleft (X\webright )}\colon \mathbb {F}_{2}\times \mathcal{P}\webleft (X\webright )\to \mathcal{P}\webleft (X\webright )$ defined by
      \begin{align*} 0\cdot U & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\emptyset ,\\ 1\cdot U & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}U; \end{align*}

    is an $\mathbb {F}_{2}$-vector space.

  18. Interaction With Powersets and Vector Spaces II. If $X$ is finite, then:
    1. The set of singletons sets on the elements of $X$ forms a basis for the $\mathbb {F}_{2}$-vector space $\webleft (\mathcal{P}\webleft (X\webright ),\alpha _{\mathcal{P}\webleft (X\webright )}\webright )$ of Item 17.
    2. We have
      \[ \dim \webleft (\mathcal{P}\webleft (X\webright )\webright )=\# \mathcal{P}\webleft (X\webright ). \]

  19. Interaction With Powersets and Rings. The quintuple $\webleft (\mathcal{P}\webleft (X\webright ),\mathbin {\triangle },\cap ,\emptyset ,X\webright )$ is a commutative ring.[4]

Item 1: Lack of Functoriality
Omitted.
Item 2: Via Unions and Intersections
See [Proof Wiki, Equivalence of Definitions of Symmetric Difference].
Item 3: Associativity
See [Proof Wiki, Symmetric Difference Is Associative].
Item 4: Commutativity
See [Proof Wiki, Symmetric Difference Is Commutative].
Item 5: Unitality
This follows from Item 4 and [Proof Wiki, Symmetric Difference With Empty Set].
Item 6: Invertibility
See [Proof Wiki, Symmetric Difference With Self Is Empty Set].
Item 7: Interaction With Unions
See [Proof Wiki, Union Of Symmetric Differences].
Item 8: Interaction With Complements I
See [Proof Wiki, Symmetric Difference With Complement].
Item 9: Interaction With Complements II
This follows from Item 4 and [Proof Wiki, Symmetric Difference With Universe].
Item 10: Interaction With Complements III
See [Proof Wiki, Symmetric Difference Of Complements].
Item 11: “Transitivity”
We have

$\webleft (U\mathbin {\triangle }V\webright )\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright ) = U\mathbin {\triangle }\webleft (V\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )\webright )$

(by Item 3)

$\phantom{\webleft (U\mathbin {\triangle }V\webright )\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )} =\rlap {U\mathbin {\triangle }\webleft (\webleft (V\mathbin {\triangle }V\webright )\mathbin {\triangle }W\webright )}\phantom{U\mathbin {\triangle }\webleft (V\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )\webright )}$

(by Item 3)

$\phantom{\webleft (U\mathbin {\triangle }V\webright )\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )} = \rlap {U\mathbin {\triangle }\webleft (\emptyset \mathbin {\triangle }W\webright )}\phantom{U\mathbin {\triangle }\webleft (V\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )\webright )}$

(by Item 6)

$\phantom{\webleft (U\mathbin {\triangle }V\webright )\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )} = \rlap {U\mathbin {\triangle }W}\phantom{U\mathbin {\triangle }\webleft (V\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )\webright )}$

(by Item 5)

Item 12: The Triangle Inequality for Symmetric Differences
This follows from Item 11 and Item 2.
Item 13: Distributivity Over Intersections
See [Proof Wiki, Intersection Distributes Over Symmetric Difference].
Item 14: Interaction With Characteristic Functions
See [Proof Wiki, Characteristic Function Of Symmetric Difference].
Item 15: Bijectivity
Clear.
Item 16: Interaction With Powersets and Groups
Item (a) follows from[5] Item 3, Item 5, Item 6, and Item 4, while Item (b) follows from Item 6.
Item 17: Interaction With Powersets and Vector Spaces I
Clear.
Item 18: Interaction With Powersets and Vector Spaces II
Omitted.
Item 19: Interaction With Powersets and Rings
This follows from Item 8 and Item 11 of Proposition 2.3.9.1.2 and Item 13 and Item 16.[6]


Footnotes

[1] Illustration:
[2] Illustration:
[3] Here are some examples:
  1. When $X=\emptyset $, we have an isomorphism of groups between $\mathcal{P}\webleft (\emptyset \webright )$ and the trivial group:
    \[ \webleft (\mathcal{P}\webleft (\emptyset \webright ),\mathbin {\triangle },\emptyset ,\text{id}_{\mathcal{P}\webleft (\emptyset \webright )}\webright ) \cong \text{pt}. \]
  2. When $X=\text{pt}$, we have an isomorphism of groups between $\mathcal{P}\webleft (\text{pt}\webright )$ and $\mathbb {Z}_{/2}$:
    \[ \webleft (\mathcal{P}\webleft (\text{pt}\webright ),\mathbin {\triangle },\emptyset ,\text{id}_{\mathcal{P}\webleft (\text{pt}\webright )}\webright ) \cong \mathbb {Z}_{/2}. \]
  3. When $X=\webleft\{ 0,1\webright\} $, we have an isomorphism of groups between $\mathcal{P}\webleft (\webleft\{ 0,1\webright\} \webright )$ and $\mathbb {Z}_{/2}\times \mathbb {Z}_{/2}$:
    \[ \webleft (\mathcal{P}\webleft (\webleft\{ 0,1\webright\} \webright ),\mathbin {\triangle },\emptyset ,\text{id}_{\mathcal{P}\webleft (\webleft\{ 0,1\webright\} \webright )}\webright ) \cong \mathbb {Z}_{/2}\times \mathbb {Z}_{/2}. \]
[4] Dangerous Bend SymbolWarning: The analogous statement replacing intersections by unions (i.e. that the quintuple $\webleft (\mathcal{P}\webleft (X\webright ),\mathbin {\triangle },\cup ,\emptyset ,X\webright )$ is a ring) is false, however. See [Proof Wiki, Symmetric Difference With Union Does Not Form Ring] for a proof.


Noticed something off, or have any comments? Feel free to reach out!


You can also use the contact form below: