Set Theory studies collections of distinct objects (elements), foundational for database design, programming, and algorithms.
1. Basic Concepts
- Set: Unique items, e.g., {1,2,3}.
- Universal Set (U): All objects under consideration.
- Empty Set (β
): No elements.
- Subset (A β B): All elements of A are in B.
- Proper Subset (A β B): A β B and A β B.
2. Core Operations & Notations
- Union (A βͺ B): Elements in A or B, e.g., {1,2} βͺ {2,3} = {1,2,3}.
- Intersection (A β© B): Elements in both, e.g., {1,2} β© {2,3} = {2}.
- Difference (A β B): Elements in A not in B, e.g., {1,2,3} β {2,4} = {1,3}.
- Complement (AαΆ): Elements in U not in A, e.g., U = {1,...,6}, A = {1,2}, AαΆ = {3,4,5,6}.
3. Key Properties
- Commutative: A βͺ B = B βͺ A; A β© B = B β© A.
- Associative: (A βͺ B) βͺ C = A βͺ (B βͺ C); (A β© B) β© C = A β© (B β© C).
- Distributive: A β© (B βͺ C) = (A β© B) βͺ (A β© C); A βͺ (B β© C) = (A βͺ B) β© (A βͺ C).
- De Morganβs Laws: (A βͺ B)αΆ = AαΆ β© BαΆ; (A β© B)αΆ = AαΆ βͺ BαΆ.
4. Beyond Basics
- Power Set (π«(S)): All subsets of S.
- Cardinality (|A|): Number of elements in A.
- Cartesian Product (A Γ B): Ordered pairs (a,b), a β A, b β B.
- Symmetric Difference (A Ξ B): Elements in exactly one of A or B.
5. Computing Applications
- Databases: UNION, INTERSECT, EXCEPT mirror set operations.
- Data Structures: Sets, hash tables, relational models.
- Algorithms: Logic, reasoning, query optimization.