# symmetric difference on a finite number of sets

Recall that the symmetric difference^{} operation^{} on sets is commutative^{} and associative. Therefore, one can speak of the symmetric difference of a finite collection^{} of sets. More precisely, let ${A}_{1},{A}_{2},\mathrm{\dots},{A}_{n}$ be sets, not necessarily pairwise distinct. The set

$$A:=\begin{array}{c}n\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i},$$ |

the symmetric difference of the sets ${A}_{i}$, is well-defined.

Let $A,{A}_{1},\mathrm{\dots},{A}_{n}$ be defined as above. There is a curious property on $A$:

###### Proposition 1.

$x\in A$ iff $x$ belongs to an odd number of the sets ${A}_{i}$.

Before proving this fact, let us make some quick observations. If there are two sets ${A}_{1},{A}_{2}$, then $A={A}_{1}\mathrm{\Delta}{A}_{2}=({A}_{1}\cap {A}_{2}^{\prime})\cup ({A}_{1}^{\prime}\cap {A}_{2})$ (here we are assuming that ${A}_{1}$ and ${A}_{2}$ are subsets of some universe^{} $U$, so the the complement^{} makes sense). So $x\in A$ iff $x\in {A}_{1}\cap {A}_{2}^{\prime}$ or $x\in {A}_{1}^{\prime}\cap {A}_{2}$ iff $x\in {A}_{1}$ or $x\in {A}_{2}$, which conforms with the statement of the proposition^{} above. If $n=3$, then $A$ has conjunctive normal form^{}

$${A}_{1}\mathrm{\Delta}{A}_{2}\mathrm{\Delta}{A}_{3}=({A}_{1}\cap {A}_{2}\cap {A}_{3})\cup ({A}_{1}\cap {A}_{2}^{\prime}\cap {A}_{3}^{\prime})\cup ({A}_{1}^{\prime}\cap {A}_{2}\cap {A}_{3}^{\prime})\cup ({A}_{1}^{\prime}\cap {A}_{2}^{\prime}\cap {A}_{3}),$$ |

(for a proof of this, see here (http://planetmath.org/ProofOfTheAssociativityOfTheSymmetricDifferenceOperator)). Then $x\in A$ iff $x$ belongs any one of the four intersections^{} in the CNF above. In each of the four cases, $x$ belongs to an odd number of sets. For example, if $x\in {A}_{1}\cap {A}_{2}^{\prime}\cap {A}_{3}^{\prime}$, then $x\in {A}_{1}$.

From the two examples above, it seems that the approach to proving the proposition is to express the symmetric difference in CNF, and this is indeed the case.

To facilitate with the proof, let us introduce some notations. Start with sets ${A}_{1},\mathrm{\dots},{A}_{n}$, which are assumed to be subsets of some set $U$. Let $I$ and $C$ be the identity^{} and complementation operations taking $A\subseteq U$ to $A$ and ${A}^{\prime}$ respectively. Let $\mathbf{n}$ be the set $\{1,\mathrm{\dots},n\}$. Let ${F}_{n}$ be the set of all functions from $\mathbf{n}$ into $\{I,C\}$. For every $f\in {F}_{n}$, we write ${f}_{i}$ for $f(i)$. Finally, we partition ${F}_{n}$ into two sets ${E}_{n}$ and ${O}_{n}$, where ${E}_{n}$ (${O}_{n}$) consists of all functions $f$ such that $|{f}^{-1}(I)|$ is even (odd), respectively.

The proposition can now be restated as a single equation:

$$\begin{array}{c}n\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i}=\bigcup _{f\in {O}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i})$$ |

###### Proof.

We prove this equation by induction^{} on $n$, for $n\ge 2$. The case when $n=2$ is already discussed above. Now,

$$\begin{array}{c}n+1\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i}=\left(\begin{array}{c}n\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i}\right)\mathrm{\Delta}{A}_{n+1}=X\cup Y,$$ |

where

$$X=\left(\begin{array}{c}n\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i}\right)\cap {A}_{n+1}^{\prime}\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}Y={A}_{n+1}\cap {\left(\begin{array}{c}n\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i}\right)}^{\prime}.$$ |

By the induction hypothesis,

$$\begin{array}{c}n\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i}=\bigcup _{f\in {O}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i}),$$ |

so that

$$X=\left(\bigcup _{f\in {O}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i})\right)\cap {A}_{n+1}^{\prime}=\bigcup _{f\in {O}_{n}}\bigcap _{i=1}^{n+1}{\widehat{f}}_{i}({A}_{i}),$$ |

where $\widehat{f}:(\mathbf{n}+\mathrm{\U0001d7cf})\to \{I,C\}$ is given by ${\widehat{f}}_{i}={f}_{i}$ if $i\in \mathbf{n}$, and ${\widehat{f}}_{n+1}=C$.

Now, for any $x\in U$, $x$ is either in an even number of ${A}_{i}$’s, or an odd number of ${A}_{i}$’s. This means that

$$x\in \bigcup _{f\in {E}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i})\mathit{\hspace{1em}\hspace{1em}}\text{or}\mathit{\hspace{1em}\hspace{1em}}x\in \bigcup _{f\in {O}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i})$$ |

and never both. This shows that $U$ can be partitioned into the two sets above. In other words,

$${\left(\bigcup _{f\in {O}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i})\right)}^{\prime}=\bigcup _{f\in {E}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i}).$$ |

As a result,

$$Y={A}_{n+1}\cap \left(\bigcup _{f\in {E}_{n}}\bigcap _{i=1}^{n}{f}_{i}({A}_{i})\right)=\bigcup _{f\in {E}_{n}}\bigcap _{i=1}^{n+1}{\overline{f}}_{i}({A}_{i}),$$ |

where $\overline{f}:(\mathbf{n}+\mathrm{\U0001d7cf})\to \{I,C\}$ is given by ${\overline{f}}_{i}={f}_{i}$ if $i\in \mathbf{n}$, and ${\widehat{f}}_{n+1}=I$.

Every function $g\in {O}_{n+1}$ can be obtained from a function in $f\in {F}_{n}$ so that ${g}_{i}={f}_{i}$ for $i\in \mathbf{n}$. If $f\in {O}_{n}$, then ${g}_{n+1}=C$, and if $f\in {E}_{n}$, then ${g}_{n+1}=I$. This means that ${O}_{n+1}$ can be partitioned into two sets $O$ and $E$, where $O$ (or $E$) contains all functions whose restriction^{} to $\mathbf{n}$ are in ${O}_{n}$ (or ${E}_{n}$).

Therefore,

$\bigcup _{g\in {O}_{n+1}}}{\displaystyle \bigcap _{i=1}^{n+1}}{g}_{i}({A}_{i})$ | $=$ | $\left({\displaystyle \bigcup _{g\in O}}{\displaystyle \bigcap _{i=1}^{n+1}}{g}_{i}({A}_{i})\right)\cup \left({\displaystyle \bigcup _{g\in E}}{\displaystyle \bigcap _{i=1}^{n+1}}{g}_{i}({A}_{i})\right)$ | ||

$=$ | $\left({\displaystyle \bigcup _{f\in {O}_{n}}}{\displaystyle \bigcap _{i=1}^{n+1}}{\widehat{f}}_{i}({A}_{i})\right)\cup \left({\displaystyle \bigcup _{f\in {E}_{n}}}{\displaystyle \bigcap _{i=1}^{n+1}}{\overline{f}}_{i}({A}_{i})\right)$ | |||

$=$ | $X\cup Y=\begin{array}{c}n+1\\ \mathrm{\Delta}\\ i=1\end{array}{A}_{i}.$ |

∎

Title | symmetric difference on a finite number of sets |
---|---|

Canonical name | SymmetricDifferenceOnAFiniteNumberOfSets |

Date of creation | 2013-03-22 18:02:24 |

Last modified on | 2013-03-22 18:02:24 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 8 |

Author | CWoo (3771) |

Entry type | Derivation |

Classification | msc 03E20 |