Proving Set Theory Basics Quick introduction, I am a just graduated high school senior working on logic and proofs just to get a better feel for my mathematics degree this fall. My book does not have a solutions page. Here is my proof to the following equality.
$$
A \cup(B \cap C)=(A\cup B)\cap (A\cup C)
$$

*

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


*This means $x$ must lie in $A\cup B$ and $A\cup C$.


*Since $x \in A \cup B$ and $x \in A \cup C$, then $x \in A$.


*Since $x \in A$, then $x \in A \cup (B\cap C)$.
I am unsure if the last step is strong enough to show equivalence. Thanks for the help!
 A: I would not say that how you write it down is sufficient to prove the equivalence.
It reads more of a proof for $x\in(A\cup B)\cap (A\cup C)$. So $A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$
Also you ignore the case where $x\notin A$. This can happen also.
So you can distinguish two cases.

*

*$x\in A$.


*$x\notin A$, then $x\in B\cap C$, as $x\in B$ and $x\in C$ has to hold in this case.
Further more, you should adopt are more formal writing style. You do not have to exeggarate, what many beginners do, but I dont like this step 1. step 2. ... style.
I think you can now fix your proof accordingly.

Example for a more formal proof:
(Introduction not part of the proof)
We want to show $(A\cup B)\cap (A\cup C)=A\cup (B\cap C)$.So an equality of sets. This is important to note, as there are many different mathematical objects. Sets, functions, numbers, ... and for every mathematical object equality is shown differently.
For sets we have to show equality by proving the both inclusions $\subseteq$ and $\supseteq$.
So when we want to proof two sets $A$ and $B$ are equal, hence $A=B$, this is done in two steps.
One is to show $A\subseteq B$. The other is $A\supseteq B$.
By definition of $A\subseteq B$ ($A$ is a subset of $B$), we have to proof that for every $x\in A$, we have $x\in B$.
Example: $\{1,2\}\subseteq \{1,2,3\}$, because every element in $\{1,2\}$ is also an element in $\{1,2,3\}$.
But $\{1,2,4\}$ is not a subset of $\{1,2,3\}$ as there is an element, namely $4$, which is not an element of $\{1,2,3\}$.
As your example involves a seperation of cases, let me give a different example.
DeMorgan's Law
Let $A,B\subseteq X$, then we have $(A\cup B)^c=A^c\cap B^c$, where $A^c$ notes the complement of $A$ in $X$. Hence $A^c=X\setminus A$. The set of all $x\in X$ with $x\notin A$.
We have to proof equality of sets. Hence $(A\cup B)^c\subseteq A^c\cap B^c$ and $(A\cup B)^c\supseteq A^c\cap B^c$.
We can do this like this:
$x\in (A\cup B)^c\Rightarrow x\in X$ and $x\notin (A\cup B)$
$\Rightarrow x\in X$ and $x\notin A$ and $x\notin B$.
$\Rightarrow x\in X$ and $x\notin A$ and $x\in X$ and $x\notin B$.
$\Rightarrow x\in X\setminus A$ and $x\in X\setminus B$
$\Rightarrow x\in A^c$ and $x\in B^c$
$\Rightarrow x\in A^c\cap B^c$.
So this ends the proof of $(A\cup B)^c\subseteq A^c\cap B^c$.
It remains to show that $A^c\cap B^c\subseteq (A\cup B)^c$.
This can be done by reading the proof above "backwards", and justifying all the steps, changing every $\Rightarrow$ into $\Leftrightarrow$.
$x\in A^c\cap B^c\Leftarrow x\in X\setminus A$ and $x\in X\setminus B$
$\Rightarrow x\in X$ and $x\notin A$ and $x\in X$ and $x\notin B$
$\Rightarrow x\in X$ and $x\notin A$ and $x\notin B$
$\Rightarrow x\in X$ and $x\notin (A\cup B)$
$\Rightarrow x\in X\setminus (A\cup B)$
$\Rightarrow x\in (A\cup B)^c$.
Ending the proof.
So basically two times exactly the same proof, which can be shortend, by just writing:
$x\in (A\cup B)^c\Rightarrow x\in X$ and $x\notin (A\cup B)$
$\Leftrightarrow x\in X$ and $x\notin A$ and $x\notin B$.
$\Leftrightarrow x\in X$ and $x\notin A$ and $x\in X$ and $x\notin B$.
$\Leftrightarrow x\in X\setminus A$ and $x\in X\setminus B$
$\Leftrightarrow x\in A^c$ and $x\in B^c$
$\Leftrightarrow x\in A^c\cap B^c$.
So this would be an example for, what I consider, a formal proof.
A: Here's a set inclusion chart:




$A$
$B$
$C$
$A\cup(B\cap C)$
$(A\cup B)\cap(A\cup C)$




Y
Y
Y
Y
Y


Y
Y
N
Y
Y


Y
N
Y
Y
Y


Y
N
N
Y
Y


N
Y
Y
Y
Y


N
Y
N
N
N


N
N
Y
N
N


N
N
N
N
N




Because the last two columns are the same, the last two sets are the same.
