Proof verification: Commutativity of set union and intersection

Question

Theorem. Let $M, N, L$ be sets. Then the following assertions hold:

(1) $M \cap N = N \cap M$

(2) $M \cup N = N \cup M$

Proof is left as an exercise.

---

My attempt:

(1) $\forall x: x \in M \cap N \implies x \in M \land x \in N \implies x \in N \cap M \implies N \cap M $

(2) $\forall x : x \in M \cup N \implies x \in M \lor x \in N \implies x \in N \cup M \implies N \cup M$

Is this right or am I either being redundant or jumping to conclusions?

---

Liesen, J., Mehrmann, V. 2015. Linear Algebra. Berlin, Germany.: Springer.

Answer 1

Showing set equality (often) comes down to showing that each is a subset of the other. I’ll show one direction. You can prove the other directions.

1) Let $x\in M\cap N$. Then $x\in M,N$. Then $x\in N\cap M$. Thus, $M\cap N \subset N\cap M$.

2) Let $x\in M\cup N$. Then $x\in M$ or $x\in N$. Then $x\in N\cup M$. Thus, $M\cup N \subset N\cup M$.

Answer 2

I am proving this using natural deduction:

1. x (arbitrary constant - a.k.a - let there be)

2. $x\in M \cup N$ (let's assume)

3. $x\in M \vee x \in N$ (Def of union, 2)

4. $ x\in N \vee x\in M$ (communitativity of disjunction, 3)

5. $ x\ N \cup M $ (Def of union, 4)

6. $x\in M \cup N \rightarrow x\in N \cup M$ (Introduction of implication, 2 to 5)

7. $x\in N \cup M$ (let's assume)

8. $x\in N \vee x \in M$ (Def of union, 2)

9. $ x\in M \vee x\in N$ (communitativity of disjunction, 3)

10. $ x\ M \cup N $ (Def of union, 4)

11. $x\in N \cup M \rightarrow x\in M \cup N$ (Introduction of implication, 7 to 10)

12. $x\in M \cup N \leftrightarrow x\in N \cup M $ (Introduction of equivalence, 11,6)
13. $\forall M,N.(x\in M \cup N \leftrightarrow x\in N \cup M)$ (Introduction of universal, 1-12) QED

It could be written a lot nicer when there's an option to use tabs, and indents.