PlanetMath: symmetric difference on a finite number of sets

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

. Let

and

be the identity and complementation operations taking $A\subseteq U$ to

and

respectively. Let $\mathbf{n}$ be the set $\lbrace 1,\ldots, n\rbrace$ . Let

be the set of all functions from $\mathbf{n}$ into $\lbrace I,C\rbrace$ . For every $f\in F_n$ , we write

for

. Finally, we partition

into two sets

and

, where

(

) consists of all functions

such that $\vert f^{-1}(I)\vert$ is even (odd), respectively.

Proof. We prove this equation by induction on

, for $n\ge 2$ . The case when

is already discussed above. Now,

$\displaystyle \displaystyle{\substack{ {n+1} \\ \displaystyle{\Delta} \\ {i=1} ... ...{ {n} \\ \displaystyle{\Delta} \\ {i=1} } A_i}\right) \Delta A_{n+1} = X\cup Y,$

where

$\displaystyle X = \left(\displaystyle{\substack{ {n} \\ \displaystyle{\Delta} \\ {i=1} } A_i}\right)\cap A'_{n+1}$ and $\displaystyle \qquad Y= A_{n+1} \cap \left( \displaystyle{\substack{ {n} \\ \displaystyle{\Delta} \\ {i=1} } A_i}\right)'.$

By the induction hypothesis,

$\displaystyle \displaystyle{\substack{ {n} \\ \displaystyle{\Delta} \\ {i=1} } A_i} = \bigcup_{f\in O_n} \bigcap_{i=1}^n f_i(A_i),$

so that

$\displaystyle X = \bigg( \bigcup_{f\in O_n} \bigcap_{i=1}^n f_i(A_i) \bigg) \cap A'_{n+1} = \bigcup_{f\in O_n} \bigcap_{i=1}^{n+1} \hat{f}_i(A_i),$

where $\hat{f}:\mathbf{(n+1)}\to \lbrace I,C\rbrace$ 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$ , is either in an even number of 's, or an odd number of 's. This means that

$\displaystyle x\in \bigcup_{f\in E_n} \bigcap_{i=1}^n f_i(A_i)$ or $\displaystyle \qquad x\in \bigcup_{f\in O_n} \bigcap_{i=1}^n f_i(A_i)$

and never both. This shows that

can be partitioned into the two sets above. In other words,

$\displaystyle \left( \bigcup_{f\in O_n} \bigcap_{i=1}^n f_i(A_i) \right)' = \bigcup_{f\in E_n} \bigcap_{i=1}^n f_i(A_i).$

As a result,

$\displaystyle 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 \lbrace I,C\rbrace$ 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 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 and , where (or ) contains all functions whose restriction to $\mathbf{n}$ are in (or ).

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}.$

$\qedsymbol$