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?


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}$$


$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)$


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))$


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.

  • $\begingroup$ hello, thanks for the reply, but going deeper into the theory ended up percer some important points as you quoted above. sorry was a quick sketch to acresentar a possible response to typical $\endgroup$ – Emanoel Oct 21 '14 at 15:01

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.

  • 2
    $\begingroup$ I've used the implication at the end because I've worked with propositional logic; so I've to prove the equivalence between formuale, i.e. the bi-implication. $\endgroup$ – Mauro ALLEGRANZA Oct 18 '14 at 15:46
  • $\begingroup$ ok, thanks you :) $\endgroup$ – Emanoel Oct 19 '14 at 0:57

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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.