3
$\begingroup$

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,

  • 1
    Your $(A ∪ B) - (A ∩ B)$ is called a [symmetric difference](http://en.wikipedia.org/wiki/Symmetric_difference).2012-07-24
  • 1
    And your first identity is incorrect.2012-07-24
  • 1
    @draks: thanks a ton. It helped me. Kindly put it as an answer so I can mark it :) :)2012-07-24
  • 0
    @PriyankThakkar you're welcome (to Math.StackExchange.com ;-)2012-07-24
  • 0
    @draks the comment is meant to OP. Certainly $(A\cap B)'\ne(A\Delta B)$, if there are other sets involved.2012-07-24
  • 0
    If other sets are involved, then what is https://www.wolframalpha.com/input/?i=A+XOR+B+XOR+C+XOR+(A+AND+B+AND+C) ? Does it have a special name?2016-09-07

3 Answers 3

3

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 <span class=$~A \triangle B \triangle C$">

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

5

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

3

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

  • 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 :)2012-07-24
  • 0
    What do you call this? https://www.wolframalpha.com/input/?i=A+XOR+B+XOR+C+XOR+(A+AND+B+AND+C) ? Does it have a special name for it?2016-09-07
  • 0
    @lifebalance How does this relate to this post? Perhaps you wanted to ask a new question instead of posting a comment? You can also [ask in chat](http://chat.stackexchange.com/rooms/info/36/mathematics) if you do not want to post it as a question on this site.2016-09-07
  • 0
    @Martin Symmetric difference must also eliminate those that are NOT unique to two or more sets, right? At least, that is what my naive intuition informs me...and therefore I thought it relevant to post here...in case, I have moved on to the chat as suggested by you.2016-09-07