Printable View
My friend has a basic set theory proof problem that I tried to help him with but was unable to figure out what to do.
(Using element argument)
Prove that
If Complement(A) ⊆ B Then A ∪ B = Universal set
I have tried a direct proof, contrapositive, and contradiction but I have failed at each one. How would this be proved?
This is NOT a homework problem of mine.
Let S = Universal set. Any element in S belongs either to A or to Complement(A). Let x be any element in S.
If x belongs to Complement(A), since Complement(A) is a subset of B, and x belongs to Complement(A), x belongs to B, and so x belongs to A union B.
If x does not belong to Complement(A), then by definition x belongs to A. Thus x belongs to A union B.
Since we've shown that if x belongs to S, x belongs to A union B, we know S is a subset of A union B. By assumption A and B are subsets of S, so that their union is also a subset of S. That is, A union B is a subset of S. This shows both directions of inclusion, so that A union B = S.
The real point is that something is either in A or in A's complement. Since anything in A's complement is in B, and anything not in A's complement is in A, those two sets must together contain everything.
Thanks. That makes sense. I was focusing more on trying to prove by contrapositive or contradiction but was getting no where. I see that direct proof was the way to go.
By contradiction, you could assume that S is not a subset of A union B. Then you'd have some x in S but not in A union B. Then x is in neither A nor B, so that x is in Complement(A). Since Complement(A) is a subset of B, x must be in B--a contradiction since x is in neither A nor B.
Thus S is a subset of A union B, and you can use two-way inclusion to prove S = A union B.
For contraposition, you would want to show the contrapositive of "S is a subset of A union B"; that is, you'd show Complement(A union B) is a subset of Complement(S). Since Complement(S) = 0 [empty set], you'd need to show Complement(A union B) is empty. Let x belong to Complement(A union B). By the rules of complementing, x belongs to Complement(A) intersect Complement(B), so x is in both Complement(A) and Complement(B), and again x is in neither A nor B. But again since Complement(A) is a subset of B, x is in B. Thus no such x exists, and Complement(A union B) is empty. From contraposition, S is a subset of A union B; two way inclusion gives the result.
It's really all about fiddling around until something clicks. The proof from my first post was far more natural for me than these other two, and was guided by my own intuition. When asked if something is true or not, a person will go through some logical steps and see if they can prove it to themselves--the proof I ended up making was the math-speak version of the one I used for myself.