1. ## Symmetric difference

Show that this operation on sets is associative: for all sets: A,B,C one has (A @B)@C = A@(B@C)

P.S. because I dont know how to type the "triangle" sign to the message, the "@" mean the "triangle" sign, the symmetric difference.

2. So how do you prove it if you're in ZF set theory, and set complementation is not allowed?

So what are the first steps? First, how do you ordinarily show that sets are equal? Second, upack the two sets by the definition of '@'.

4. Well, I'm doing Suppes' Axiomatic Set Theory. Problem 2.3.12 is the one I'm working on. It goes like this:

We define the operation of symmetric difference by the identity:

$\displaystyle A\div B=(A\sim B)\cup(B\sim A)$.

Prove:
$\displaystyle (A\div B)\div C=A\div(B\div C)$. (This is actually part (c) of a multi-step problem, but this is the step that has me stumped.)

I've seen emakarov's solution on this forum, using the exclusive or function's associativity. That's nice, but I'm wondering if all that extra baggage of having to prove the relationship between the exclusive or and the symmetric difference is worth it. Then you've also introduced a whale of a lot of symbols that ZF set theory hasn't defined yet.

If you write out the right and left sides of the identity, you get:

$\displaystyle (A\div B)\div C=(((A\sim B)\cup (B\sim A))\sim C)\cup(C\sim((A\sim B)\cup (B\sim A)))$, and

$\displaystyle A\div(B\div C)=(A\sim((B\sim C)\cup(C\sim B)))\cup(((B\sim C)\cup(C\sim B))\sim A)$.

Now, you can show that $\displaystyle A\sim(B\cup C)=(A\sim B)\cap(A\sim C)$, and that $\displaystyle A\sim(B\cap C)=(A\sim B)\cup(A\sim C)$.

Moreover, you can also show that $\displaystyle (A\cup B)\sim C=(A\sim C)\cup(B\sim C)$, and $\displaystyle (A\cap B)\sim C=(A\sim C)\cap(B\sim C)$. The last is technically part (d) of the problem; although I can prove it independently of part (c), it'd be great if I didn't have to use it.

However, what I'm really looking for is a more elegant, less tedious way of showing this property. I mean, it's not even true that $\displaystyle (((A\sim B)\cup (B\sim A))\sim C)=(A\sim((B\sim C)\cup(C\sim B)))$. So whatever method you use from here would have to straddle the union in the middle. Not nice at all.

5. Oh, and I should also point out that one thought I had as to strategy was to show that both sides equaled the following expression:

$\displaystyle ((A\sim B)\cap(A\sim C))\cup((B\sim A)\cap(B\sim C))\cup((C\sim A)\cap(C\sim B))\cup(A\cap B\cap C)$.

6. There are many ways to prove this, and depending what has already been proven.

But I'm not thinking of the most elegant or even less tedious approach. Rather, I'm thinking of the most obvious, straightforward approach - just the most obvious, basic, direct way to get the thing proven.

That is,

1. Assume x in A@(B@C) and show x in (A@B)@C.
2. Asuume x in (A@B)@C and show x in A@(B@C).

Assume 1:

Either
x in A and it is not the case that either ((x in B and x not in C) or (x in C and x not in B))

or

either ((x in B and x not in C) or (x in C and x not in B)) or x not in A.

And you can keep breaking this down to a "table" of cases.

Then show, by also "breaking down" (A@B)@C and taking the cases above, that x in (A@B)@C.

Then do the converse (2.) in similar manner.

7. Yes, I am aware of the usual way to prove two sets are equal. The sentences you've written down are entirely equivalent to the ones I've written down. In doing it the usual way, I would think logical errors would be extremely easy to come by. Moreover, the result would barely be human-readable! This is why I'm not a fan of that approach for this problem. It's just a bit too unwieldy. I like the elegance of the exclusive or approach; if I could prove emakarov's lemma that makes the correspondence between set difference and exclusive or the bijection it needs to be, and with preferably as little extra baggage as possible, I think I'd probably go with that. Do you have any different ideas for the proof?

8. Do as you wish, but proving it in the "literal" way of just unpacking to a "table" of alternatives is not especially prone to logical error nor need it be unreadable. Indeed, it is utterly straightforward, airtight, convincing, and its formalization in first order logic would be routine. Personally, I wouldn't make such a big deal about this proof - looking for especially elegant ways to prove it (which ways themselves require some detour into lemmas, whatever) - but rather I'd just apply the definitions and directly prove it as suggested, then to move on in the book. (Indeed, in the time we've exchanged messages about this - about looking for a more elegant way - one could have as easily just typed out the rest of the proof I started).

Later, of course, you'll see how this goes hand in hand with the sentential operator 'exclusive or' and the Boolean operation, etc. But for mere purposes of getting the thing proven at this point in Suppes text, I'd just go ahead and unpack the definitions and show x in one iff x in the other. But suit yourself...

9. Or, one could just as well write:

Suppose x in A@(B@C).

So

either
x in A and it is not the case that either ((x in B and x not in C) or (x in C and x not in B))

or

either ((x in B and x not in C) or (x in C and x not in B)) or x not in A.

[Then in the same manner spell out the condition for x in (A@B)@C. Then write: "So x in (A@B)@C follows by routine sentential logic." Then do the converse. Then done.]

10. Originally Posted by Ackbeet
So how do you prove it if you're in ZF set theory, and set complementation is not allowed?
Why the hell did you open a three year old thread? I should start doing that! Answer all the old posts that interst me!! >