Introduction
Set identities establish equivalences between expressions composed of set operations: union (∪), intersection (∩), and complement ('). They provide a toolkit for simplifying, transforming, and proving properties in set theory and discrete mathematics. Usage spans logic, computer science, probability, and database theory.
"Mathematics is the art of giving the same name to different things." -- Henri Poincaré
Basic Set Operations
Union (∪)
Definition: A ∪ B = {x | x ∈ A or x ∈ B}. Operation: combines elements of A and B.
Intersection (∩)
Definition: A ∩ B = {x | x ∈ A and x ∈ B}. Operation: common elements only.
Complement (')
Definition: A' = {x | x ∉ A} relative to universal set U. Operation: elements not in A.
Identity Laws
Union Identity
A ∪ ∅ = A. Union with empty set leaves A unchanged.
Intersection Identity
A ∩ U = A. Intersection with universal set leaves A unchanged.
Summary
Identity elements: ∅ for union, U for intersection.
A ∪ ∅ = AA ∩ U = ADomination Laws
Union Domination
A ∪ U = U. Union with universal set dominates.
Intersection Domination
A ∩ ∅ = ∅. Intersection with empty set dominates.
A ∪ U = UA ∩ ∅ = ∅Idempotent Laws
Union Idempotent
A ∪ A = A. Repeated union has no effect.
Intersection Idempotent
A ∩ A = A. Repeated intersection has no effect.
A ∪ A = AA ∩ A = AComplement Laws
Complement of Universal and Empty Sets
U' = ∅, ∅' = U.
Complement Interaction
A ∪ A' = U, A ∩ A' = ∅.
| Expression | Result | Explanation |
|---|---|---|
| U' | ∅ | Complement of universal set is empty set |
| ∅' | U | Complement of empty set is universal set |
| A ∪ A' | U | Union of set and complement is universal set |
| A ∩ A' | ∅ | Intersection of set and complement is empty set |
Double Complement Law
Definition
Taking complement twice returns original set: (A')' = A.
Proof Sketch
Elements not in complement of A are exactly those in A.
Associative Laws
Union Associativity
(A ∪ B) ∪ C = A ∪ (B ∪ C). Grouping does not change union.
Intersection Associativity
(A ∩ B) ∩ C = A ∩ (B ∩ C). Grouping does not change intersection.
(A ∪ B) ∪ C = A ∪ (B ∪ C)(A ∩ B) ∩ C = A ∩ (B ∩ C)Commutative Laws
Union Commutativity
A ∪ B = B ∪ A. Order does not affect union.
Intersection Commutativity
A ∩ B = B ∩ A. Order does not affect intersection.
A ∪ B = B ∪ AA ∩ B = B ∩ ADistributive Laws
Intersection Distributes over Union
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Union Distributes over Intersection
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
| Law | Expression |
|---|---|
| Intersection over Union | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
| Union over Intersection | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) |
Absorption Laws
Union Absorption
A ∪ (A ∩ B) = A. Union with intersection absorbed by A.
Intersection Absorption
A ∩ (A ∪ B) = A. Intersection with union absorbed by A.
A ∪ (A ∩ B) = AA ∩ (A ∪ B) = ADe Morgan's Laws
First Law
(A ∪ B)' = A' ∩ B'. Complement of union is intersection of complements.
Second Law
(A ∩ B)' = A' ∪ B'. Complement of intersection is union of complements.
Significance
Critical in logic, set theory, Boolean algebra for simplification and duality.
(A ∪ B)' = A' ∩ B'(A ∩ B)' = A' ∪ B'References
- Halmos, P.R., Naive Set Theory, Springer, 1974, pp. 20-45.
- Rosen, K.H., Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill, 2012, pp. 45-75.
- Enderton, H.B., Elements of Set Theory, Academic Press, 1977, pp. 30-60.
- Grimaldi, R.P., Discrete and Combinatorial Mathematics, 5th ed., Pearson, 2003, pp. 110-140.
- Velleman, D.J., How to Prove It: A Structured Approach, 2nd ed., Cambridge University Press, 2006, pp. 50-80.