Proof verification: Commutativity of set union and intersection
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.
$\endgroup$ 42 Answers
$\begingroup$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$.
$\endgroup$ 1 $\begingroup$I am proving this using natural deduction:
x (arbitrary constant - a.k.a - let there be)
$x\in M \cup N$ (let's assume)
$x\in M \vee x \in N$ (Def of union, 2)
- $ x\in N \vee x\in M$ (communitativity of disjunction, 3)
$ x\ N \cup M $ (Def of union, 4)
$x\in M \cup N \rightarrow x\in N \cup M$ (Introduction of implication, 2 to 5)
$x\in N \cup M$ (let's assume)
$x\in N \vee x \in M$ (Def of union, 2)
- $ x\in M \vee x\in N$ (communitativity of disjunction, 3)
$ x\ M \cup N $ (Def of union, 4)
$x\in N \cup M \rightarrow x\in M \cup N$ (Introduction of implication, 7 to 10)
- $x\in M \cup N \leftrightarrow x\in N \cup M $ (Introduction of equivalence, 11,6)
- $\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.
$\endgroup$
