Thread: 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


I am not just sure really where to go next in the proof.
The help would be ever so appreciated.

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.

Could do this "directly" via intersection/union/complement manipulations using , 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
Let .

Then either , or . Thus the possiblities split into:
Part 1, Case 1: and .
Part 1, Case 2: and .
For Part 1, Case 1: and , so:
Since , either and , or and .
Part 1, Case 1.1:
Part 1, Case 1.2:
For Part 1, Case 2: and , so:
Since , either or . Thus this splits into 2 cases:
Part 1, Case 2.1:
Part 1, Case 2.2: .

Have show that implies:
(Part 1, Case 1.1)
OR (Part 1, Case 1.2)
OR (Part 1, Case 2.1)
OR (Part 1, Case 2.2).

Now that Part 1 is broken up into its components, must show that, in each of those case, .
(There another way to do this problem. There's a trick that could be used here: show that examining Part 2, where , 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 (Part 1, Case 1.1), then , and . Therefore .

If (Part 1, Case 1.2), then , and . Therefore .

If (Part 1, Case 2.1), then , and . Therefore .

If (Part 1, Case 2.2), then , and . Therefore .

Therefore, have proven Part 1: , so have proven that .

Now do the exact same procedure for Part 2, which will examine, and then prove, that . The rest would look like:

Part 2: Show
Let .
Then... blah... blah... blah...
...
Therefore have proven Part 2: , so have proven that .
Therefore, Part 1 and Part 2 together have proven that .
QED