## Archive for July, 2012

### 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.