I found the following problem in Paul Halmos’s Naive Set Theory. It seemed interesting so I thought I would post it here.

Exercise. A necessary and sufficient condition that is that . Observe that the condition has nothing to do with the set .

The trick here I think is to realize that we can use some past results from set theory to aid us. In particular, I think the following will be helpful.

One must also keep in mind the distributive laws for sets.

Moving on with the exercise, let us assume that . We first see that the left side becomes . Since under our assumption that , we see that this becomes .

For the right side, we get , which is just , since . Now, we distribute *again*, which gives us . So we have shown that is a sufficient condition for . We now go on to show that it is also a necessary condition, completing our proof.

Suppose . Our task is to show that . It is probably a good idea to use the let trick. So let . Our task now is to show that . If we let be an arbitrary set, then since , we also know that . This tells us that . Since by assumption, we also have . If , we know that and . So since , we can conclude that . This completes our proof.

Now about the “Observe that the condition has nothing to do with the set ” part. Well, we see that in our proof, the set was arbitrary and wasn’t important at all. So that’s that.

### Like this:

Like Loading...

*Related*

This entry was posted on July 8, 2012 at 8:58 am and is filed under set theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can skip to the end and leave a response. Pinging is currently not allowed.

August 10, 2012 at 6:05 pm |

I agree that the question is interesting. However, I’m not sure that the proof you give is what Halmos is hinting at when he says, “Observe that the condition has nothing to do with .” It’s notable that the result is true when and also when is the universal set of which all three sets are presumably subsets. How can we exploit this to show the result for an arbitrary ? One idea is to use the fact that two sets are equal if their intersections with are equal and their intersections with are equal. These two cases amount to treating as the universal set and then treating it as the empty set. So we’re done. (I need to think a bit more about how I’d present that argument rigorously.)

December 12, 2012 at 2:34 pm |

For the second implication, it is probably easier to argue by contrapositive: assume C is not a subset of A; let x be an element in C that does not belong to A; then it is clear that x is in one of the sets and not the other.