$x\in\triangle_{i=1}^{n}A_i$ if and only $x$ belongs to an odd number of $A_1,A_2,\dots,A_n$

39 Views Asked by At

Is the following argument correct?

Proposition. Given an arbitrary $x$ and sets $A_1,A_2,\dots,A_n$, we have $x\in A_1\triangle A_2\triangle \dots\triangle A_n$ if and only if $x$ belongs to an odd number of $A_1,A_2,\dots,A_n$, here $A_1\triangle A_2 = (A_1\backslash A_2)\cup(A_2\backslash A_1)$.

Proof. We contruct the proof by recourse to Mathematical-Induction, the proof of the base case is trivial. We therefore proceed with the inductive step. Assume for an arbitrary $k\in\mathbf{N}$ that given any $k$ sets $A_1,A_2,\dots,A_k$, $x\in A_1\triangle A_2\triangle \dots\triangle A_n$ if and only if $x$ belongs to an odd number of $A_1,A_2,\dots,A_n$.

Now let $X_1,X_2,\dots,X_k,X_{k+1}$ be any $k+1$ arbitrary sets. We prove both conditionals as follows

$(\Rightarrow).$ Assume $x\in (\triangle_{j=1}^{k}X_j)\triangle X_{k+1}$, then either $x\in(\triangle_{j=1}^{k}X_j)\backslash X_{k+1}$ in which case the inductive hypothesis readily implies that $x$ belongs to an odd number of of $X_1,X_2,\dots,X_k$, the claim in question is the evident, or $x\in X_{k+1}\backslash(\triangle_{j=1}^{k}X_j)$ but then $x\not\in \triangle_{j=1}^{k}X_j$, and thus by inductive hypothesis $x$ belongs to an even number of $X_1,X_2,\dots,X_k$ which together with $x\in X_{k+1}$, implies that $x$ belongs to an odd number of $X_1,X_2,\dots,X_k,X_{k+1}$.

$(\Leftarrow).$ Now assume that $x$ belongs to an odd number of $X_1,X_2,\dots,X_{k},X_{k+1}$. Now either $x\in X_{k+1}$, in which case $x$ belongs to an even number of $X_1,X_2,\dots,X_k$ which by inductive hypothesis implies that $x\not\in\triangle_{j=1}^{k}X_j$ and by extension $x\in X_{k+1}\backslash(\triangle_{j=1}^{k}X_j)\subseteq X_{k+1}(\triangle_{j=1}^{k+1}X_j)$, or $x\not\in X_{k+1}$, but then $x$ belongs to an odd number of $X_1,X_2,\dots,X_k$ and by inductive hypothesis $x\in \triangle_{j=1}^{k}X_j$, thus $x\in (\triangle_{j=1}^{k}X_j)\backslash X_{k+1}\subseteq \triangle_{j=1}^{k+1}X_j$.

$\blacksquare$