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.
Subscribe to:
Post Comments (Atom)
5 comments:
I think you mean \ is difference, not compliment.
In case 2, you've actually derived a contradiction. You can use that to negate the premise, and the negation of the premise is what you want to prove. You don't really need case 1. To wit:
x in B and x not in A
-> x in AUB and x not in A^B
-> x in AUB\A^B
-> x in A
-> x not in B or x in A
-> (x in B -> x in A)
I would say that this is really just a cleaned up version of your proof. The problem is so simple and the proof is so short that I don't think there's a way to come up with a really different argument that is any shorter.
1) complement -> difference.
Thanks, difference is correct. (I've changed the entry)
As for "I would say that this is really just a cleaned up version of your proof."
this is *exactly* what I was looking for.
Much better!
Thank You!
I thought about this some more, and the more I think about it the smaller the real differences between the proofs look. My version starts with x in B and x not in A, but that is not given. It basically assumes case 1, and a more complete and formal proof would still probably contain an (x in B) and (x in A or X not in A) clause at some point. The difference is that my version no longer needs to refer back to case 1 at the end of the proof, so it can just be left out because it is so obvious.
This is the way mathematicians like to do things, and it is nicer in a lot of ways. But the difference is really more in the style of the way the proof is written than in the elegance of the actual mathematical or logical content. To make an analogy with computing, it just shifts work from the application to the interpreter, it doesn't reduce the size or complexity of the system as a whole.
Here's a proof based on Boolean algebra.
We're given A xor B <= A.
Using the usual definition of <= on a Boolean algebra, (A <= B <==> A + B = B), we can write:
A xor B <= A
<==> A xor B + A = A.
<==> A(!B) + (!A)B + A = A
<==> A(!B + 1) + (!A)B = A
<==> A + (!A)B = A
<==> A + B = A
<==> B <= A
"I thought about this some more, and the more I think about it the smaller the real differences between the proofs look."
True, but your version was still useful to me because it explicitly identifies the contradiction and then (explicitly) negates the assumption. This was something I missed out on in my version, where I was over focussed on the "creation of exhaustive cases" idea.
Post a Comment