Prove through induction that $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ is odd

Question

I am trying to prove the following claim through induction:

Assume $A_1,\ldots,A_n$ series of Sets.

Prove that $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ is odd

My questions:

1. The base case starts here from one or from zero?
2. Should I prove this claim in two ways? right to left and left to right? i.e do two inductions?

Answer 1

You can start from $0$, because one can define the multiple symmetric difference by $$ \mathop{\large\triangle}_{i=0}^0 A_i=\emptyset, \qquad \mathop{\large\triangle}_{i=0}^{n+1} A_i= \biggl(\mathop{\large\triangle}_{i=0}^{n} A_i\biggr)\mathbin{\triangle}A_{n+1} $$ Here, associativity of symmetric difference is important.

Now the base step of the induction is clear: for $n=0$, we have $|\{i\mid a\in A_i\}|=0$ and $a\notin\emptyset$.

Now suppose that the statement holds for $n$ sets and set, for simplicity, $$ B=\mathop{\large\triangle}_{i=0}^{n} A_i $$ We have that $a\in B\mathbin{\triangle}A$ if and only if $a\in B$ or $a\in A_{n+1}$, but $a\notin B\cap A_{n+1}$. This is equivalent, by the induction hypothesis, to

$|\{i\mid a\in A_i\}|$ is odd or $a\in A_{n+1}$, but $a\notin B\cap A_{n+1}$.

Check the cases and you're done.

Answer 2

Base case is for $n=1$:

$$a \in A_1 \iff |\{i \in \{1\} : a \in A_i\}| = 1 \iff |\{i\in \{1\} : a \in A_i\}| \text{ is odd}$$

since $|\{i \in \{1\} : a \in A_i\}| \in \{0,1\}$.

Assume that $a \in A_1 \Delta\, \cdots \Delta\,A_n \iff |\{i \in \{1, \ldots, n\}: a \in A_i\}|$ is odd.

For $n+1$ we have \begin{align} a \in A_1 \Delta\, \cdots \Delta\,A_n \Delta\,A_{n+1} &\iff \vee\begin{cases} \big(a \in A_1 \Delta\, \cdots \Delta\,A_n\big) \wedge (a \notin A_{n+1}), \\ \big(a \notin A_1 \Delta\, \cdots \Delta\,A_n\big) \wedge (a \in A_{n+1})\end{cases}\\ &\iff \vee\begin{cases} \big(|\{i \in \{1, \ldots, n\}: a \in A_i\}| \text{ is odd}\big) \wedge (a \notin A_{n+1}), \\ \big(|\{i \in \{1, \ldots, n\}: a \in A_i\}| \text{ is even}\big) \wedge (a \in A_{n+1})\end{cases}\\ &\iff \vee\begin{cases} |\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}| \text{ is odd}, \\ |\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}| \text{ is odd}\end{cases}\\ &\iff |\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}|\text{ is odd} \end{align}