Proof of the Associative Law of Symetric Difference

Hi there,

I have to prove using Element Chasing that (A delta B) delta C = A delta ( B delta C)

I have the Venn drawn, and was told to start with:

let x be an element of (A delta B) delta C

if x is an element of (A delta B) union(and) C but not in x element (A delta B) intersection(or) C

(Thinking)

I am not just sure really where to go next in the proof. (Worried)

The help would be ever so appreciated. (Evilgrin)

Re: Proof of the Associative Law of Symetric Difference

Note the following.

For all sets X and Y, x belongs to X ∆ Y iff x belongs to precisely one of X and Y; correspondingly, x does not belong to X ∆ Y iff x belongs to either both X and Y or none of them. (*)

There are 2³ = 8 cases for whether x belongs to each of A, B and C. You can decide to be patient and go through all of them checking for each case whether x belongs to either side of the equality using (*).

Another way is to prove first that x belongs to (A ∆ B) ∆ C iff x belongs to an odd number of sets (either one or three). For any set X, define in(x, X) = 1 if x ∈ X and in(x, X) = 0 if x ∉ X. Then we want to prove the following.

For all sets A, B and C, x ∈ (A ∆ B) ∆ C iff in(x, A) + in(x, B) + in(x, C) is odd. (**)

Note that (*) says the same thing, but about two instead of three sets. To show (**), note that x ∈ (A ∆ B) ∆ C iff either (1) x ∈ A ∆ B and x ∉ C or (2) x ∉ A ∆ B and x ∈ C. In (1), in(x, A) + in(x, B) is odd and in(x, C) = 0, so in(x, A) + in(x, B) + in(x, C) is odd. In (2), in(x, A) + in(x, B) is even and in(x, C) = 1, so again in(x, A) + in(x, B) + in(x, C) is odd. (Note that this proof of (**) can be used in a proof by induction of the generalization of (**) for n sets.)

Now, given specific sets A', B', C', we can instantiate A = B', B = C' and C = A' in (**) to get

x ∈ (B' ∆ C') ∆ A' iff in(x, B') + in(x, C') + in(x, A') is odd. (***)

But (B' ∆ C') ∆ A' = A' ∆ (B' ∆ C'), so (***) gives

x ∈ A' ∆ (B' ∆ C') iff in(x, A') + in(x, B') + in(x, C') is odd, (****)

which together with (**) proves associativity. Alternatively, (****) can be shown similarly to (**).

See also this thread.

Re: Proof of the Associative Law of Symetric Difference

Could do this "directly" via intersection/union/complement manipulations using $\displaystyle A \Delta B = (A \cup B ) \cap ( \ (A \cap B)^c \ )$, but I assume that's not "element chasing".

The general technique of showing that two sets are equal is to show that each is a subset of the other. Thus it's a two part process, one for each direct of subset inclusion. For this problem, it's largely a book-keeping problem of being systematic. Here's how it might be done:

**Part 1**: Show $\displaystyle (A \Delta B) \Delta C \subset A \Delta (B \Delta C)$

Let $\displaystyle x \in (A \Delta B) \Delta C$.

Then either $\displaystyle x \in (A \Delta B), x\notin C$, or $\displaystyle x \in C, x \notin (A \Delta B)$. Thus the possiblities split into:

*Part 1, Case 1: *$\displaystyle x \in (A \Delta B)$ and $\displaystyle x \notin C$.

*Part 1, Case 2: *$\displaystyle x \in C$ and $\displaystyle x \notin (A \Delta B)$.

For Part 1, Case 1: $\displaystyle x \in (A \Delta B)$ and $\displaystyle x \notin C$, so:

Since $\displaystyle x \in (A \Delta B)$, either $\displaystyle x \in A$ and $\displaystyle x \notin B$, or $\displaystyle x \in B$ and $\displaystyle x \notin A$.

*Part 1, Case 1.1: *$\displaystyle x \in A, x \notin B, x \notin C$

*Part 1, Case 1.2:* $\displaystyle x \notin A, x \in B, x \notin C$

For Part 1, Case 2: $\displaystyle x \in C$ and $\displaystyle x \notin (A \Delta B)$, so:

Since $\displaystyle x \notin (A \Delta B)$, either $\displaystyle x \notin A \cup B$ or $\displaystyle x \in A \cap B$. Thus this splits into 2 cases:

*Part 1, Case 2.1: *$\displaystyle x \in A, x \in B, x \in C$

*Part 1, Case 2.2:* $\displaystyle x \notin A, x \notin B, x \in C$.

Have show that $\displaystyle x \in (A \Delta B) \Delta C$ implies:

$\displaystyle x \in A, x \notin B, x \notin C$ (Part 1, Case 1.1)

OR $\displaystyle x \notin A, x \in B, x \notin C$ (Part 1, Case 1.2)

OR $\displaystyle x \in A, x \in B, x \in C$ (Part 1, Case 2.1)

OR $\displaystyle x \notin A, x \notin B, x \in C$ (Part 1, Case 2.2).

Now that Part 1 is broken up into its components, must show that, in each of those case, $\displaystyle x \in A \Delta (B \Delta C)$.

(There another way to do this problem. There's a trick that could be used here: show that examining Part 2, where $\displaystyle x \in A \Delta (B \Delta C)$, also breaks down into those 4 same cases. If you could do that, you'd be done. However, I'll proceed doing it the "direct" way.)

If $\displaystyle x \in A, x \notin B, x \notin C$ (Part 1, Case 1.1), then $\displaystyle x \notin B \Delta C$, and $\displaystyle x \in A$. Therefore $\displaystyle x \in A \Delta (B \Delta C)$.

If $\displaystyle x \notin A, x \in B, x \notin C$ (Part 1, Case 1.2), then $\displaystyle x \in B \Delta C$, and $\displaystyle x \notin A$. Therefore $\displaystyle x \in A \Delta (B \Delta C)$.

If $\displaystyle x \in A, x \in B, x \in C$ (Part 1, Case 2.1), then $\displaystyle x \notin B \Delta C$, and $\displaystyle x \in A$. Therefore $\displaystyle x \in A \Delta (B \Delta C)$.

If $\displaystyle x \notin A, x \notin B, x \in C$ (Part 1, Case 2.2), then $\displaystyle x \in B \Delta C$, and $\displaystyle x \notin A$. Therefore $\displaystyle x \in A \Delta (B \Delta C)$.

Therefore, have proven Part 1: $\displaystyle x \in (A \Delta B) \Delta C \Rightarrow x \in A \Delta (B \Delta C)$, so have proven that $\displaystyle (A \Delta B) \Delta C \subset A \Delta (B \Delta C)$.

Now do the exact same procedure for Part 2, which will examine, and then prove, that $\displaystyle A \Delta (B \Delta C) \subset (A \Delta B) \Delta C$. The rest would look like:

__Part 2:__ Show $\displaystyle A \Delta (B \Delta C) \subset (A \Delta B) \Delta C$

Let $\displaystyle x \in A \Delta (B \Delta C)$.

Then... blah... blah... blah...

...

Therefore have proven Part 2: $\displaystyle x \in A \Delta (B \Delta C) \Rightarrow x \in (A \Delta B) \Delta C$, so have proven that $\displaystyle A \Delta (B \Delta C) \subset (A \Delta B) \Delta C$.

Therefore, Part 1 and Part 2 together have proven that $\displaystyle A \Delta (B \Delta C) = (A \Delta B) \Delta C$.

QED