[Math] Some basic set theory proofs.

elementary-set-theory

Are these proofs correct? I felt really bad because I felt that I have only written a bunch of garbage just to restate the obvious rather than proving anything. (I am not very used to the mentality in set theory.)

Q: Show that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C).$

ANS:

First we need to show that $A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C).$
\begin{eqnarray*}
&\text{if}\ x \in A \cap (B \cup C)\\
&\Rightarrow x \in A \ \text{and}\ x \in (B \cup C)\\
&\Rightarrow x \in A \ \text{and}\ (x \in B \ \text{or}\ x \in C)\\
&\Rightarrow (x \in A \ \text{and}\ x \in B )\ \text{or}
\ (x \in A \ \text{and}\ x \in C)\\
&\therefore A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C).
\end{eqnarray*}
Now we need to show that $(A \cap B) \cup (A \cap C) \subset A \cap (B \cup C)$.
\begin{eqnarray*}
&\text{if}\ x \in (A \cap B) \cup (A \cap C)\\
&\Rightarrow (x \in A \ \text{and}\ x \in B )\ \text{or}
\ (x \in A \ \text{and}\ x \in C)\\
&\Rightarrow x \in A \ \text{and}\ (x \in B \ \text{or}\ x \in C)\\
&\Rightarrow x \in A \ \text{and}\ x \in (B \cup C)\\
&\therefore (A \cap B) \cup (A \cap C) \subset A \cap (B \cup C).
\end{eqnarray*}
We conclude $A \cap (B \cup C) = (A \cap B) \cup (A \cap C).$

Best Answer

They are fine. Note that the way you've written them reduces the set theory property of distributivity to the logical property (i.e. in a Boolean algebra) of distributivity. This you do in the transition from "$x \in A$ and $(x \in B \text { or } x \in C)$" to "$(x \in A \text { and } x \in B) \text { or } (x \in A \text { and } x \in C)$", in the first proof, e.g.

You can also use a more "natural deduction"-like approach: e.g. for the first inclusion: suppose $x \in A \cap (B \cup C)$. This means that $x \in A$ and also $x \in (B \cup C)$. Now we consider two cases:

Suppose $x \in B$, then $x \in A$ still and $x \in B$ so $x \in A \cap B$, and so certainly $x \in (A \cap B) \cup (A \cap C)$.

On the other hand, if $x \in C$ (second case), $x \in A \cap C$ and again $x \in (A \cap B) \cup (A \cap C)$, and so $x$ is in the right hand side in both cases, and this proves the inclusion.