Ravi Mohan's Tech Blog. To read my non technical blog, click here

Friday, October 3, 2008

An Unsatisfactory Proof

To be proved

"If the symmetric difference of sets A and B is a subset of A, prove that B is a subset of A"



symmetric difference of A and B = A U B \ A ^ B (using U for union , ^ for intersection and \ for difference).

What I've come up with


The Proof


Let x be an arbitrary element of B.

Then x is also an element of A (case 1) or it is not (case 2).

case 1.

If an arbitrary element of B is an element of A then B is a subset of A .

case 2.

x is an element of B but is not an element of A. In which case, it is an element of (A U B) \ ( A ^ B), ie it is an element of the symmetric difference of the sets A and B. Since it is given that the symmetric difference of A and B is a subset of A, x is an element of A.

Since x is an element of A in both cases and since x is an arbitrary element of B, we conclude that B is a subset of A.

Q.E.D

I keep getting the feeling there is a more elegant way to prove this. If anyone wants to write to me (or comment here) I'd appreciate it much.

PS: - the proposition is obviously true (draw a Venn diagram to see why). I am asking for help on the (structure of the) proof itself.