We have a universal set of lowercase alphabet letters, $U = \{a, b, ... , z\}$ . For sets $A,B \subseteq U$ we can define a relation, $A \sim B$ as long as the number of elements that are in either $A$ or $B$, but not both, is even. Prove that $\sim$ is an equivalence relation, and describe the equivalence classes.
I've come up with equations for $A \sim B$ and $B\sim C$. For $A \sim B$, I have $|(A \cup B)-(A \cap B)| \equiv 0 \mod2$, and for $B \sim C$, I have $|(B \cup C)-(B \cap C)| \equiv 0 \mod 2$. I've been told to come up with equations for $A\sim B$ and $B \sim C$, then add them to prove $A\sim C$, but I don't know how that's possible. I'm thinking I should end up with $|(A\cup C)-(A \cap C)| \equiv 0 \mod2$, but I don't know how. Perhaps my equations are incorrect?
This is not so difficult to figure out if you draw the complete Venn diagram and consider all possible intersections. In symbols, it works as follows.
Put $\alpha := A\setminus(B\cup C),$ $\delta := (A\cap C)\setminus B,$ $\gamma := B\setminus(A\cup C),$ $\zeta := (B\cap C)\setminus A,$ $\beta := (A\cap B)\setminus C,$ $\eta := C\setminus(A\cup B).$ Convince yourself with the aid of the aforementioned Venn diagram that all those sets denoted by greek letters are pairwise disjoint, and also that we have: $$ A\setminus B = \alpha \cup \delta $$ $$ B\setminus A = \gamma \cup \zeta $$ $$ B\setminus C = \beta \cup \gamma $$ $$ C\setminus B = \delta \cup \eta $$ $$ A\setminus C = \alpha \cup \beta $$ $$C\setminus A = \eta \cup \zeta $$ Now, from $A\sim B,$ we conclude $$ 2|\left(|\alpha| + |\delta| + |\gamma| + |\zeta|\right), $$ and from $B \sim C,$ we conclude $$ 2|\left(|\beta|+|\gamma|+|\delta|+|\eta|\right). $$ By "adding up" these two statements, we get $$ 2|\left(|\alpha|+|\beta|+|\zeta|+|\eta|+2|\gamma|+2|\delta|\right). $$ This is equivalent to $$ 2|\left(|\alpha|+|\beta|+|\zeta|+|\eta|\right). $$ Now, using all the definitions and facts from above, we see that this is equivalent to $$ 2|(|A\Delta C|),\qquad or \qquad A \sim C, $$ as desired.