An exercise from Halmos’s set theory book

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 (A \cap B) \cup C = A \cap (B\cup C) is that C\subset A. Observe that the condition has nothing to do with the set B.

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.

  • C\subset A\iff A\cap C = C
  • C\subset A\iff A\cup C=A

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

Moving on with the exercise, let us assume that C\subset A. We first see that the left side becomes (A\cup C)\cap(B\cup C). Since A\cup C=A under our assumption that C\subset A, we see that this becomes A\cap(B\cup C).

For the right side, we get (A\cap B)\cup (A\cap C), which is just (A\cap B)\cup C, since A\cap C=C. Now, we distribute C again, which gives us (A\cup C)\cap(B\cup C)=A\cap(B\cup C). So we have shown that C\subset A is a sufficient condition for (A \cap B) \cup C = A \cap (B\cup C). We now go on to show that it is also a necessary condition, completing our proof.

Suppose (A \cap B) \cup C = A \cap (B\cup C). Our task is to show that C\subset A. It is probably a good idea to use the let trick. So let x\in C. Our task now is to show that x\in A. If we let X be an arbitrary set, then since x\in C, we also know that x\in C\cup X. This tells us that x\in(A\cap B)\cup C. Since (A \cap B) \cup C = A \cap (B\cup C) by assumption, we also have x\in A \cap (B\cup C). If x\in X\cap Y, we know that x\in X and x\in Y. So since x\in A \cap (B\cup C), we can conclude that x\in A. This completes our proof.

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


2 Responses to “An exercise from Halmos’s set theory book”

  1. gowers Says:

    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 \null B.” It’s notable that the result is true when \null B=\emptyset and also when \null B is the universal set of which all three sets are presumably subsets. How can we exploit this to show the result for an arbitrary \null B? One idea is to use the fact that two sets are equal if their intersections with \null B are equal and their intersections with \null B^c are equal. These two cases amount to treating \null B 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.)

  2. Luís Sequeira Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: