Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
1  
Your $(A ∪ B) - (A ∩ B)$ is called a symmetric difference. –  draks ... Jul 24 '12 at 9:24
1  
And your first identity is incorrect. –  Tapu Jul 24 '12 at 9:26
1  
@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
show 1 more comment

3 Answers

up vote 2 down vote accepted

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$

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

share|improve this answer
add comment

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).

share|improve this answer
1  
@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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.