Fundamental laws of algebra of sets

The laws of algebra of sets describe the properties of set operations and relations. These laws help simplify set expressions without changing their meaning.

Summary of the laws

Let $A$, $B$, and $C$ be non-empty sets. The following are fundamental laws of set algebra:

S/N	Set Notation	Law Type
1.	$A \cup \emptyset = A$; $A \cap U = A$; $A \cup U = U$; $A \cap \emptyset = \emptyset$	Identity / Domination
2.	$A \cup A = A$; $A \cap A = A$	Idempotent
3.	$(A')' = A$	Double Complement
4.	$A \cup B = B \cup A$; $A \cap B = B \cap A$	Commutative
5.	$A \cup (B \cup C) = (A \cup B) \cup C$; $A \cap (B \cap C) = (A \cap B) \cap C$	Associative
6.	$(A \cup B)' = A' \cap B'$; $(A \cap B)' = A' \cup B'$	De Morgan's
7.	$A \cup (A \cap B) = A$; $A \cap (A \cup B) = A$	Absorption
8.	$A \cup A' = U$, where $U$ is the universal set; $A \cap A' = \emptyset$; $U' = \emptyset$	Complement
9.	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$; $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$	Distributive

Selected proofs

a. Idempotent law

Given a set $A$:

• $A \cup A = A$
• $A \cap A = A$

Proof:

By definition:

• $x \in A \cup A \iff x \in A \text{ or } x \in A \Rightarrow x \in A$
• $x \in A \cap A \iff x \in A \text{ and } x \in A \Rightarrow x \in A$

Thus, both identities hold.

b. Commutative law

For sets $A$ and $B$:

• $A \cup B = B \cup A$
• $A \cap B = B \cap A$

Proof:

Let $x \in A \cup B \Rightarrow x \in A$ or $x \in B \Rightarrow x \in B \cup A$.

Similarly, $x \in B \cup A \Rightarrow x \in A \cup B$.

So $A \cup B = B \cup A$, and likewise for $\cap$.

c. Associative law

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

Proof:

Let $x \in A \cup (B \cup C) \Rightarrow x \in A$ or $x \in B \cup C$.

That implies $x \in (A \cup B) \cup C$. The reverse direction follows similarly.

d. Distributive law

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

Proof:

Let $x \in A \cap (B \cup C) \Rightarrow x \in A$ and $x \in B \cup C$.

Then $x \in A \cap B$ or $x \in A \cap C \Rightarrow x \in (A \cap B) \cup (A \cap C)$.

Reverse is also true, hence the sets are equal.

e. De Morgan's laws

• $(A \cup B)' = A' \cap B'$
• $(A \cap B)' = A' \cup B'$

Proof:

Let $x \in (A \cup B)' \Rightarrow x \notin A \cup B \Rightarrow x \notin A$ and $x \notin B \Rightarrow x \in A' \cap B'$.

Hence, $(A \cup B)' = A' \cap B'$. The other law is proved similarly.

f. Complement law

• $A \cup A' = U$
• $A \cap A' = \emptyset$
• $U' = \emptyset$
• $\emptyset' = U$

g. Identity/Domination law

• $A \cup \emptyset = A$
• $A \cap U = A$
• $A \cup U = U$
• $A \cap \emptyset = \emptyset$

h. Double complement law

• $(A')' = A$

Proof:

If $x \in (A')'$, then $x \notin A' \Rightarrow x \in A$. Hence, $(A')' = A$.

i. Absorption law

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