3
$\begingroup$

Let $A + B = (A - B) \cup (B - A)$ also known as the symmetric difference.

  1. Look for the identity and let $e$ be the identity element

$A + e = A$

$(A - e) \cup (e - A) = A$

Now there are two cases:

  1. $(A - e) = A$ This equation can be interpreted as removing from A all elements that belong to $e$ to yield the set $A$. In order for this statement to be true, the identity element $e$ must be the empty set.

  2. $(e - A) = A$ This equation can be interpreted as removing from $e$ all elements that belong to $A$ to generate a set $A$. Is this statement undefined?

  • 0
    These links seem to be a little related: http://www.proofwiki.org/wiki/Symmetric_Difference_on_Power_Set_forms_Abelian_Group http://www.proofwiki.org/wiki/Symmetric_Difference_with_Intersection_forms_Ring2011-07-21

4 Answers 4

2

Following Sleziak's suggestion, it might be useful to point out that under the bijection $A\mapsto\chi_{A}$, the symmetric difference is realized as

\[ A\triangle B\sim\left|\chi_{A}-\chi_{B}\right|^{2}.\]

It is then straightforward to check that multiplication is distributive:

\[ C\cap\left(A\triangle B\right) \sim \chi_{C}\left|\chi_{A}-\chi_{B}\right|^{2}=\left|\chi_{C\cap A}-\chi_{C\cap B}\right|^{2} \sim \left(C\cap A\right)\triangle\left(C\cap B\right).\]

5

I thought it might be helpful to add a completely different viewpoint. (Feel free to ignore this answer, if other answers are clearer for you or if this post contains some things that you have not studied yet.)

We work with subsets of some given set $M$. Such subsets can be identified with function from $M$ to $\{0,1\}$, namely, there is a bijection between $\mathcal P(M)$ and $\{0,1\}^M$ given by $$A\mapsto\chi_A$$ where $\chi_A$ is the characteristic function of the set $A$:

$$\chi_A(x)= \begin{cases} 1,& x\in A\\ 0,& x\notin A \end{cases} $$

So we have a bijection between $\mathcal P(M)$ and the ring $\mathbb Z_2^M$ (with the componentwise operations). Let us have a look which set operations correspond to the ring operations $\oplus$ and $\odot$.

$$\chi_{A\triangle B}=\chi_A\oplus\chi_B$$ (I prefer the symbol $\triangle$ as the notation for symmetric difference.) $$\chi_{A\cap B}=\chi_A\odot\chi_B$$

So $(\mathcal P(M),\triangle,\cap)$ is a ring isomorphic to $(\mathbb Z_2^M, \oplus, \odot)$. If we work with the second ring, we see that the identity for the operation $\oplus$ is $(0,0,\dots,0)$, which means that the identity for $\triangle$ is the corresponding set, which is $\emptyset$.

I am mentioning this basically for the reason that it illustrates the situation when instead of proving some things about one structure (in this case it is $(\mathcal P(M),\triangle,\cap)$) it might be helpful to find an isomorphic structure which we are already familiar with.

  • 1
    Nice. I like this answer. Although it is very fun to see, I doubt OP wanted to complicate his problem in order to solve it! But seriously, it's cool and good to know. +12011-07-22
  • 0
    @Patrick: I agree with you that this answer was probably not particularly helpful to OP, but still it might be helpful to other people. I find this relationship kind of nice and when I have enough time, I try to show this to my students when they're learning about rings.2011-07-22
4

$e-A = A$ is clearly impossible... $e-A$ contains no element of the set $A$ by construction. The only thing that could define an identity is clearly the empty set, because $(e-A)$ doesn't contain any element of $A$, hence must not contain any element at all, for if $e$ contains an element, there exists a set $A$ which does not contain this element and therefore $(e-A)$ contains an element not in $A$, contradicting the fact that $(A-e) \cup (e-A) = A$. Now $A-\varnothing = A$ so that $\varnothing$ is your identity.

Hope that helps,

  • 0
    If I'm following you correctly: $(A - e) \cup (e - A) = A$. If $e$ is the empty set, $A \cup \emptyset = A$2011-07-21
  • 0
    Well, I am saying that if you want $(A-e) \cup (e-A) = A$, $e$ must be empty, and $\varnothing$ works, so $\varnothing$ is your only choice.2011-07-21
  • 0
    If e is the emptyset, I clearly see why $(A - e) = A$. But would $(e - A) = \emptyset$ or undefined? Sorry, my knowledge of set theory is limited. Because if $(e - A) = \emptyset$ is true, then $A \cup \emptyset = A$ is definitely true.2011-07-21
  • 0
    I'm not saying it's empty ; it's just that if you want $(A-e) \cup (e-A) = A$, $e-A$ must not contain any element for any choice of the set $A$, because if $e$ does contain an element, call it $x$, you can choose a set $A$ so that $x \notin A$, so that $x \in e-A$ and $x \notin A$, thus $(A-e) \cup (e-A) = A$ cannot hold, because $x$ is in the LHS but not in the RHS. In other words, you WANT $(e-A)$ to be empty, all the time.2011-07-21
  • 0
    Patrick, I follow your logic, but just for clarification, if I want $(e - A)$ to be empty, then $e = \emptyset$ because if I try to remove elements of A from an emptyset, I will only get an empty set right?2011-07-21
  • 0
    This is not why $e = \varnothing$. It is because no other set than $\varnothing$ will do. What I said in terms of logic is that if $e \neq \varnothing$, then it doesn't work, and $e = \varnothing$ does work (because of what you just explained), so it is the only possibility.2011-07-22
3

Patrick's got it. Here's the same, in a somewhat different presentation.

The symmetric difference of two sets is the stuff that's in exactly one of the two sets. If the symmetric difference of $A$ and $B$ is $A$, then $B$ can't have any elements that are in $A$ (since those elements of $A$ wouldn't be in the symmetric difference), and $B$ can't have any elements that aren't in $A$ (since those non-elements of $A$ would be in the symmetric difference), so $B$ can't have any elements. Thus if $B$ is to be the identity, $B$ must be empty; moreover, if $B$ is empty, it works as an identity element for symmetric difference.