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

elementary-set-theoryinduction

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?

Best Answer

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.

Related Question