Natural Deduction for Sentence Logic sets

Question

I am trying to prove by natural deduction the following laws of sets, but I doubt I am doing it the right way.

$$\begin{align} a) A \cup B = B \cup A \end{align}$$

$$\begin{align} (1) & A \cup B && [\text{hypothesis }] \\ (2) & |A && [\text{hypothesis }] \\ (3) & |B \cup A && [\text{introduction (2)}] \\ (4) & |B && [\text{hypothesis }] \\ (5) & |B \cup A && [\text{introduction (4)}] \\ (4) & B \cup A && [\text{assumed}] \\ \end{align}$$

---

$$\begin{align} b) A \cap B = B \cap A \end{align}$$

$$\begin{align} (1) & A \cap B && [\text{hypothesis }] \\ (2) & B && [\cap \text{-elim}(1)] \\\ (3) & A && [\cap \text{-elim}(1)] \\\ (5) & B \cap A && [\cap - \text{introduction (2,3)}] \\ \end{align}$$

Could someone point out any errors?

Answer 1

With Natural Deduction you prove logical formulae, with logical conncetive, like $\lor, \land$; thus, we have to use : $\equiv$ (equivalence) and not $=$ (identity).

To prove the equivalence (or bi-implication) $\varphi \equiv \psi$, we have to prove two implications : $\varphi \rightarrow \psi$ and $\psi \rightarrow \varphi$, and then use the $\equiv$-introduction rule :

$$\frac{\varphi \rightarrow \psi \quad \psi \rightarrow \varphi}{\varphi \equiv \psi}$$

---

For

$a_1)$ : $(A \lor B) \rightarrow (B \lor A)$

steps (1)-(5) are correct (the rule to be referenced in comments is : $\lor$-introduction), but the final steps are missing :

(6) $B \lor A$ --- from (1), (2) and (4) by $\lor$-elimination

where $\lor$-elimination is the rule :

$$\frac{\varphi \lor \psi \quad \varphi \vdash \sigma \quad \psi \vdash \sigma}{\varphi \lor \psi \vdash \sigma}$$

Finally :

(7) $(A \lor B) \rightarrow (B \lor A)$ --- from (1) and (6) by $\rightarrow$-introduction.

Then, you have to repeat it for :

$a_2)$ : $(B \lor A) \rightarrow (A \lor B)$.

From $a_1)$ and $a_2)$, by $\equiv$-introduction, we conclude with :

$(A \lor B) \equiv (B \lor A)$

Answer 2

Hello thanks for the feedback,

I can use the basic rules of natural dedudção even working upon sets!, just did not understand why the use of the implication at the end ..   Remaking and putting their references:

$$\begin{align} a) A \cup B = B \cup A \end{align}$$

$$\begin{align} (1) & A \cup B && [\text{hypothesis }] \\ (2) & |A && [\text{hypothesis }] \\ (3) & |B \cup A && [\cup \text{-introduction (2)}] \\ (4) & |B && [\text{hypothesis }] \\ (5) & |B \cup A && [\cup \text{-introduction (4)}] \\ (6) & B \cup A && [\cup \text{-elim(1-5)}] \\ \end{align}$$

The second question, it is wrong ?! used because the rules as was a deletion of the operator and. thanks.

Answer 3

You are confused about the natural deduction method. When working with natural deduction, our introduction/elimination rules are restricted to logical connectives, i.e. negation rules, conjunction rules, disjunction rules, implication rules. So they cannot be casually applied to others non-logical operators.

First, what is the set-theoretic definition of $X \cup Y$?

$X \cup Y \equiv x∈X∨x∈Y$

Now what is the meaning of $X=Y$?

$ X =Y \equiv X \subseteq Y \wedge Y \subseteq X$

Hence we want to prove that:

$$ ((x∈A∨x∈B) \subseteq (x∈B∨x∈A)) \wedge ((x∈B∨x∈A) \subseteq (x∈A∨x∈B)) $$

Which, by the natural deduction rule conjunction introduction, it means that we need to prove that both

$((x∈A∨x∈B) \subseteq (x∈B∨x∈A))$ and $((x∈B∨x∈A) \subseteq (x∈A∨x∈B))$

holds.

Now how to prove the left one? Again, what is the definition of '$\subseteq$'?

I hope this shed some light on your problem, and helps you to see how simple proof strategies works in general.

Answer 4

that time the letter this way: $\def\fitch#1#2{~\begin{array}{|l}#1\\\hline#2\end{array}}$

$\fitch{}{ \fitch{~~1.~~[x]\qquad\text{hyp}}{ \fitch{~~2.~~x\in A \cup B\qquad\text{hyp}}{ \fitch{~~3.~~x\in A\qquad\text{hyp}}{ ~~4.~~x\in B \cup A\qquad\text{Int }\cup}\\ \fitch{~~5. x\in B\qquad\text{hyp}}{ ~~6.~~x\in B \cup A\qquad\text{Int }\cup}\\ ~~7.~~x\in B \cup A}\\ ~~8.~~x\in A\cup B\to x\in B\cup A}\\ ~~9.~~A\cup B\subseteq B\cup A\\ \fitch{10.~~[y]\qquad\text{hyp}}{ \fitch{11.~~ y\in B \cup A\qquad\text{hyp}}{ \fitch{12.~~y\in A\qquad\text{hyp}}{ 13.~~y\in A \cup B\qquad\text{Int }\cup}\\ \fitch{14.~~y\in B\qquad\text{hyp}}{ 15.~~y\in A \cup B\qquad\text{Int }\cup}\\ 16.~~y\in A\cup B}\\ 17.~~y\in B \cup A \to y\in A \cup B}\\ 18.~~B\cup A\subseteq A\cup B\\19.~~A\cup B=B\cup A}$