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,

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

  • 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