Algebra of Sets

---

---

---

The algebra of sets describes basic laws on set operations: union, intersection, complement and other relations, which are mentioned as below.
Let \(A, B,C\) be subsets of a universal set \(U\) then

Laws	Identities
	Over union	Over Intersection
Idempotent Laws	\(A \cup A = A\)	\(A \cap A = A\)
Identities Laws	\(A \cup U = U , A \cup \phi = A\)	\(A \cap U = A , A \cap \phi = \phi \)
Complement Laws	\(A\cup \overline{A} = U , \overline{(\overline{A} )}=A\)	\(A \cap \overline{A} = \phi , \overline{U}=\phi \)
Commutative Laws	\( A \cup B = B \cup A\)	\(A \cap B = B \cap A\)
Associative Laws	\(( A \cup B )\cup C = A\cup (B\cup A)\)	\((A\cap B)\cap C=A\cap (B\cap A)\)
Distributive Laws	\(A\cup (B\cap C)=( A \cup B )\cap (A\cup C)\)	\(A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\)
De-Morgan’s Laws	\(\overline{(A\cup B)}=\overline{A} \cap \overline{B}\)	\(\overline{(A\cup B)}=\overline{A} \cap \overline{B}\)

Prove that \((A \cap B)'=A' \cup B' \)

Proof

1. Inductive method (example)
   Let \(U = \{1, 2, 3, 4, 5, 6\}\) be the universal set with \(A = \{1, 2, 3, 4\}, B = \{3, 4, 5, 6\}\)
   , then
   1. Calculate \( A \cap B = \{3, 4\}\)
   2. Calculate \((A \cap B)' = U \setminus (A \cap B) = \{1, 2, 5, 6\}\) (1)
   3. Calculate \( A' = U \setminus A = \{5, 6\}\)
   4. Calculate \(B' = U \setminus B = \{1, 2\}\)
   5. Calculate \( A' \cup B' = \{1, 2\} \cup \{5, 6\} = \{1, 2, 5, 6\}\) (2)
   6. Conclusion: \((A \cap B)' = \{1, 2, 5, 6\} = A' \cup B'\)
2. Venn-diagram method (figure)
3. Tabular method (logic)
4. Deductive method (set-builder)
   Let \(x\in (A\cap B)'\) then
   \(x \notin (A\cap B)\)
   or\(x \notin A \text{ or } x \notin B\)
   or\(x \in A' \text{ or } x \in B'\)
   or\(x \in (A' \cup B')\)
   Hence, \((A\cap B)'=A'\cup B'\)