Properties of Set Operations

In this lesson we will look at the following properties and laws for union and intersection as well as their proof.

Commutativity of Union and Intersection
Associativity of Union and Intersection
Distributive Property of Union over Intersection and Intersection over Union
De Morgan's Laws

Commutativity

$A \cup B = B \cup A$

$A \cap B = B \cap A$

This should be intuitive by the definition of both union and intersection. $A \cup B$ means that "all $x$ that are in $A$ or $B$ " which is the same as "all $x$ that are in $B$ or $A$ ". $A \cap B$ means that "all $x$ that are in both $A$ and $B$ " which is the same as "all $x$ that are in both $B$ and $A$ "

$A \cup B = \{ x | x \in A \lor x \in B\} = \{ x | x \in B \lor x \in A\} = B \cup A$

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

Associativity

$(A \cup B) \cup C = A \cup (B \cup C)$

$(A \cap B) \cap C = A \cap (B \cap C)$

The proof for this is also intuitive, but for the sake of completion and as a precursor for what is to come, here is the proof in technical terms.

Proof for Associativity of Union

$(A \cup B) \cup C = A \cup (B \cup C)$

Let $x \in (A \cup B) \cup C$

$\Rightarrow x \in (A \cup B) \lor x \in C$

$\Rightarrow x \in A \lor x \in B \lor x \in C$

$\Rightarrow x \in A \lor x \in (B \cup C)$

$\Rightarrow x \in A \cup (B \cup C)$

But x is an arbitary member of $(A \cup B) \cup C$ and all $x$ are also in $A \cup (B \cup C)$ . Which means that;

$\Rightarrow (A \cup B) \cup C \subseteq A \cup (B \cup C) \quad [1]$

Similarly, we have to prove that $(A \cup B) \cup C \subseteq A \cup (B \cup C)$

Let $y \in A \cup (B \cup C)$

$\Rightarrow y \in A \lor x \in (B \cup C)$

$\Rightarrow y \in A \lor x \in B \lor x \in C$

$\Rightarrow y \in (A \cup B) \lor C$

$\Rightarrow y \in (A \cup B) \cup C$

But y is an arbitary member of $A \cup (B \cup C)$ and all $y$ are also in $(A \cup B) \cup C$ . Which means that;

$\Rightarrow A \cup (B \cup C) \subseteq (A \cup B) \cup C \quad [2]$

From $[1]$ and $[2]$ , we get;

$\Rightarrow A \cup (B \cup C) = (A \cup B) \cup C \quad [2]$

Because two sets that are subset of each other much be equal.

The proof for associativity of intersection is exactly the same with the signs switched and is left to the student.

Distributivity Properties:

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

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

Here is the interactive step by step proof for union over intersection distributive property.

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

Start by assuming an arbitrary element of the left-hand side.

Let $x \in A \cup (B \cap C) \quad [1]$

Rewrite the membership in terms of logical operators.

$\Rightarrow x \in A \lor x \in (B \cap C) \quad [2]$

SKIP

We need to transform $x \in A$ and $x \in B \cap C$ into the same expression.

SKIP

Starting with $x \in A$

If $x$ is in $A$ , how does that relate to $A \cup B$ and $A \cup C$ ?

If $x \in A$ , then it must belong to $A \cup B$ and $A \cup C$

Express this statement with set membership notation and logical 'and'.

$x \in A = x \in (A \cup B) \wedge (A \cup C)$

Change $\wedge$ to $\cap$ .

$= x \in (A \cup B) \cap (A \cup C) \quad [3]$

SKIP

Now transforming $x \in (B \cap C)$

State what $x \in (B \cap C)$ means in terms of membership in $B$ and $C$ .

If $x \in (B \cap C)$ then $x \in B$ and $x \in C$

Express this with logical 'and' notation.

$x \in (B \cap C) = x \in B \wedge x \in C$

Relate this to $A \cup B$ and $A \cup C$ .

$= x \in (A \cup B) \wedge x \in (A \cup C) \quad [4]$

SKIP

Going back to the relation $x \in A \lor x \in (B \cap C)$

Substituting $[3]$ and $[4]$ in $[2]$

$\Rightarrow (x \in (A \cup B) \wedge x \in (A \cup C)) \lor x \in (A \cup B) \wedge x \in (A \cup C)$

Simplifying the statement

$= x \in (A \cup B) \wedge x \in (A \cup C)$

Simplifying the statement

$= x \in (A \cup B) \cap (A \cup C) \quad [5]$

From the membership of $x$ in $[1]$ and $[5]$ , we can conclude that;

$\Rightarrow A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C) \quad [6]$

SKIP

Now we need to prove the opposite that $\\ (A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C) \\$ to complete the proof.

Assume an arbitrary element from the right-hand side intersection.

Let $y \in (A \cup B) \cap (A \cup C) \quad [7]$

SKIP

CASE 1: $y \in A$

If $y$ is in $A$ , where else must it belong?

if $y \in A$ , then it must be that $y \in A \cup (B \cap C) \quad [8]$

SKIP

CASE 2: $y \notin A$

SKIP

if $y \in (A \cup B) \cap (A \cup C)$ but $y \notin A$

From the above, what can we conclude about $y$ ?

$\Rightarrow y \in B$ and $y \in C$

What does that imply about $y$ ?

$\Rightarrow y \in (B \cap C)$

If $y$ is in $B \cap C$ , where else must it belong?

if $y \in (B \cap C)$ , then it must be that $y \in A \cup (B \cap C) \quad [9]$

From $[8]$ and $[9]$ , we can conclude that;

$y \in A \cup (B \cap C) \quad [10]$

From the membership of $y$ from $[7]$ and $[10]$ , we can conclude that:

$\Rightarrow (A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C) \quad [11]$

From $[6]$ and $[11]$ , we can conclude the following from the two subset relations;

$\Rightarrow A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

SKIP

Proven!

The same steps can be taken to prove $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ . That proof is left to the student.

Prove that $(A \cup B)^c = A^c \cap B^c$

Start by assuming an arbitrary element of the left-hand side.

Let $x \in (A \cup B)^{c} \quad [1]$

Unpack the complement of a union into a statement about non-membership.

$\Rightarrow x \notin A \;\wedge\; x \notin B \quad [2]$

Restate non-membership using complements.

$\Rightarrow x \in A^{c} \;\wedge\; x \in B^{c} \quad [3]$

Change $\wedge$ to intersection.

$\Rightarrow x \in A^{c} \cap B^{c} \quad [4]$

Conclude the subset direction.

$\Rightarrow (A \cup B)^{c} \subseteq A^{c} \cap B^{c} \quad [5]$

SKIP

Now prove the reverse inclusion to complete the equality.

Assume an arbitrary element of the right-hand side.

Let $y \in A^{c} \cap B^{c} \quad [6]$

Unpack the intersection.

$\Rightarrow y \in A^{c} \;\wedge\; y \in B^{c} \quad [7]$

Translate membership in complements to non-membership.

$\Rightarrow y \notin A \;\wedge\; y \notin B \quad [8]$

Conclude non-membership in the union.

$\Rightarrow y \notin (A \cup B) \quad [9]$

Return to complement notation.

$\Rightarrow y \in (A \cup B)^{c} \quad [10]$

Conclude the second subset direction.

$\Rightarrow A^{c} \cap B^{c} \subseteq (A \cup B)^{c} \quad [11]$

Combine the two inclusions.

$\Rightarrow (A \cup B)^{c} = A^{c} \cap B^{c}$

SKIP

Proven!

The same steps can be taken to prove $(A \cap B)^c = A^c \cup B^c$ . That proof is left to the student.

Visualizing Proofs Using Venn Diagrams

End of Lesson

Properties of Set Operations

Commutativity

Associativity

Proof for Associativity of Union

Distributivity Properties:

Prove that A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)A∪(B∩C)=(A∪B)∩(A∪C)

Prove that (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c(A∪B)c=Ac∩Bc

Visualizing Proofs Using Venn Diagrams

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

Prove that $(A \cup B)^c = A^c \cap B^c$