Prove that $ (A_1 \cap \dots \cap A_n) \triangle (B_1 \cap \dots \cap B_n) \subset (A_1 \triangle B_1) \cup \dots \cup (A_n \triangle B_n) $

Question

Prove that $ (A_1 \cap \dots \cap A_n) \triangle (B_1 \cap \dots \cap B_n) \subset (A_1 \triangle B_1) \cup \dots \cup (A_n \triangle B_n) $ is true for any sets $A_1, \dots , A_n$ and $B_1, \dots , B_n $

I tried to solve it using math induction.

n = 1: $A_1 \triangle B_1 \subset A_1 \triangle B_1$ is true

n = m: $ (A_1 \cap \dots \cap A_m) \triangle (B_1 \cap \dots \cap B_m) \subset (A_1 \triangle B_1) \cup \dots \cup (A_m \triangle B_m) $

n = m + 1: $ (A_1 \cap \dots \cap A_m) \triangle (B_1 \cap \dots \cap B_m) \cup A_{m+1} \triangle B_{m+1} \subset (A_1 \triangle B_1) \cup \dots \cup (A_{m+1} \triangle B_{m+1})$

But I have no idea what to do next

Answer 1

You can prove it directly by element-chasing; using induction just overcomplicates matters. Suppose that $x\in\left(\bigcap_{k=1}^nA_k\right)\triangle\left(\bigcap_{k=1}^nB_k\right)$; then either $x\in\left(\bigcap_{k=1}^nA_k\right)\setminus\left(\bigcap_{k=1}^nB_k\right)$, or $x\in\left(\bigcap_{k=1}^nB_k\right)\setminus\left(\bigcap_{k=1}^nA_k\right)$. Without loss of generality we may assume that $x\in\left(\bigcap_{k=1}^nA_k\right)\setminus\left(\bigcap_{k=1}^nB_k\right)$. Then $x\in\bigcap_{k=1}^nA_k$, so $x\in A_k$ for $k=1,\ldots,n$, and $x\notin\bigcap_{k=1}^nB_k$, so there is an $\ell\in\{1,\ldots,n\}$ such that $x\notin B_\ell$. But then $x\in A_\ell\setminus B_\ell\subseteq A_\ell\triangle B_\ell\subseteq\bigcup_{k=1}^n(A_k\triangle B_k)$, and since $x$ was an arbitrary element of $\left(\bigcap_{k=1}^nA_k\right)\triangle\left(\bigcap_{k=1}^nB_k\right)$, we conclude that $\left(\bigcap_{k=1}^nA_k\right)\triangle\left(\bigcap_{k=1}^nB_k\right)\subseteq\bigcup_{k=1}^n(A_k\triangle B_k)$, as desired.

Answer 2

Notice that $$A\triangle B=(A\setminus B) \cup (B\setminus A) = (A\cap B^c)\cup(B\cap A^c)=A^c\triangle B^c $$

So

$$\Big(\bigcap^n_{k=1} A_k\Big)\triangle \Big(\bigcap^n_{j=1}B_j\Big)= \Big(\bigcup^n_{k=1} A^c_k\Big)\triangle \Big(\bigcup^n_{j=1}B^c_j\Big)$$

Now, using distributive properties of union and intersection, i.e., $C\cap\Big(\bigcup_\alpha D_\alpha\Big)=\bigcup_\alpha (D_\alpha \cap C)$, we obtain that

$$ \begin{align} \Big(\bigcup^n_{k=1} A^c_k\Big)\triangle \Big(\bigcup^n_{j=1}B^c_j\Big)&= \left(\Big(\bigcup^n_{k=1}A^c_k\Big)\setminus\Big(\bigcup^n_{j=1}B^c_j\Big)\right)\cup \left(\Big(\bigcup^n_{j=1}B^c_j\Big)\setminus\Big(\bigcup^n_{k=1}A^c_k\Big)\right)\\ &= \left(\Big(\bigcup^n_{k=1}A^c_k\Big)\cap\bigcap^n_{j=1}B_j\right)\cup \left(\Big(\bigcup^n_{j=1}B^c_j\Big)\cap\bigcap^n_{k=1}A_k\right)\\ &=\left(\bigcup^n_{k=1}\Big(A^c_k\cap\bigcap^n_{j=1}B_j\Big)\right) \cup \left(\bigcup^n_{j=1}\Big(B^c_j\cap\bigcap^n_{k=1}A_k\Big)\right) \\ &\subset \left(\bigcup^n_{k=1}\Big(A^c_k\cap B_k\Big)\right) \cup \left(\bigcup^n_{j=1}\Big(B^c_j\cap A_j\Big)\right)\\ &=\bigcup^n_{k=1}\big((B_k\setminus A_k)\cup (A_k\setminus B_k)\big)=\bigcup^n_{k=1}A_k\triangle B_k \end{align} $$