# Proof for Associative Law for Symmetric Difference

• Jan 7th 2009, 05:43 PM
h2osprey
Proof for Associative Law for Symmetric Difference
That is, prove that A delta (B delta C) = (A delta B) delta C.

I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?
• Jan 8th 2009, 02:43 PM
HallsofIvy
Quote:

Originally Posted by h2osprey
That is, prove that A delta (B delta C) = (A delta B) delta C.

I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?

As long as it is a valid proof, there is no reason why it shouldn't be acceptable.
• Jan 8th 2009, 03:00 PM
Jhevon
Quote:

Originally Posted by h2osprey
That is, prove that A delta (B delta C) = (A delta B) delta C.

I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?

it would probably be good for you to post your proof...just how lengthy is it? :D
• Jan 9th 2009, 07:43 AM
gusztav
Quote:

Originally Posted by h2osprey
That is, prove that A delta (B delta C) = (A delta B) delta C.

Here is one way to prove it, it may be similar to your way, but here goes:

By definition, we know that $\displaystyle A \Delta B=(A \backslash B) \cup (B \backslash A)$. Therefore,

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

$\displaystyle =((A \Delta B)\backslash C) \cup (C \backslash (A \Delta B))=$

$\displaystyle =((A \Delta B)\cap (C)^c) \cup (C \cap (A \Delta B)^c)=$

$\displaystyle =[((A \backslash B) \cup (B \backslash A))\cap (C)^c]\cup[C \cap ((A \backslash B)\cup (B \backslash A))^c]=(*)$

Now we make a little digression to simplify $\displaystyle ((A \backslash B)\cup (B \backslash A))^c$ from the above expression:
$\displaystyle ((A \backslash B)\cup (B \backslash A))^c=$
$\displaystyle =((A \cap B^c) \cup (B \cap A^c))^c=$
$\displaystyle =(A \cap B^c)^c \cap (B \cap A^c)^c=$
$\displaystyle =(A^c \cup (B^c)^c) \cap (B^c \cup (A^c)^c)=$
$\displaystyle =(A^c \cup B) \cap (B^c \cup A)=$
$\displaystyle =(A^c\cap B^c) \cup (A^c\cap A) \cup (B \cap B^c) \cup (B \cap A)=$
$\displaystyle =(A^c\cap B^c) \cup (A \cap B)$, and then plug this into the equation above;

$\displaystyle (*)=[((A \cap B^c) \cup (A^c \cap B))\cap C^c]\cup[C \cap ((A^c\cap B^c) \cup (A \cap B))]=$

$\displaystyle =[(A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c)]\cup[(C \cap A^c \cap B^c) \cup (C \cap A \cap B))]=$

$\displaystyle =(A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c)\cup (A^c \cap B^c \cap C) \cup (A \cap B \cap C)$

Next, if you exchange sets in the original expression ($\displaystyle (A \Delta B) \Delta C$) in the following way: $\displaystyle A \leftrightarrow B$;$\displaystyle B \leftrightarrow C$;$\displaystyle C \leftrightarrow A$, you'll get that

$\displaystyle (B \Delta C) \Delta A=...=(A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c)\cup (A^c \cap B^c \cap C) \cup (A \cap B \cap C)$, and from this, it follows that

$\displaystyle (A \Delta B) \Delta C =(B \Delta C) \Delta A=$(and, because the symmetric difference is a symmetric operation, i.e. $\displaystyle X \Delta Y= Y \Delta X$, it follows that)=$\displaystyle A \Delta (B \Delta C)$.

Therefore, $\displaystyle (A \Delta B) \Delta C =A \Delta (B \Delta C)$
• Jan 10th 2009, 01:44 PM
h2osprey
Quote:

Originally Posted by Jhevon
it would probably be good for you to post your proof...just how lengthy is it? :D

I basically gave the proof above except I didn't show that both sides were equal to the derived one; I proved it all the way with iff's.
• Nov 27th 2009, 09:39 AM
emakarov
Here is a different way to prove this, or rather to reduce it to associativity of addition $\displaystyle \oplus$ modulo 2. To remind, $\displaystyle \oplus:\{0,1\}\times\{0,1\}\to\{0,1\}$; $\displaystyle x\oplus y=x+y$ if at least one of $\displaystyle x,y$ is $\displaystyle 0$, and $\displaystyle 1\oplus 1=0$.

Definition. For a set $\displaystyle A$ and an object $\displaystyle x$, let $\displaystyle in(x,A)=1$ if $\displaystyle x\in A$ and $\displaystyle in(x,A)=0$ otherwise.

Lemma. For all sets $\displaystyle A, B$ and any object $\displaystyle x$, $\displaystyle in(x,A{\scriptstyle\triangle} B)=in(x,A)\oplus in(x,B)$.

Theorem. For all sets $\displaystyle A,B,C$, $\displaystyle A{\scriptstyle\triangle}(B{\scriptstyle\triangle}C )=(A{\scriptstyle\triangle}B){\scriptstyle\triangl e}C$.

Proof. For any $\displaystyle x$, $\displaystyle in(x,A{\scriptstyle\triangle}(B{\scriptstyle\trian gle}C))=in(x,A)\oplus(in(x,B)\oplus in(x,C))$ = $\displaystyle (in(x,A)\oplus in(x,B))\oplus in(x,C)=in(x,(A{\scriptstyle\triangle}B){\scriptst yle\triangle}C)$.
• Dec 6th 2009, 10:00 PM
pol02oma
(Hi)
Quote:

Originally Posted by h2osprey
That is, prove that A delta (B delta C) = (A delta B) delta C.

I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?

• Dec 6th 2009, 10:16 PM
pol02oma
hi math members my name is Paul Otuoma from Nairobi,Kenya. Am a student at the University of Nairobi.Am persuing Bachelor of Science, where am taking Double maths and Physics..Am glad to join this group its superb..Let me ask how comes (A delta B) is (A\B) U (B\A)?? our teacher taught us that, (A delta B)= ( A-B) U (B-A) ??? Please help..
• Dec 7th 2009, 01:21 AM
Shanks
You can prove it by using characteristic function, the prove would be simpler.
• Dec 7th 2009, 02:21 AM
emakarov
Quote:

Originally Posted by pol02oma
maths and Physics..Am glad to join this group its superb..Let me ask how comes (A delta B) is (A\B) U (B\A)?? our teacher taught us that, (A delta B)= ( A-B) U (B-A) ???

$\displaystyle A-B$ and $\displaystyle A\setminus B$ are two different notations for the same thing: set difference. In fact, it is a good idea for people to define less-standard concepts and notations when they ask questions because there are so many variations of the same concepts around the world. I am talking in general, not so much about this particular thread because both $\displaystyle A-B$ and $\displaystyle A\setminus B$ are pretty standard.