Sets
A set is a well-defined collection of distinct objects. The word well-defined is key — it means there is no ambiguity about whether an object belongs to the collection or not.
A set is a collection of well-defined, distinct objects called elements or members. We write x ∈ A to say “x belongs to set A”, and x ∉ A to say “x does not belong to A.”
How to Write a Set
There are two standard ways to describe a set:
- Roster (Tabular) Form: List all elements inside curly braces separated by commas. Example: A = {1, 2, 3, 4, 5}
- Set-Builder Form: Describe the rule that elements must satisfy. Example: A = {x : x is a natural number less than 6} — read as “the set of all x such that x is a natural number less than 6.”
Types of Sets
∅ or { }
{7} or {Monday}
{2, 4, 6, 8}
ℕ = {1,2,3,...}
{1,2} = {2,1}
U = {1...10}
Roster form: List them out: {2, 4, 6, 8, 10}
Set-builder form: Describe the rule:
{x : x is even, 1 ≤ x ≤ 10}
Both forms represent the same set. Roster is easier to read; set-builder is more powerful for large or infinite sets.
Cardinality of a Set
The cardinality of a set A, written n(A) or |A|, is the number of elements it contains.
Subset and Superset
Once we understand what sets are, the next question is: how do sets relate to each other in terms of containment? This is where subsets and supersets come in.
Set A is a subset of set B, written A ⊆ B, if every element of A is also an element of B. In other words: if x ∈ A, then x ∈ B.
A is a proper subset of B, written A ⊂ B, if A ⊆ B and A ≠ B. That is, every element of A is in B, but B has at least one extra element.
Superset
If A ⊆ B, then B is called a superset of A, written B ⊇ A. The superset is the “bigger” set that contains A.
A ⊆ B? 1 ∈ B ✔ 2 ∈ B ✔ Yes, A ⊂ B (proper subset)
B ⊆ B? Every element of B is in B. Yes, B ⊆ B (every set is a subset of itself)
C ⊆ B? 4 ∉ B. No, C is NOT a subset of B.
A ⊂ B (proper), B ⊆ B (improper), C ⊈ B. Note: ∅ ⊆ every set.
Important Results about Subsets
- Every set is a subset of itself: A ⊆ A
- The empty set is a subset of every set: ∅ ⊆ A for any set A
- If A ⊆ B and B ⊆ A, then A = B
- If A ⊆ B and B ⊆ C, then A ⊆ C (transitivity)
- The number of subsets of a set with n elements is 2n
- The number of proper subsets is 2n − 1
The Power Set
The power set of A, written P(A), is the set of ALL subsets of A (including ∅ and A itself).
n(A) = 3, so P(A) has 23 = 8 subsets
List all subsets (by size): ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}
P(A) = { ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} } — 8 elements total.
Operations on Sets
Just as we add, subtract or multiply numbers, we can operate on sets to produce new sets. The four fundamental operations are Union, Intersection, Difference, and Complement.
Union (A ∪ B)
A ∪ B = { x : x ∈ A or x ∈ B } — all elements that belong to A, to B, or to both.
Intersection (A ∩ B)
A ∩ B = { x : x ∈ A and x ∈ B } — only elements that belong to BOTH A and B simultaneously.
Difference (A − B)
A − B = { x : x ∈ A and x ∉ B } — elements in A that are not in B. Also written A \ B.
Complement (A')
A' = { x : x ∈ U and x ∉ A } — everything in the universal set U that is not in A.
A∪B (all elements in either): {1,2,3,4,5,6}
A∩B (common elements only): {3,4}
A−B (in A, not in B): {1,2}
A' (in U, not in A): {5,6,7,8}
Notice B−A = {5,6} ≠ A−B = {1,2}. Set difference is NOT commutative.
Key Properties
A∩B = B∩A
A∩(B∩C) = (A∩B)∩C
De Morgan's Laws
These two laws are among the most important results in set theory. They connect complement with union and intersection:
In words: the complement of a union is the intersection of complements. The complement of an intersection is the union of complements.
n(M) = 25, n(P) = 20, n(M∩P) = 10
Apply formula: n(M∪P) = 25 + 20 − 10 = 35
35 students study at least one subject. The remaining 40 − 35 = 5 study neither.
Ordered Pair
When we pair two elements and the order matters, we get an ordered pair. This is different from a set, where {a, b} = {b, a}. In an ordered pair, (a, b) ≠ (b, a) unless a = b.
An ordered pair (a, b) is a pair of elements where a is the first component and b is the second component. Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Cartesian Product
The Cartesian product A × B is the set of all ordered pairs where the first element comes from A and the second from B.
A × B = { (a, b) : a ∈ A and b ∈ B }
Form all ordered pairs (a,b) where a∈A and b∈B:
A×B = {(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)}
Count: n(A×B) = 2 × 3 = 6
The Cartesian product has 6 ordered pairs. Note A×B ≠ B×A since (1,x) ≠ (x,1).
Why Ordered Pairs Matter
Ordered pairs are the backbone of coordinate geometry (every point on a graph is an ordered pair), relations, and functions. Whenever you plot (3, 5) on a graph, you are using an ordered pair from ℝ×ℝ.
Relation
A relation describes how elements from one set are connected to elements of another. Formally, it is a subset of the Cartesian product.
A relation R from set A to set B is any subset of A × B. We write aRb or
(a,b) ∈ R to say “a is related to b.”
The domain of R is the set
of first elements; the range is the set of second elements.
Types of Relations on a Set A
(a,a) ∈ R for all a∈A
(a,b)∈R ⇒ (b,a)∈R
aRb, bRc ⇒ aRc
Like “≤” on numbers
Like “=” on numbers
R = ∅
Reflexive: (1,1),(2,2),(3,3) ∈ R ✔ Yes, reflexive.
Symmetric: (1,2) ∈ R and (2,1) ∈ R ✔ Yes, symmetric.
Transitive: (1,2) and (2,1) ∈ R, so need (1,1) ∈ R ✔. Check all — holds. Yes, transitive.
R is reflexive, symmetric, and transitive — therefore R is an Equivalence Relation.
Number of Relations
If n(A) = p and n(B) = q, then n(A×B) = pq. The total number of possible relations from A to B is 2pq, since each relation is a subset of A×B.
Composition of Relations
Just as we compose functions, we can compose two relations to produce a third. If R relates A to B, and S relates B to C, then the composition R∘S (or SoR in some notations) relates A to C by chaining through B.
Let R be a relation from A to B, and S be a relation from B to C. The composition S
∘ R (read “S composed with R”) is a relation from A to C defined as:
S ∘ R = { (a, c) : ∃ b ∈ B such that (a,b) ∈ R and (b,c) ∈ S
}
How to Compute a Composition
Think of it as a two-step path: to get from a to c, you must first find an intermediate b such that a is R-related to b, and b is S-related to c.
Trace each element of A through R, then through S:
1: 1 → a (via R) → x (via S) so (1,x) ∈ S∘R
2: 2 → b (via R) → x (via S) so (2,x) ∈ S∘R
3: 3 → c (via R) → y (via S) so (3,y) ∈ S∘R
S ∘ R = { (1,x), (2,x), (3,y) } — a relation directly from A to C.
Key Properties of Composition
- Associativity: (T∘S)∘R = T∘(S∘R) — composition is associative
- Not Commutative: S∘R ≠ R∘S in general — the order matters
- Identity Relation: I∘R = R∘I = R, where I is the identity relation {(a,a) : a∈A}
Inverse of a Relation
The inverse of relation R, written R−1, swaps all pairs: R−1 = { (b,a) : (a,b) ∈ R }. If R is from A to B, then R−1 is from B to A.
Venn Diagram
A Venn diagram uses overlapping circles inside a rectangle (representing the universal set U) to visually represent sets and their relationships. They make abstract set operations instantly intuitive.
In a two-set Venn diagram with circles A and B:
• Circle A only (left crescent) = elements in A but not B = A−B
• Overlap (middle) = elements in both = A∩B
• Circle B only (right crescent) = elements in B but not A = B−A
• Outside both circles = elements in neither = (A∪B)'
Three-Set Venn Diagrams
When three sets A, B, C overlap, the diagram has 8 distinct regions. The inclusion-exclusion formula extends to:
Only Tea (left crescent): 60 − 30 = 30
Only Coffee (right crescent): 50 − 30 = 20
At least one: n(T∪C) = 60+50−30 = 80
Neither: 100 − 80 = 20
Only tea: 30 | Only coffee: 20 | Both: 30 | Neither: 20
Common Exam Tips for Venn Diagrams
- Always fill in the intersection region first, then work outward
- Use the inclusion-exclusion formula to find missing values
- The sum of all regions must equal n(U)
- A region cannot have a negative count — if it does, recheck your working