Archive for the ‘set theory’ Category

An exercise from Halmos’s set theory book

July 8, 2012

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.