## You are here

Homesymmetric difference on a finite number of sets

## Primary tabs

# 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},\ldots,A_{n}$ be sets, not necessarily pairwise distinct. The set

$A:=\displaystyle{\substack{{n}\\ \displaystyle{\Delta}\\ {i=1}}A_{i}},$ |

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

Let $A,A_{1},\ldots,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}\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}\Delta A_{2}\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). 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},\ldots,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,\ldots,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:

$\displaystyle{\substack{{n}\\ \displaystyle{\Delta}\\ {i=1}}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\geq 2$. The case when $n=2$ is already discussed above. Now,

$\displaystyle{\substack{{n+1}\\ \displaystyle{\Delta}\\ {i=1}}A_{i}}=\left(\displaystyle{\substack{{n}\\ \displaystyle{\Delta}\\ {i=1}}A_{i}}\right)\Delta A_{{n+1}}=X\cup Y,$ |

where

$X=\left(\displaystyle{\substack{{n}\\ \displaystyle{\Delta}\\ {i=1}}A_{i}}\right)\cap A^{{\prime}}_{{n+1}}\qquad\mbox{and}\qquad Y=A_{{n+1}}% \cap\left(\displaystyle{\substack{{n}\\ \displaystyle{\Delta}\\ {i=1}}A_{i}}\right)^{{\prime}}.$ |

By the induction hypothesis,

$\displaystyle{\substack{{n}\\ \displaystyle{\Delta}\\ {i=1}}A_{i}}=\bigcup_{{f\in O_{n}}}\bigcap_{{i=1}}^{n}f_{i}(A_{i}),$ |

so that

$X=\bigg(\bigcup_{{f\in O_{n}}}\bigcap_{{i=1}}^{n}f_{i}(A_{i})\bigg)\cap A^{{% \prime}}_{{n+1}}=\bigcup_{{f\in O_{n}}}\bigcap_{{i=1}}^{{n+1}}\hat{f}_{i}(A_{i% }),$ |

where $\hat{f}:\mathbf{(n+1)}\to\{I,C\}$ is given by $\hat{f}_{i}=f_{i}$ if $i\in\mathbf{n}$, and $\hat{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})\qquad\mbox{or}\qquad 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+1)}\to\{I,C\}$ is given by $\overline{f}_{i}=f_{i}$ if $i\in\mathbf{n}$, and $\hat{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,

$\displaystyle\bigcup_{{g\in O_{{n+1}}}}\bigcap_{{i=1}}^{{n+1}}g_{i}(A_{i})$ | $\displaystyle=$ | $\displaystyle\bigg(\bigcup_{{g\in O}}\bigcap_{{i=1}}^{{n+1}}g_{i}(A_{i})\bigg)% \cup\bigg(\bigcup_{{g\in E}}\bigcap_{{i=1}}^{{n+1}}g_{i}(A_{i})\bigg)$ | ||

$\displaystyle=$ | $\displaystyle\bigg(\bigcup_{{f\in O_{n}}}\bigcap_{{i=1}}^{{n+1}}\hat{f}_{i}(A_% {i})\bigg)\cup\bigg(\bigcup_{{f\in E_{n}}}\bigcap_{{i=1}}^{{n+1}}\overline{f}_% {i}(A_{i})\bigg)$ | |||

$\displaystyle=$ | $\displaystyle X\cup Y=\displaystyle{\substack{{n+1}\\ \displaystyle{\Delta}\\ {i=1}}A_{i}}.$ |

∎

## Mathematics Subject Classification

03E20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## SymDiff = +

Just a comment, as I spent some time on this once, but it may ease things at some point to observe that the symmetric difference is just the natural field or ring operation usually signified by "+", and so it inherits all of the usual properties of that. JA

## Re: SymDiff = +

Yes I realize that. But I am not sure how that would help in proving the proposition...

## Re: SymDiff = +

There's a discussion in this old application paper of mine:

http://www.mywikibiz.com/Directory:Jon_Awbrey/Papers/Differential_Logic_...

Let B = {0, 1}

Let x_i for i = 1 to n be the characteristic functions

of the sets A_i, i = 1 to n, all subsets of universe X.

Consider the "factoring" of a proposition f : X -> B,

where f is 1 of the 2^(2^n) functions based on the x_i,

as the composite function f*(c(x)), where c : X -> B^n

is the "coding" of each x in X as an n-bit string in B^n,

and where f* is the mapping of these code n-tuples into B.

............ X ... f ... B

............. o-------->o

.............. \ ..... ^

{x_1, ..., x_n) \ ... / f*

................ \ . /

................. v /

.................. o

................. B^n

There are 2^n linear functions h : B^n -> B,

with (n choose k) linear functions of rank k,

for k = 0 to n.

These linear functions are the same things as the

symmmetric differences of rank k, for k = 0 to n.

A typical one can be written as a k-fold sum,

x_i_1 + x_1_2 + ... x_i_(k-1) + x_i_k, where

"+" signifies the GF(2) addition, also known

as exclusive disjunction (XOR) or Sym.Diff.

I hope I got this right -- it's been a while.

(You may have to insert leading spaces into

the diagram in order to make it display right.)