Item 15 (005N) — The Clowder Project

4.3.12 Symmetric Differences

Let $X$ be a set and let $U,V\in \mathcal{P}\webleft (X\webright )$.

Definition 4.3.12.1.1 ▶ Symmetric Differences

The symmetric difference of $U$ and $V$ is the set $U\mathbin {\triangle }V$ defined by¹

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

¹Illustration:

Proposition 4.3.12.1.2 ▶ Properties of Symmetric Differences

Let $X$ be a set.

1.
Lack of Functoriality. The assignment $\webleft (U,V\webright )\mapsto U\mathbin {\triangle }V$ does not in general define functors

\[ \begin{array}{ccc} U\mathbin {\triangle }-\colon \mkern -15mu & \webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ) \mkern -17.5mu& {}\mathbin {\to }\webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ),\\ -\mathbin {\triangle }V\colon \mkern -15mu & \webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ) \mkern -17.5mu& {}\mathbin {\to }\webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ),\\ -_{1}\mathbin {\triangle }-_{2}\colon \mkern -15mu & \webleft (\mathcal{P}\webleft (X\webright )\times \mathcal{P}\webleft (X\webright ),\subset \times \subset \webright ) \mkern -17.5mu& {}\mathbin {\to }\webleft (\mathcal{P}\webleft (X\webright ),\subset \webright ). \end{array} \]
2.
Via Unions and Intersections. We have

\[ U\mathbin {\triangle }V=\webleft (U\cup V\webright )\setminus \webleft (U\cap V\webright ) \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$, as in the Venn diagram
3.
Symmetric Differences of Disjoint Sets. If $U$ and $V$ are disjoint, then we have

\[ U\mathbin {\triangle }V=U\cup V. \]
4.
Associativity. The diagram
commutes, i.e. we have

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

for each $U,V,W\in \mathcal{P}\webleft (X\webright )$, as in the Venn diagram
5.
Unitality. The diagrams
commute, i.e. we have

\begin{align*} U\mathbin {\triangle }\text{Ø}& = U,\\ \text{Ø}\mathbin {\triangle }U & = U \end{align*}

for each $U\in \mathcal{P}\webleft (X\webright )$.
6.
Commutativity. The diagram
commutes, i.e. we have

\[ U\mathbin {\triangle }V = V\mathbin {\triangle }U \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
7.
Invertibility. We have

\[ U\mathbin {\triangle }U = \text{Ø} \]

for each $U\in \mathcal{P}\webleft (X\webright )$.
8.
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 $U,V,W\in \mathcal{P}\webleft (X\webright )$.
9.
Interaction With Complements I. We have

\[ U\mathbin {\triangle }U^{\textsf{c}}= X \]

for each $U\in \mathcal{P}\webleft (X\webright )$.
10.
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 $U\in \mathcal{P}\webleft (X\webright )$.
11.
Interaction With Complements III. The diagram
commutes, i.e. we have

\[ U^{\textsf{c}}\mathbin {\triangle }V^{\textsf{c}}=U\mathbin {\triangle }V \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
12.
“Transitivity”. We have

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

for each $U,V,W\in \mathcal{P}\webleft (X\webright )$.
13.
The Triangle Inequality for Symmetric Differences. We have

\[ U\mathbin {\triangle }W\subset U\mathbin {\triangle }V\cup V\mathbin {\triangle }W \]

for each $U,V,W\in \mathcal{P}\webleft (X\webright )$.
14.
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 $U,V,W\in \mathcal{P}\webleft (X\webright )$.

15.
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}\ \ (\mathrm{mod}\ 2) \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.

16.

Bijectivity. Given $U,V\in \mathcal{P}\webleft (X\webright )$, the maps

\begin{align*} U\mathbin {\triangle }- & \colon \mathcal{P}\webleft (X\webright ) \to \mathcal{P}\webleft (X\webright ),\\ -\mathbin {\triangle }V & \colon \mathcal{P}\webleft (X\webright ) \to \mathcal{P}\webleft (X\webright ) \end{align*}

are bijections with inverses given by

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

Moreover, the map

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

17.

Interaction With Powersets and Groups. Let $X$ be a set.

(a)
The quadruple $\webleft (\mathcal{P}\webleft (X\webright ),\mathbin {\triangle },\text{Ø},\operatorname {\mathrm{id}}_{\mathcal{P}\webleft (X\webright )}\webright )$ is an abelian group.¹
(b)
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).

18.

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 Item 17;
•
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}}}=}}\text{Ø},\\ 1\cdot U & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}U; \end{align*}

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

19.

Interaction With Powersets and Vector Spaces II. If $X$ is finite, then:

(a)
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 18.
(b)
We have

\[ \dim \webleft (\mathcal{P}\webleft (X\webright )\webright )=\# {X}. \]

20.

Interaction With Powersets and Rings. The quintuple $\webleft (\mathcal{P}\webleft (X\webright ),\mathbin {\triangle },\cap ,\text{Ø},X\webright )$ is a commutative ring.²

21.

Interaction With Direct Images. We have a natural transformation

with components

\[ f_{!}\webleft (U\webright )\mathbin {\triangle }f_{!}\webleft (V\webright )\subset f_{!}\webleft (U\mathbin {\triangle }V\webright ) \]

indexed by $U,V\in \mathcal{P}\webleft (X\webright )$.

22.

Interaction With Inverse Images. The diagram

i.e. we have

\[ f^{-1}\webleft (U\webright )\mathbin {\triangle }f^{-1}\webleft (V\webright )=f^{-1}\webleft (U\mathbin {\triangle }V\webright ) \]

for each $U,V\in \mathcal{P}\webleft (Y\webright )$.

23.

Interaction With Codirect Images. We have a natural transformation

with components

\[ f_{*}\webleft (U\mathbin {\triangle }V\webright )\subset f_{*}\webleft (U\webright )\mathbin {\triangle }f_{*}\webleft (V\webright ) \]

indexed by $U,V\in \mathcal{P}\webleft (X\webright )$.

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

Proof of Proposition 4.3.12.1.2.

Item 1: Lack of Functoriality

Omitted.

Item 2: Via Unions and Intersections

See [Proof Wiki Contributors, Equivalence of Definitions of Symmetric Difference — Proof Wiki].

Item 3: Symmetric Differences of Disjoint Sets

Since $U$ and $V$ are disjoint, we have $U\cap V=\text{Ø}$, and therefore we have

\begin{align*} U\mathbin {\triangle }V & = \webleft (U\cup V\webright )\setminus \webleft (U\cap V\webright )\\ & = \webleft (U\cup V\webright )\setminus \text{Ø}\\ & = U\cup V, \end{align*}

where we’ve used Item 2 and Item 12 of Proposition 4.3.10.1.2.

Item 4: Associativity

See [Proof Wiki Contributors, Symmetric Difference Is Associative — Proof Wiki].

Item 5: Unitality

This follows from Item 6 and [Proof Wiki Contributors, Symmetric Difference With Empty Set — Proof Wiki].

Item 6: Commutativity

See [Proof Wiki Contributors, Symmetric Difference Is Commutative — Proof Wiki].

Item 7: Invertibility

See [Proof Wiki Contributors, Symmetric Difference With Self Is Empty Set — Proof Wiki].

Item 8: Interaction With Unions

See [Proof Wiki Contributors, Union of Symmetric Differences — Proof Wiki].

Item 9: Interaction With Complements I

See [Proof Wiki Contributors, Symmetric Difference With Complement — Proof Wiki].

Item 10: Interaction With Complements II

This follows from Item 6 and [Proof Wiki Contributors, Symmetric Difference With Universe — Proof Wiki].

Item 11: Interaction With Complements III

See [Proof Wiki Contributors, Symmetric Difference of Complements — Proof Wiki].

Item 12: “Transitivity”

We have

$\webleft (U\mathbin {\triangle }V\webright )\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )$	$\mathord {=}$	$U\mathbin {\triangle }\webleft (V\mathbin {\triangle }\webleft (V\mathbin {\triangle }W\webright )\webright )$	(by Item 4)
	$\mathord {=}$	$U\mathbin {\triangle }\webleft (\webleft (V\mathbin {\triangle }V\webright )\mathbin {\triangle }W\webright )$	(by Item 4)
	$\mathord {=}$	$U\mathbin {\triangle }\webleft (\text{Ø}\mathbin {\triangle }W\webright )$	(by Item 7)
	$\mathord {=}$	$U\mathbin {\triangle }W$.	(by Item 5)