0
$\begingroup$

For any three sets $A, B$ and $C$, show that $$A\Delta B = C \iff A = B\Delta C.$$

I am a student and wish some more information on the above. Kindly help.

  • 2
    Do you know that $\Delta$ is associative and $A\Delta A=\emptyset$?2012-08-28
  • 3
    What is $\Delta$ here? Symmetric difference?2012-08-28
  • 1
    @HenningMakholm: Yes, that is the customary meaning of the symbol.2012-08-28
  • 1
    Not so, @HaraldHanche-Olsen...according to WA (http://mathworld.wolfram.com/SymmetricDifference.html ), one must dispose of that symbol as it is already used in other contexts.2012-08-29
  • 2
    @DonAntonio: right. I will bow to the authority and will immediately stop following a custom that goes back to the beginnings of measure theory and set theory just because W|A (of all people) says so... FWIW: I've never seen any of the other symbols (except maybe +) that are suggested on that page in any measure theory or topology book. Deprecated. That's ridiculous.2012-08-29
  • 0
    As you wish. That symbol you say was introduced in the beginnings of set theory is said to be introduced less than two decades ago. I really don't care as long as it's made clear. You can read here http://www.proofwiki.org/wiki/Definition:Symmetric_Difference about other symbols. Besides this:(1) Jean Rubin's "set Theory for the mathematician" uses the symbol $\,\square\,$ , (2) Kaplansky's "Set theory and matrices" and Halmos's "Axiomatic Set theory" both use the symbol $\,+\,$ , (3) Suppes's " Axiomatic Set Theory" uses the symbol $\,\div\,$...so there's hardly "a custom".2012-08-29
  • 1
    @DonAntonio: Different cultures, I guess :) Measure theory is more my business than set theory and I thought Hausdorff used the symbol but I seem to have misremembered; sorry about that. I should probably have added the qualifier *modern* to measure theory and left set theory out. Virtually every measure theory book I know features that symbol and nothing else (some use + instead). Halmos's 1950 first edition of his *Measure theory* has it and it's in Royden's 1967 edition, just two examples among many others (and far older than 2 decades ago). Definitely a custom in measure theory.2012-08-29

5 Answers 5

7

Here is a fact which is easy to check:

The set $C=A\Delta B$ is uniquely defined by the identity $\mathbf 1_C=\mathbf 1_A+\mathbf 1_B\bmod{2}$.

Hence, $C=A\Delta B$ if and only if $\mathbf 1_{C}=\mathbf 1_A+\mathbf 1_B\bmod{2}$ if and only if $\mathbf 1_A=\mathbf 1_C-\mathbf 1_B=\mathbf 1_C+\mathbf 1_B\bmod{2}$ if and only if $A=C\Delta B$.

Edit: @Harald Hanche-Olsen's answer is based on an equivalent formulation of the easy fact above, equally worthy of notice and perhaps even more interesting because it is more symmetrical, namely:

The set $C=A\Delta B$ is uniquely defined by the identity $\mathbf 1_A+\mathbf 1_B+\mathbf 1_C=0\bmod{2}$.

4

Here is one way: Notice that $A\bigtriangleup B=C$ is equivalent to the statement that every $x$ belongs to an even number (i.e., none or two) of the sets $A$, $B$, $C$. From that the claim follows by symmetry.

  • 0
    MathJax's `\bigtriangleup` seems a bit too big. Oh well.2012-08-28
  • 0
    There is `\Delta` $\Delta$ v. $\bigtriangleup$2012-08-28
  • 0
    @Harold, if you have the STIX fonts installed, that might be the culprit, as the big triangle in that font is a bit larger than TeX's version. There is not a lot of choice in the triangles within a font, I'm afraid.2012-08-29
  • 0
    @Henry: Yes, I know, but $\Delta$ is an ordinary math symbol. Though I could of course have fixed that by typing `\mathbin\Delta` to get $A\mathbin\Delta B=C$.2012-08-29
1

Using the associativity and commutativity of the symmetric difference operator, you get:

$$A \Delta B = (B \Delta C) \Delta B = C \Delta (B \Delta B) = C \Delta \emptyset = C$$

  • 0
    And how do you prove that this operator is associative and commutative?2012-08-28
  • 0
    Your assumptions and conclusions don't seem very clear to me. It would be simpler, I think, if you phrased your argument as "if [...] then [...]".2012-08-28
  • 1
    @ Godot: That is a different question I guess. The commutativity is absolutely trivial. The associativity follows rather easily. However, I didn't feel that it was important when I wrote my answer. I just wanted to make Michael Kessy aware of that what he is asking follows easily from these two properties2012-08-28
  • 0
    @ Ben Millwood: You are absolutely right, it was sloppy. I just wanted to demonstrate that using these two properties is the way to go. Michael Kessy will have to do the formalities himself when he applies this to his problem, or whatever.2012-08-28
1

Here's the long messy way. We want to show $A\triangle B = C \iff A = B\triangle C$

$\Rightarrow$: Assume $C = A\triangle B$

Recall $A\triangle B = (A\cup B) - (A\cap B) = (B-A)\cup(A-B)$

$$\begin{align} (B\cup C) - (B\cap C) &= (B\cup [(A - B) \cup (B - A)]) - (B\cap [(A\cup B) - (A\cap B)]) \\ &= ([B\cup (A- B)] \cup (B - A)) - ([B\cap (A\cup B)] - [B\cap (A\cap B)]) \\ &= ((A\cup B) \cup (B - A)) - (B - (A\cap B))\\ &= ((A\cup B) \cup (B - A)) - (B - A)\\ &= (A\cup B) - (B - A)\\ &= A \end{align}$$

$\Leftarrow$ is, dare is say, symmetric.

0

The algebraic structure of classical sets under union, intersection and complement (note that I've included complement, so we do have a universal set here), comes as the same as the algebra of classical logic under disjunction, conjunction, and negation. So, you can first rewrite the symmetric difference formulas in terms of union and complement. Then you can check out the corresponding truth tables in terms of disjunction and negation. After that you can invoke the sameness of algebraic structure and the result follows (unless it's not correct, I haven't checked myself).