Associativity Archives - Stumbling Robot

Prove that $A \cup (B \cup C) = (A \cup B) \cup C$ and that $A \cap (B \cap C) = (A \cap B) \cap C$ .

Proof (Associativity of unions). First, let $x$ be any element in $A \cup (B \cup C)$ . This means that $x \in A$ or $x \in (B \cup C)$ . If $x \in A$ then $x \in (A \cup B)$ ; hence, $x \in (A \cup B) \cup C$ . On the other hand, if $x \notin A$ , then $x \in (B \cup C)$ . This means $x \in B$ or $x \in C$ . If $x\in B$ , then $x \in (A \cup B) \implies x \in (A \cup B) \cup C$ . If $x \in C$ , then $x \in (A \cup B) \cup C$ . Hence, $A \cup (B \cup C) \subseteq (A \cup B) \cup C$ .
For the reverse inclusion, let $x$ be any element of $(A \cup B) \cup C$ . Then, $x \in (A \cup B)$ or $x \in C$ . If $x \in (A \cup B)$ , we know $x \in A$ or $x \in B$ . If $x \in A$ , then $x \in A \cup (B \cup C)$ . If $x \in B$ , then $x \in (B \cup C)$ ; hence, $x \in A \cup (B \cup C)$ . On the other hand, if $x \in C$ , then $x \in (B \cup C)$ , and so, $x \in A \cup (B \cup C)$ . Therefore, $(A \cup B) \cup C \subseteq A \cup (B \cup C)$ .
Thus, $A \cup (B \cup C) = (A \cup B) \cup C$ .∎

Proof (Associativity of intersections). To expedite matters, will prove both inclusions at once: $x$ is in $A \cap (B \cap C)$ if and only if $x \in A$ and $x \in (B \cap C)$ , further, $x \in (B \cap C)$ if and only if $x \in B$ and $x \in C$ . Similarly, $x \in (A \cap B) \cap C$ if and only if $x \in A$ and $x \in B$ and $x \in C$ . Thus, $A \cap (B \cap C)$ and $(A \cap B) \cap C$ have exactly the same elements (since $x \in A \cap (B \cap C)$ if and only if $x \in A$ and $x \in B$ and $x \in C$ if and only if $x \in (A \cap B) \cap C$ ).
Thus, $A \cap (B \cap C) = (A \cap B) \cap C$ .∎

Stumbling Robot

Tag: Associativity

Prove the associative laws for union and intersections of sets