Item 8 (005F) — The Clowder Project

4.3.12 Symmetric Differences

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

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}}}=}}(U\setminus V)\cup (V\setminus U). \]

¹Illustration:

Proposition 4.3.12.1.2 ▶ Properties of Symmetric Differences

Let $X$ be a set.

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

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

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

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

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

for each $U,V,W\in \mathcal{P}(X)$, 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}(X)$.
6.
Commutativity. The diagram
commutes, i.e. we have

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

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

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

for each $U\in \mathcal{P}(X)$.

8.
Interaction With Unions. We have

\[ (U\mathbin {\triangle }V)\cup (V\mathbin {\triangle }T) = (U\cup V\cup W)\setminus (U\cap V\cap W) \]

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

Interaction With Complements I. We have

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

for each $U\in \mathcal{P}(X)$.

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}(X)$.

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}(X)$.

12.

“Transitivity”. We have

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

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

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}(X)$.

14.

Distributivity Over Intersections. We have

\begin{align*} U\cap (V\mathbin {\triangle }W) & = (U\cap V)\mathbin {\triangle }(U\cap W),\\ (U\mathbin {\triangle }V)\cap W & = (U\cap W)\mathbin {\triangle }(V\cap W) \end{align*}

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

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}(X)$.

16.

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

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

are self-inverse bijections. Moreover, the map

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

17.

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

(a)
The quadruple $(\mathcal{P}(X),\mathbin {\triangle },\text{Ø},\operatorname {\mathrm{id}}_{\mathcal{P}(X)})$ is an abelian group.¹
(b)
Every element of $\mathcal{P}(X)$ has order $2$ with respect to $\mathbin {\triangle }$, and thus $\mathcal{P}(X)$ is a Boolean group (i.e. an abelian $2$-group).

18.

Interaction With Powersets and Vector Spaces I. The pair $(\mathcal{P}(X),\alpha _{\mathcal{P}(X)})$ consisting of

•
The group $\mathcal{P}(X)$ of Item 17;
•
The map $\alpha _{\mathcal{P}(X)}\colon \mathbb {F}_{2}\times \mathcal{P}(X)\to \mathcal{P}(X)$ 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 $(\mathcal{P}(X),\alpha _{\mathcal{P}(X)})$ of Item 18.
(b)
We have

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

20.

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

21.

Interaction With Direct Images. We have a natural transformation

with components

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

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

22.

Interaction With Inverse Images. The diagram

i.e. we have

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

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

23.

Interaction With Codirect Images. We have a natural transformation

with components

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

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

¹Here are some examples:
1. (i)
  When $X=\text{Ø}$, we have an isomorphism of groups between $\mathcal{P}(\text{Ø})$ and the trivial group:
  
  \[ (\mathcal{P}(\text{Ø}),\mathbin {\triangle },\text{Ø},\operatorname {\mathrm{id}}_{\mathcal{P}(\text{Ø})}) \cong \mathrm{pt}. \]
2. (ii)
  When $X=\mathrm{pt}$, we have an isomorphism of groups between $\mathcal{P}(\mathrm{pt})$ and $\mathbb {Z}_{/2}$:
  
  \[ (\mathcal{P}(\mathrm{pt}),\mathbin {\triangle },\text{Ø},\operatorname {\mathrm{id}}_{\mathcal{P}(\mathrm{pt})}) \cong \mathbb {Z}_{/2}. \]
3. (iii)
  When $X=\left\{ 0,1\right\} $, we have an isomorphism of groups between $\mathcal{P}(\left\{ 0,1\right\} )$ and $\mathbb {Z}_{/2}\times \mathbb {Z}_{/2}$:
  
  \[ (\mathcal{P}(\left\{ 0,1\right\} ),\mathbin {\triangle },\text{Ø},\operatorname {\mathrm{id}}_{\mathcal{P}(\left\{ 0,1\right\} )}) \cong \mathbb {Z}_{/2}\times \mathbb {Z}_{/2}. \]
²Warning: The analogous statement replacing intersections by unions (i.e. that the quintuple $(\mathcal{P}(X),\mathbin {\triangle },\cup ,\text{Ø},X)$ 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

Let $X = \left\{ 0,1\right\} , U = \left\{ 0\right\} $. Then $\text{Ø}\subset U$, but $U \mathbin {\triangle }\text{Ø}= U \centernot {\subset }\text{Ø}= U \mathbin {\triangle }U$ from Item 5 and Item 7. This gives a counterexample to the first statement. By using Item 6, we can adapt it to the second and third statement.

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 & = (U\cup V)\setminus (U\cap V)\\ & = (U\cup V)\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

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

This finishes the proof.

Item 13: The Triangle Inequality for Symmetric Differences

This follows from Item 12 and Item 2.

Item 14: Distributivity Over Intersections

See [Proof Wiki Contributors, Intersection Distributes Over Symmetric Difference — Proof Wiki].

Item 15: Interaction With Characteristic Functions

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

Item 16: Bijectivity

•

We show that

\[ (U\mathbin {\triangle }-)\colon \mathcal{P}(X)\to \mathcal{P}(X) \]

is self-inverse.

Let $W \in \mathcal{P}(X)$. Then,

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

•
By Item 6, $(- \mathbin {\triangle }V) = (V \mathbin {\triangle }-)$, hence the former is also self-inverse by the first point.
•
The map $- \mathbin {\triangle }(U \mathbin {\triangle }V)$ is a bijection as a special case of the second point. From the first two points and Item 6, we get

\[ U \mathbin {\triangle }(U \mathbin {\triangle }V) = V,\ V \mathbin {\triangle }(U \mathbin {\triangle }V) = V \mathbin {\triangle }(V \mathbin {\triangle }U) = U. \]

Hence the function maps $U$ to $V$ and $V$ to $U$.