Algebra of Sets: Understanding Set Operations and Their Laws
Explore the fundamental laws and properties governing set operations (union, intersection, complement). This guide provides a detailed explanation of these properties, proving key theorems, and illustrating their application in simplifying set expressions.
Algebra of Sets
Laws of Set Algebra
Set operations (union, intersection, complement) follow specific laws. Let A and B represent sets, U represent the universal set, and Ø represent the empty set. The complement of A is denoted as Ac.
| Law | Equation(s) |
|---|---|
| Idempotent Laws | A ∪ A = A A ∩ A = A |
| Associative Laws | (A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C) |
| Commutative Laws | A ∪ B = B ∪ A A ∩ B = B ∩ A |
| Distributive Laws | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
| De Morgan's Laws | (A ∪ B)c = Ac ∩ Bc (A ∩ B)c = Ac ∪ Bc |
| Identity Laws | A ∪ Ø = A A ∪ U = U A ∩ U = A A ∩ Ø = Ø |
| Complement Laws | A ∪ Ac = U A ∩ Ac = Ø Uc = Ø Øc = U |
| Involution Law | (Ac)c = A |
Proofs of Idempotent Laws
(a) A ∪ A = A
Since A ⊆ A ∪ A and if x ∈ A ∪ A, then x ∈ A or x ∈ A, which means x ∈ A. Therefore, A ∪ A ⊆ A. Since both A ⊆ A ∪ A and A ∪ A ⊆ A, we conclude A ∪ A = A.
(b) A ∩ A = A
Since A ∩ A ⊆ A, and if x ∈ A, then x ∈ A and x ∈ A, so x ∈ A ∩ A. Therefore, A ⊆ A ∩ A. Since both A ∩ A ⊆ A and A ⊆ A ∩ A, we conclude A ∩ A = A.
Proofs of Associative Laws
(a) (A ∪ B) ∪ C = A ∪ (B ∪ C)
If x ∈ (A ∪ B) ∪ C, then (x ∈ A or x ∈ B) or x ∈ C. This is equivalent to x ∈ A or (x ∈ B or x ∈ C), meaning x ∈ A ∪ (B ∪ C).
(b) (A ∩ B) ∩ C = A ∩ (B ∩ C)
If x ∈ (A ∩ B) ∩ C, then x ∈ A ∩ B and x ∈ C. This means x ∈ A and (x ∈ B and x ∈ C), which is equivalent to x ∈ A ∩ (B ∩ C).
Proofs of Commutative Laws
(a) A ∪ B = B ∪ A
The order of elements in a set doesn't matter; A ∪ B contains all elements in A or B, which is the same as B ∪ A.
(b) A ∩ B = B ∩ A
Similarly, A ∩ B contains all elements in both A and B, which is the same as B ∩ A.
Duality
The dual of a set equation is obtained by swapping ∪ and ∩, and swapping U and Ø.
Principle of Extension
Two sets are equal if and only if they contain the same elements.
Cartesian Product of Two Sets
The Cartesian product of sets P and Q (written P x Q) is the set of all possible ordered pairs (p, q) where p ∈ P and q ∈ Q.
(An illustrative example of a Cartesian product should be included here.)
Conclusion
These laws govern how we work with sets and are fundamental to many areas of mathematics and computer science.