Proof:A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

From CS2800 wiki
[math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) \href{/cs2800/wiki/index.php/Equality_(sets)}{=} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]
Proof: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Choose arbitrary sets [math]A [/math], [math]B [/math], and [math]C [/math]. We want to show that the LHS is a subset of the RHS and vice-versa.

To see that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} LHS [/math]. Then we know that either [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] or [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) [/math].

In the case that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], we see that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%5Ccup}{\cup} B) [/math] by definition; similarly [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. Therefore [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) = \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] as desired.

In the other case, we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C [/math]. We want to show that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} = (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. Thus we must show both that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. Well, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) [/math] because [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math] (since we know [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} C [/math]); [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math] similarly. This completes this case and the fact that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math].

We must now show that [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math]. Choose an arbitrary [math]x ∈ \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]; note that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. We know that either [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] or [math]x \notin A [/math]. If [math]x ∈ A [/math] then [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math] by definition of .

On the other hand, if [math]x \notin A [/math] then [math]x [/math] must be in [math]B [/math]; otherwise [math]x [/math] could not be in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]. Similarly, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} C [/math]; thus [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) [/math] so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math] as required.

We have now shown that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] and [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math], which completes the proof that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math].

This is a good (although perhaps slightly wordy) proof of the claim: each statement is clear, and follows from the previous statements using standard proof techniques.

There are a variety of different styles demonstrated in this proof. For example, the first case in the [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] works fortward from what is known, while the second case works backwards from what we want to show. Both styles are useful, but you must clearly distinguish what you have already proved from what you want to show. Otherwise, you will end up giving an invalid backwards proof.