Question about the proof of the distributive property for sets

Question

I have been learning set theory from scratch again and I have a question about the distributive property for sets. It seems the only proof I found of it actually USES the very same distributive property while proving it. This seems circular to me, could someone explain why it is allowed?

This is what I am trying to prove.
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

I got this proof from a quora answer.

Let $x \in A \cup (B \cap C)$. If $x \in A \cup (B \cap C)$ then $x$ is either in $A$ or in ($B \cap C$).

$x \in A$ or $x \in (B \cap C)$

$x \in A$ or ($x \in B$ and $x \in C$)

HERE!!! How does one get from the statement above to the one below without actually using the distributive property itself?

($x \in A$ or $x \in B$) and ($x \in A$ or $x \in C$)

$x \in (A \cup B)$ and $x \in (A \cup C)$

$x \in (A ∪ B) \cap (A ∪ C)$

$x \in A \cup (B \cap C) \implies x \in (A \cup B) \cap (A \cup C)$.

Thanks a lot!!

Answer 1

The argument is not really circular, as the logical operations are distinct from the set theoretic operations. If you consider the logical operations as being more "basic", you can decompose the unions and intersections into logical statements, then use the logical statements to get your results. That is, it might be helpful if you rewrote your proof to distinguish more between the logical operations (and, or, not, etc.) and the set operations ($\cap$, $\cup$, complementation, etc).

There is also an issue in that your argument only proves one of the two containments required in order to prove the desired statement. You also need to show that the reverse containment holds.

• Suppose that $x \in A \cup (B \cap C)$ [NOTE: right here, I am stating that $x\in B\cap C$, and not $x\in (B \text{ and } C)$;I am being careful to to mix statements about set containment with logical statements. This is important.]. By definition of the union, either $x \in A$ or $x\in B\cap C$. There are now two cases to consider:

  1. If $x\in A$, then by definition of unions, $x \in A \cup B$ and $x \in A\cup C$. Therefore $x \in (A\cup B) \cap (A\cup C)$ by definition of the intersection.

  2. If $x\in B\cap C$, then by definition of the intersection, $x \in B$ and $x \in C$. Since $x \in B$, it follows from the definition of the union that $x \in A \cup B$. Similarly, $x \in A\cup C$. Therefore $x\in (A\cup B) \cap (A\cup C)$.

  In either case, we have that $x \in (A\cup B) \cap (A\cup C)$. This implies that $$A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C).$$

• Now suppose that $x \in (A\cup B)\cap (A\cup C)$. Then $x \in A\cup B$ and $x \in A \cup C$. If $x \in A$, then $x \in A\cup (B\cap C)$, and we are done. Otherwise, $x \not\in A$ implies that $x \in B$ (since $x \in A\cup B$) and $x \in C$ (since $x\in A \cup C)$. But then $x \in B\cap C$. Hence $x \in A \cup (B\cap C)$. Therefore $$A\cup (B\cap C) \supseteq (A\cup B)\cap (A\cup C).$$

As both containments hold, the proof is complete.

EDIT: I see that you asked for a reference in a comment on the other fine answer. Personally, I rather like Richard Hammock's Book of Proof for this material. The text is reasonably rigorous, relatively easy to read, and (best of all) free. The approach is, perhaps, a little different than your current approach, but I think that you should be able to marry to two without too much difficulty.

Answer 2

Though it certainly feels like it, it actually is not circular: you use the distributive property for the logical operations of 'and' and 'not' to prove the distributive property for the set operations of union and intersection. Moreover, the purely logical properties are seen as more 'fundamental', so this is all ok.

Of course, if you are asking why the logical distributive property holds, well, that's another question.