Theorem – Union and intersection of sets are distributive, associative and commutative.

We will prove that the intersection and union of two sets obey the laws of distributivity, associativity and commutativity.

Page contents

– Theorem
– Proof of commutativity property
– Proof of associativity property

Theorem

Let $A$ , $B$ and $C$ be sets. The following equalities hold,

Commutativity-

$A\cup{B} = B\cup{A} \\ A\cap{B} = B\cap{A}$

Associativity-

$(A\cup{B})\cup{C} = A\cup{(B\cup{C})} \\ (A\cap{B})\cap{C} = A\cap{(B\cap{C})}$

Distributivity –

$(A\cup{B})\cap{C} = (A\cap{C})\cup{}(B\cap{C}) \\ (A\cap{B})\cup{C} = (A\cup{C})\cap{}(B\cup{C})$

Proof of commutativity

Let $A$ and $B$ be sets. We claim that

$\begin{aligned} A\cup{B} = B\cup{A} \\ A\cap{B} = B\cap{A}\end{aligned}$

Proof [Union] –

First we shall prove the commutativity property for a union of two sets. Recall that the union of two sets is defined as

$A\cup{B} = \{x~|~x\in{A} \vee x\in{B}\}$

So we aim to prove that

$\begin{aligned} A\cup{B} &= \{x~|~x\in{A} \vee x\in{B}\} \\&= \{x~|~x\in{B} \vee x\in{A}\} \\ &= B\cup{A} \end{aligned}$

However, we know that $[x\in{A} \vee x\in{B}] \Leftrightarrow{[x\in{B} \vee x\in{A}}]$ . Therefore, the only contraint on $x$ in both of the above unions is the same in both sets. As a result, it holds that

$\{x~|~x\in{A} \vee x\in{B}\} = \{x~|~x\in{B} \vee x\in{A}\} \\$

Which of course implies

$A\cup{B} = B\cup{A}~~~\square$

Next, we aim to prove the same property for the intersection of two sets.

Proof [Intersection] –

Recall that the intersection is defined as

$A\cap{B} = \{x~|~x\in{A}\wedge x\in{B}\}$

Now, we wish to show that

$\begin{aligned} A\cap{B} &= \{x~|~x\in{A} \wedge x\in{B}\} \\&= \{x~|~x\in{B} \wedge x\in{A}\} \\ &= B\cap{A} \end{aligned}$

But we know that $p\wedge q \Leftrightarrow q\wedge p$ . Therefore we know that

$\{x~|~x\in{A} \wedge x\in{B}\} = \{x~|~x\in{B} \wedge x\in{A}\} \\$

So again, we have that

$A\cap{B} = B\cap{A}~~~\square$

Proof of associativity

Let $x\in{(A\cup{B})\cap{C}}$ . Then,

$\begin{aligned} x\in{(A\cup{B})\cap{C}} &\Leftrightarrow [(x\in{A})\vee (x\in{B})]\wedge (x\in{C}) \\ &\Leftrightarrow [(x\in{A}) \wedge (x\in{C})] \vee [(x\in{B}) \wedge (x\in{C})] \\ & \Leftrightarrow x\in{(A\cap{C})\cup (B\cap{C})~\square}&\end{aligned}$

Now, let $x\in{(A\cap{B})\cup{C}}$ . Then,

$\begin{aligned} x\in{(A\cap{B})\cup{C}} &\Leftrightarrow [(x\in{A})\wedge (x\in{B})]\vee (x\in{C}) \\ &\Leftrightarrow [(x\in{A}) \vee(x\in{C})] \wedge [(x\in{B}) \vee (x\in{C})] \\ & \Leftrightarrow x\in{(A\cup{C})\cap (B\cup{C})~\square}&\end{aligned}$