# How to prove that symmetric difference of intersections is a subset of unions of symmetric differences

I need to prove that: $$(A_1\cap A_2\cap ...\cap A_n) \Delta (B_1\cap B_2\cap ...\cap B_n) \subset (A_1\Delta B_1) \cup (A_2\Delta B_2)\cup...\cup(A_n\Delta B_n)$$ and show that inverse statement is not correct. But, appling the symmetric difference formulas doesn't really helps. For left side for the case of $(A_1\cap A_2) \Delta (B_1\cap B_2)$ I get $(A_1\cap A_2)\setminus(B_1\cap B_2)\cup(B_1\cap B_2)\setminus(A_1\cap A_2)$, and for the right side I get $(A_1\setminus B_1)\cup (B_1\setminus A_1)\cup (A_2\setminus B_2)\cup (B_2\setminus A_2)$, but it doesn't help much. Anyway, I gets worse in case if I add $A_3$ and $B_3$ to the statement, as the formula becomes more complicated.

Thanks Martin Sleziak for the formula! I didn't know it before. It seems like using De Morgan's law can help. The left side: $$(A_1\cap A_2 \cap A_3)\Delta(B_1\cap B_2 \cap B_3) = ( A_1\cap A_2 \cap A_3)\cap (B_1\cap B_2 \cap B_3)' \cup ( A_1\cap A_2 \cap A_3)'\cap (B_1\cap B_2 \cap B_3) = ( A_1\cap A_2 \cap A_3)\cap (B_1'\cup B_2' \cup B_3') \cup ( A_1'\cup A_2'\cup A_3')\cap (B_1\cap B_2 \cap B_3) = (B_1'\cap A_1\cap A_2 \cap A_3) \cup (B_2'\cap A_1\cap A_2 \cap A_3) \cup (B_3'\cap A_1\cap A_2 \cap A_3) \cup (A_1'\cap B_1\cap B_2 \cap B_3) \cup (A_2'\cap B_1\cap B_2 \cap B_3)\cup (A_3'\cap B_1\cap B_2 \cap B_3)$$ while the right side is: $$(A_1\Delta B_1) \cup (A_2\Delta B_2) \cup (A_3\Delta B_3) = (B_1'\cap A_1) \cup (A_1'\cap B_1) \cup (B_2'\cap A_2) \cup (A_2'\cap B_2) \cup (B_3'\cap A_3) \cup (A_3'\cap B_3)$$ As you can see, there are 6 terms on both sides. Moreover, each term from the left side has a pair on the right side: $(A_3'\cap B_1\cap B_2 \cap B_3)$ and $(A_3'\cap B_3)$, and so on. I think, that the following is correct $(A_3'\cap B_3\cap B_2 \cap B_1) \subseteq (A_3'\cap B_3)$, because the additional intersection with $B_2\cap B_3$ can only reduce (or left unchanged) the size of $(A_3'\cap B_3)$. So, the left side of the equation is a subset of the right. Here I show that both left and right sides can be equal in some cases, but the original equation is strict. Why did that happen?

-
Here I show that both left and right sides can be equal in some cases, but the original equation is strict. Why did that happen? This seems to be notational issue. Some people use $\subset$ to denote strict inclusion and in some text this symbols means inclusion. Obviously for $A_1=\dots=A_n$ and $B_1=\dots=B_n$ you have equality. –  Martin Sleziak Oct 9 '12 at 11:35
Yes, sure, you are right. Thanks again. –  Kos Oct 9 '12 at 13:04

You can express symmetric difference as $$X\triangle Y = (X\cap Y') \cup (X'\cap Y),$$ where $X'$ denotes the complement of the set $X$.

This gives $$(A_1\cap\dots\cap A_n)\triangle(B_1\cap\dots\cap B_n)= [(A_1\cap\dots\cap A_n)\cap (B_1\cap\dots\cap B_n)'] \cup [(A_1\cap\dots\cap A_n)\cap(B_1\cap\dots\cap B_n)'].$$

Do you know some expression for $(X_1\cap\dots X_n)'$? If you use this expression, can you somehow simplify the result?

-
Thanks for the formula and the idea. I've updated the post to reflect the solution, which I came up using your suggestion. Thanks again. –  Kos Oct 9 '12 at 11:04

This kind of result is often most easily proved by ‘element-chasing’: let $x$ be any element of the set on the lefthand side, and show that $x$ must be an element of the set on the righthand side. (If you were proving an equality, instead of an inclusion, you’d then repeat the process in the other direction.)

So suppose that $x\in(A_1\cap A_2\cap\ldots\cap A_n)\triangle(B_1\cap B_2\cap\ldots\cap B_n)$. Then either $$x\in A_1\cap A_2\cap\ldots\cap A_n\quad\text{and}\quad x\notin B_1\cap B_2\cap\ldots\cap B_n\;,\tag{1}$$ or $$x\in B_1\cap B_2\cap\ldots\cap B_n\quad\text{and}\quad x\notin A_1\cap A_2\cap\ldots\cap A_n\;.\tag{2}$$ The two cases are entirely similar, so let’s assume $(1)$.

Since $x\notin B_1\cap B_2\cap\ldots\cap B_n$, there is some $k\in\{1,\dots,n\}$ such that $x\notin B_k$. But $x\in A_k$, so ... ?

-