Associativity of symmetric difference of sets
In that post it said the symmetric difference is $$1_{A\mathbin{\Delta} B} = 1_A + 1_B – 1_{A\cap B}$$
Why is it not $$1_{A\mathbin{\Delta} B}=1_A+1_B-2(1_{A\cap B})$$
I can't really see why.
[Math] Symmetric difference and indicator function
elementary-set-theory
Related Solutions
As Asaf said in the comments, this is bookkeeping and induction. I’m going to write out the induction step in full, but I’m going to do it in a very compact fashion that may not be easy to follow at first. I’m doing this for two reasons. First, you really ought to try to work out the induction step on your own, so I don’t want to make it too easy to read. (If you have trouble doing it in general, I suggest writing out the argument for $n=3$ and perhaps $n=4$ first; at that point you should be able to see fairly clearly what’s going on, and the main problem will likely be expressing it clearly in the general case.) Secondly, at some point you’ll want to get used to reading this sort of compact argument.
First let’s write out the sum in full:
$$\left|\bigoplus_{k=1}^nA_k\right|=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\left|\bigcap_{i\in S}A_i\right|\;,\tag{1}$$
where I’ve used $\oplus$ for symmetric difference, and $[n]=\{1,\dots,n\}$. To avoid having too many subscripts, let $\chi_k$ be the characteristic function of $A_k$, and let $\varphi_n$ be the characteristic function of $\bigoplus_{k=1}^nA_k$. Then $(1)$ will certainly be true if
$$\varphi_n=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\;,\tag{2}$$
since $\prod_{i\in S}\chi_i$ is the characteristic function of $\bigcap_{i\in S}A_i$.
You can prove $(2)$ by induction on $n$. You need to use the fact that for any characteristic function $\chi$, $\chi^2=\chi$. You already know that $\chi_{A\oplus B}=(\chi_A-\chi_B)^2$. Now for the induction step you have
$$\begin{align*} \varphi_{n+1}&=\left(\varphi_n-\chi_{n+1}\right)^2\\ &=\varphi_n^2+\chi_{n+1}^2-2\varphi_n\chi_{n+1}\\ &=\varphi_n+\chi_{n+1}-2\varphi_n\chi_{n+1}\\ &=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i+\chi_{n+1}-2\chi_{n+1}\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\tag{3} \end{align*}$$
for starters. The first term in $(3)$ can be split as
$$\sum_{i\in[n]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\tag{4}$$
and the first term of $(4)$ can be combined with the $\chi_{n+1}$ term in $(3)$ to yield
$$\begin{align*} \varphi_{n+1}&=\sum_{i\in[n+1]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i-2\chi_{n+1}\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\\ &=\sum_{i\in[n+1]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i-2\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\chi_{n+1}\tag{5}\;. \end{align*}$$
Now let $S$ be a subset of $[n+1]$ such that $|S|=k$. If $k=1$, then $\prod_{i\in S}$ is one of the $\chi_i$, and it appears in the first term of $(5)$ with coefficient $1=(-1)^02^0=(-1)^{k-1}2^{k-1}$.
Suppose now that $1<k\le n$. If $n+1\notin S$, $\prod_{i\in S}\chi_i$ is counted in the second term of $(5)$, where it appears with coefficient $(-1)^{k-1}2^{k-1}$. If $n+1\in S$, then $\prod_{i\in S}\chi_i$ appears in the last term of $(5)$ as $\prod_{i\in S'}\chi_i\chi_{n+1}$, where $S'=S\setminus\{n+1\}$, and $|S'|=k-1$. In this case the coefficient of $\prod_{i\in S}\chi_i$ is $-2(-1)^{k-2}2^{k-2}=(-1)^{k-1}2^{k-1}$.
Finally, suppose that $k=n+1$. Then $S=[n+1]$, and $\prod_{i\in S}\chi_i=\prod_{i\in[n]}\chi_i\chi_{n+1}$ appears in the last term of $(5)$ with coefficient $-2(-1)^{n-1}2^{n-1}=(-1)^n2^n=(-1)^{k-1}2^{k-1}$.
It follows that $(5)$ (and hence $\varphi_{n+1}$) is equal to
$$\sum_{k=1}^{n+1}(-1)^{k-1}2^{k-1}\sum_{S\subset[n+1]\atop|S|=k}\prod_{i\in S}\chi_i\;,$$
which completes the induction step.
By the way, a simpler approach is to show that $a\in\bigoplus_{k=1}^nA_k$ iff $|\{k\in[n]:a\in A_k\}|$ is odd, which is an easy induction, and then to show that that the righthand side of $(1)$ counts the elements of $\bigcup_{k=1}^nA_k$ that are in an odd number of the $A_k$. This is a fairly easy consequence of the binomial theorem. If an element $a$ is in exactly $m$ of the $n$ sets, for each $k$ from $1$ through $m$ it’s in $\binom{m}k$ $k$-fold intersections, so it contributes
$$\begin{align*} \sum_{k=1}^m\binom{m}k(-1)^{k-1}2^{k-1}&=-\frac12\sum_{k=1}^m\binom{m}k(-2)^k\\ &=-\frac12\left(\sum_{k=0}^m\binom{m}k(-2)^k-1\right)\\ &=\frac12\Big(1-(1-2)^m\Big)\\ &=\frac{1-(-1)^m}2\\ &=\begin{cases} 1,&\text{if }m\text{ is odd}\\ 0,&\text{if }m\text{ is even} \end{cases} \end{align*}$$
to the righthand side of $(1)$.
If $\chi_U$ denotes the characteristic function of the set $U$, then we have $\chi_{A\Delta B} = |\chi_A - \chi_B|$. Hence we have \begin{align*} \mathbb{P}(A\Delta C) &= \int |\chi_A - \chi_C| d\mu \\ &= \int |(\chi_A - \chi_B) + (\chi_B - \chi_C)| d\mu \\ &\leq \int (|\chi_A - \chi_B| + |\chi_B - \chi_C|) d\mu \\ &= \int (|\chi_A - \chi_B|d\mu + \int |\chi_B - \chi_C|) d\mu\\ &= \mathbb{P}(A\Delta B) + \mathbb{P}(B\Delta C) \end{align*}
Best Answer
You are correct.
On $A\cap B$, the idicator function of $A\mathbin\Delta B$ should be $0$. However, the function $1_A + 1_B - 1_{A\cap B}$ has the value $1 + 1 - 1 = 1$ on $A\cap B$ and is the indicator function of $A\cup B$.
Another way to see $1_{A\mathbin\Delta B}= 1_A + 1_B - 2(1_{A \cap B})$ is to realize that $$1_{A\setminus B} = 1_A - 1_{A\cap B}$$ and $$1_{B \setminus A} =1_B - 1_{B \cap A}.$$
Since $A\mathbin\Delta B = (A\setminus B) \cup (B \setminus A)$ and this union is disjoint, you can write $1_{A \Delta B}$ as the sum of these.