Natural Deduction for sets

Question

I'm a student of logic and I have a question, want to prove The Following sets by natual deduction, but do not know how to proceed.

$$\begin{align} a) A \cap (B \cup C) ≡ (A \cap B) \cup (A \cap C) \end{align}$$

\begin{align} (1) & A \cap (B \cup C) && [\text{hypothesis }] \\ (2) & A && [\cap \text{-elim }] \\ \end{align}

the first question is that I want to get to (A ∩ B) ∪ (A∩C) eliminated get A and (B∪C) but now I do not know how to go about the rest of the deduction.

some help!

Answer 1

You have to proceed "by cases" , i.e. use $\lor$-elimination.

For the first inclusion : $A∩(B∪C) \subseteq (A∩B)∪(A∩C)$ you have from

(1) : $A∩(B∪C)$ --- premise

it is an "and" [$x \in A∩(B∪C)$ iff $x \in A \land x \in (B∪C)$]; thus, by $\land$-elim we derive :

(2) : $A$

(3) : $B∪C$

this is an "or" [$x \in B∪C$ iff $x \in B \lor x \in C$]; thus we need $\lor$-elim :

(4) : assume $B$ and derive : $A ∩ B$ by $\land$-intro and then

(5) : $(A∩B)∪(A∩C)$ by $\lor$-introduction

in the same way :

(6) : assume $C$ and derive : $A ∩ C$ by $\land$-intro and then

(7) : $(A∩B)∪(A∩C)$ by $\lor$-introduction

We have derived $(A∩B)∪(A∩C)$ from both "temporary" assumptions : $B$ and $C$; thus, by $\lor$-elim, we conclude with :

(8) : $(A∩B)∪(A∩C)$ from 3 : $B∪C$, discharging (4) and (6).

---

In the same way we can proceed for the other inclusion : $(A∩B)∪(A∩C) \subseteq A∩(B∪C)$.