Set Concepts
What Is a Set?
A set is an unordered collection of distinct elements. Sets group objects that share (or are selected by) some property. Sets are the foundational structure of discrete mathematics.
Representing Sets
1. Roster (Tabular) Form
List all elements, separated by commas, enclosed in curly braces.
Examples:
- First six natural numbers: N = {1, 2, 3, 4, 5, 6}
- Vowels: V = {a, e, i, o, u}
- Even numbers less than 9: X = {2, 4, 6, 8}
2. Set-Builder Notation
Describe all elements using a rule or condition.
Examples:
- P = {x | x is a counting number and x > 12}
- A = {x | x is an even number, 4 < x < 16}
3. Cardinality
The cardinality of a set is its size — the number of distinct elements. Written as |A|.
Examples:
- A = {2, 4, 6, 8, 12} → |A| = 5
- B = {1, 2, 3, 3, 4, 6, 8} → |B| = 6 (3 appears twice but counts once)
Set Operations
Union (∪)
All elements belonging to either set A or set B (or both).
A ∪ B = {x | x ∈ A or x ∈ B}
Example: A = {1, 2, 5, 8}, B = {1, 3, 4, 6, 7} A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8}
Intersection (∩)
Only the elements that appear in both A and B.
A ∩ B = {x | x ∈ A and x ∈ B}
Example: A = {1, 2, 3, 4}, B = {2, 4, 6, 8} A ∩ B = {2, 4}
Complement (Aᶜ or A')
All elements in the universal set U that are not in A.
Example: A = {1, 2, 3, 4}, U = {1, 2, 3, 4, 5, 6, 7, 8} A' = {5, 6, 7, 8}
Difference (A − B)
Elements in A that are not in B.
A − B = {x | x ∈ A and x ∉ B}
Example: A = {1, 2, 3, 4, 5}, B = {3, 4} A − B = {1, 2, 5}
Cartesian Product (A × B)
The set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
|A × B| = |A| × |B|
Example: A = {1, 2}, B = {a, b} A × B = {(1,a), (1,b), (2,a), (2,b)}
De Morgan's Laws for Sets
- (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
- (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
These mirror De Morgan's laws for propositional logic.
Inclusion-Exclusion Principle
When counting the union of two sets where some elements overlap:
|A ∪ B| = |A| + |B| − |A ∩ B|
For three sets:
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|