0

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?

Ludolila
  • 3,034
Annette
  • 3

1 Answers1

1

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.

jflipp
  • 4,786
  • Can you explain why the "2|γ|+2|δ|" disappear when you show that it is equivalent to the next line? I don't understand that part. – Annette Dec 16 '14 at 10:11
  • Suppose we have two numbers $j,k\in\mathbb Z.$ Then $2|(j+2k)$ iff $2|j.$ This is so because the statement $2|(2k)$ is always true, for any $k.$ More formally, suppose $2|j$. This then implies ($2|j$ and $2|(2k)$) (since $2|(2k)$ is always true). This implies $2|(j+2k).$ In the other direction, suppose $2|(j+2k).$ This then implies ($2|(j+2k)$ and $2|(2k)$) (again, $2|(2k)$ is always true). This implies $2|(j+2k-2k),$ or $2|j,$ as desired. Now, apply this reasoning to the calculations in my answer. – jflipp Dec 16 '14 at 10:30