Subsection 4.3.10 (004D): Differences

4.3.10 Differences

Let $X$ and $Y$ be sets.

The difference of $X$ and $Y$ is the set $X\setminus Y$ defined by

\[ X\setminus Y \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in X\ \middle |\ a\not\in Y\right\} . \]

Proposition 4.3.10.1.2 ▶ Properties of Differences

Let $X$ be a set.

1.
Functoriality. The assignments $U,V,(U,V)\mapsto U\cap V$ define functors

\[ \begin{array}{ccc} U\setminus -\colon \mkern -15mu & (\mathcal{P}(X),\supset ) \mkern -17.5mu& {}\mathbin {\to }(\mathcal{P}(X),\subset ),\\ -\setminus V\colon \mkern -15mu & (\mathcal{P}(X),\subset ) \mkern -17.5mu& {}\mathbin {\to }(\mathcal{P}(X),\subset ),\\ -_{1}\setminus -_{2}\colon \mkern -15mu & (\mathcal{P}(X)\times \mathcal{P}(X),\subset \times \supset ) \mkern -17.5mu& {}\mathbin {\to }(\mathcal{P}(X),\subset ). \end{array} \]

In particular, the following statements hold for each $U,V,A,B\in \mathcal{P}(X)$:
1. (a)
  If $U\subset A$, then $U\setminus V\subset A\setminus V$.
2. (b)
  If $V\subset B$, then $U\setminus B\subset U\setminus V$.
3. (c)
  If $U\subset A$ and $V\subset B$, then $U\setminus B\subset A\setminus V$.
2.
De Morgan’s Laws. We have equalities of sets

\begin{align*} X\setminus (U\cup V) & = (X\setminus U)\cap (X\setminus V),\\ X\setminus (U\cap V) & = (X\setminus U)\cup (X\setminus V) \end{align*}

for each $U,V\in \mathcal{P}(X)$.
3.
Interaction With Unions I. We have equalities of sets

\[ U\setminus (V\cup W)=(U\setminus V)\cap (U\setminus W) \]

for each $U,V,W\in \mathcal{P}(X)$.
4.
Interaction With Unions II. We have equalities of sets

\[ (U\setminus V)\cup W=(U\cup W)\setminus (V\setminus W) \]

for each $U,V,W\in \mathcal{P}(X)$.
5.
Interaction With Unions III. We have equalities of sets

\begin{align*} U\setminus (V\cup W) & = (U\cup W)\setminus (V\cup W)\\ & = (U\setminus V)\setminus W\\ & = (U\setminus W)\setminus V \end{align*}

for each $U,V,W\in \mathcal{P}(X)$.
6.
Interaction With Unions IV. We have equalities of sets

\[ (U\cup V)\setminus W=(U\setminus W)\cup (V\setminus W) \]

for each $U,V,W\in \mathcal{P}(X)$.
7.
Interaction With Intersections. We have equalities of sets

\begin{align*} (U\setminus V)\cap W & = (U\cap W)\setminus V\\ & = U\cap (W\setminus V) \end{align*}

for each $U,V,W\in \mathcal{P}(X)$.
8.
Interaction With Complements. We have an equality of sets

\[ U\setminus V=U\cap V^{\textsf{c}} \]

for each $U,V\in \mathcal{P}(X)$.
9.
Interaction With Symmetric Differences. We have an equality of sets

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

for each $U,V\in \mathcal{P}(X)$.
10.
Triple Differences. We have

\[ U\setminus (V\setminus W)=(U\cap W)\cup (U\setminus V) \]

for each $U,V,W\in \mathcal{P}(X)$.
11.
Left Annihilation. We have

\[ \text{Ø}\setminus U=\text{Ø} \]

for each $U\in \mathcal{P}(X)$.
12.
Right Unitality. We have

\[ U\setminus \text{Ø}=U \]

for each $U\in \mathcal{P}(X)$.
13.
Right Annihilation. We have

\[ U\setminus X=\text{Ø} \]

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

\[ U\setminus U = \text{Ø} \]

for each $U\in \mathcal{P}(X)$.
15.
Interaction With Containment. The following conditions are equivalent:
1. (a)
  We have $V\setminus U\subset W$.
2. (b)
  We have $V\setminus W\subset U$.
16.
Interaction With Characteristic Functions. We have

\[ \chi _{U\setminus V}=\chi _{U}-\chi _{U\cap V} \]

for each $U,V\in \mathcal{P}(X)$.
17.
Interaction With Direct Images. We have a natural transformation
with components

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

indexed by $U,V\in \mathcal{P}(X)$.
18.
Interaction With Inverse Images. The diagram
commutes, i.e. we have

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

for each $U,V\in \mathcal{P}(X)$.
19.
Interaction With Codirect Images. We have a natural transformation
with components

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

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

Proof of Proposition 4.3.10.1.2.

Item 1: Functoriality

See [Proof Wiki Contributors, Set Difference Over Subset — Proof Wiki] and [Proof Wiki Contributors, Set Difference With Subset Is Superset of Set Difference — Proof Wiki].

Item 2: De Morgan’s Laws

See [Proof Wiki Contributors, De Morgan's Laws (Set Theory) — Proof Wiki].

Item 3: Interaction With Unions I

See [Proof Wiki Contributors, De Morgan's Laws (Set Theory)/Set Difference/Difference with Union — Proof Wiki].

Item 4: Interaction With Unions II

We have

\begin{align*} (U \setminus V) \cup W & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ x \in X\ \middle |\ \text{($x \in U$ and $x \not\in V$) or $x \in W$}\right\} \\ & = \left\{ x \in X\ \middle |\ \text{($x \in U$ or $x \in W$) and ($x \not\in V$ or $x \in W$)}\right\} \\ & = \left\{ x \in X\ \middle |\ \text{($x \in U \cup W$) and not ($x \in V$ and $x \not\in W$)}\right\} \\ & = \left\{ x \in X\ \middle |\ \text{($x \in U \cup W$) and not ($x \in V \setminus W$)}\right\} \\ & = \left\{ x \in X\ \middle |\ \text{($x \in (U \cup W) \setminus (V \setminus W)$)}\right\} \\ & = (U \cup W) \setminus (V \setminus W). \end{align*}

Item 5: Interaction With Unions III

See [Proof Wiki Contributors, Set Difference With Union — Proof Wiki].

Item 6: Interaction With Unions IV

See [Proof Wiki Contributors, Set Difference Is Right Distributive Over Union — Proof Wiki].

Item 7: Interaction With Intersections

See [Proof Wiki Contributors, Intersection With Set Difference Is Set Difference With Intersection — Proof Wiki].

Item 8: Interaction With Complements

See [Proof Wiki Contributors, Set Difference as Intersection With Complement — Proof Wiki].

Item 9: Interaction With Symmetric Differences

See [Proof Wiki Contributors, Set Difference as Symmetric Difference With Intersection — Proof Wiki].

Item 10: Triple Differences

See [Proof Wiki Contributors, Set Difference With Set Difference Is Union of Set Difference With Intersection — Proof Wiki].

Item 11: Left Annihilation

The direction $\text{Ø}\subset \text{Ø}\setminus U$ always holds. Now assume $x \in \text{Ø}\setminus U$. Then, $x \in \text{Ø}$ and $x \not\in U$. Hence $\text{Ø}\setminus U \subset \text{Ø}$ must hold and the sets are equal.

Item 12: Right Unitality

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

Item 13: Right Annihilation

It suffices to show that no $x \in X$ can be an element of $U \setminus X$. Assume $x \in U \setminus X$. Then $x \not\in X$, contradicting $x \in X$. This completes the proof.

Item 14: Invertibility

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

Item 15: Interaction With Containment

The conditions are symmetric in $U,W$, hence it suffices to show that $V \setminus U \subset W$ implies $V \setminus W \subset U$. So assume $V \setminus U \subset W, x \in V \setminus W$. Then $x \in V, x \not\in W$. So by contraposition, $x \not\in V \setminus U$. But $x \in V$, so we must have $x \in U$, completing the proof.

Item 16: Interaction With Characteristic Functions

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

Item 17: Interaction With Direct Images

See [Proof Wiki Contributors, Image of Set Difference Under Mapping — Proof Wiki].

Item 18: Interaction With Inverse Images

See [Proof Wiki Contributors, Preimage of Set Difference Under Mapping — Proof Wiki].