# Applying the symmetric difference to multiple sets

I was working on set theory and I came across a rule: $$(A\cup B) - (A\cap B) = (A\cap B)'$$

I have 4 sets $A$, $B$, $C$, $D$. How can I apply the rule above to all set at same time? is the below mentioned result mathematically correct? $$(A\cup B\cup C\cup D) - (A\cap B\cap C\cap D) = (A\cap B\cap C\cap D)'$$

Regards,

-
Your $(A ∪ B) - (A ∩ B)$ is called a symmetric difference. – draks ... Jul 24 '12 at 9:24
And your first identity is incorrect. – Tapu Jul 24 '12 at 9:26
@draks: thanks a ton. It helped me. Kindly put it as an answer so I can mark it :) :) – Priyank Thakkar Jul 24 '12 at 9:30
@Tapu why? ${ }$ – draks ... Jul 24 '12 at 9:32
@PriyankThakkar you're welcome (to Math.StackExchange.com ;-) – draks ... Jul 24 '12 at 9:37

If by $(\cdots)'$ you denote the complement of $(\cdots)$, $$(A ∪ B) - (A ∩ B) = (A\cap B)'$$ which is corresponds to the symmetric difference $A\,\triangle\,B\,$. As pointed by Martin your second equation is also just a way of writing the complement.

And, as already pointed out by Tapu, for multiple sets the $(\cap_k A_k )' \neq \triangle_k A_k$.

$\hskip2.7in$

Venn diagram of $~A \triangle B \triangle C$

-

If you want a talk about complement of a set, you have first to state what is the universe $U$ you are working with. If you choose a universe then the complement of $A$ is $A'=U\setminus A$.

So if $U=A\cup B$ then $(A\cap B)'=U\setminus (A\cap B)$ and if $U=A\cup B\cup C\cup D$ then $(A\cap B\cap C\cap D)'=A\cup B\cup C\cup D\setminus (A\cap B\cap C\cap D)$.

So your formula is just the definition of complement, if the universe you're working with is $U=A\cup B$ in the first case and $U=A\cup B\cup C\cup D$ in the second one.

If you work with a different universe $U\supsetneqq A\cup B\cup C\cup D$, then the equality you wrote is not correct (and neither is the first one).

-
@Marting Sleziak: I didn't use proper math terminology. What I exactly wanted to ask was how to apply Symmetric difference to multiple set. Thanks for the guidance :) – Priyank Thakkar Jul 24 '12 at 9:37

If we let $\triangle$ denote the symmetric difference of two sets, $$A\triangle B = (A\cup B) - (A\cap B) = (A-B)\cup(B-A),$$ then we have:

Theorem. If $A_1,\ldots,A_n$ are sets, then \begin{align*} x\in (A_1\triangle\cdots\triangle A_{n-1})\triangle A_n&\iff x\text{ is in exactly an odd number of }A_i\\ &\iff \Bigl|\{i\mid 1\leq i\leq n, x\in A_i\}\Bigr|\text{ is odd.} \end{align*}

Proof. We proceed by induction on $n$. The result is true if $n=1$ or $2$. Assume the result holds for $k$. Then $x\in (A_1\triangle \cdots\triangle A_n)\triangle A_{n+1}$ if and only if $x$ is in exactly one of $A_1\triangle\cdots\triangle A_n$ and $A_{n+1}$.

If $x$ lies in an even number of sets from among $A_1,\ldots,A_{n+1}$, then it either lies in an even number of sets from among $A_1,\ldots,A_n$ and not in $A_{n+1}$, in which case it lies in neither $A_1\triangle\cdots\triangle A_n$ (by the induction hypothesis) nor in $A_{n+1}$, hence not in the symmetric difference; or else it lies in an odd number of sets from among $A_1,\ldots,A_n$ (and hence lies in $A_1\triangle\cdots\triangle A_n$ by the induction hypothesis) and in $A_{n+1}$, and so it does not lie in the symmetric difference (since it lies in both operands).

If $x$ lies in an odd number of sets from among $A_1,\ldots,A_{n+1}$, then it either lies in an even number of sets from among $A_1,\ldots,A_n$ (and hence not in $A_1\triangle\cdots\triangle A_n$), and in $A_{n+1}$; or it lies in an odd number of sets from among $A_1,\ldots,A_n$ and not in $A_{n+1}$. Either way, it lies in exactly one of $A_1\triangle\cdots\triangle A_n$ and $A_{n+1}$, hence lies in $(A_1\triangle\cdots\triangle A_n)\triangle A_{n+1}$.

Thus, $x\in (A_1\triangle\cdots\triangle A_n)\triangle A_{n+1}$ if and only if it lies in exactly an odd number of sets from among $A_1,\ldots,A_{n+1}$. $\Box$

Moreover, since $(A\triangle B)\triangle C = A\triangle(B\triangle C)$ for all $A$, $B$, and $C$ (it follows easily from the theorem, or from truth tables), we can dispense with the parentheses.

Essentially, the characteristic function of the symmetric difference is the sum, modulo $2$, of the characteristic functions of the two sets: $$1_{A\triangle B} = 1_A\oplus 1_B,\qquad \oplus=\text{addition modulo }2.$$

-