1.1 What is a Set?
A set is a well-defined, unordered collection of distinct objects, called its elements. "Well-defined" means membership is never ambiguous: for any object x and set A, exactly one of x ∈ A or x ∉ A holds.
Two standard ways to describe a set:
- Roster form: V = {a, e, i, o, u}
- Set-builder form: A = {x | x ∈ Z and 0 < x ≤ 5} = {1, 2, 3, 4, 5}
The cardinality |A| is the number of elements in A. Standard sets: N (naturals), Z (integers), Q (rationals), R (reals).
1.2 Types of Sets
| Type | Definition | Example | ||||
|---|---|---|---|---|---|---|
| Empty set ∅ | Contains no elements; | ∅ | = 0 | {x ∈ R | x^2 = −1} | |
| Singleton | Exactly one element | {0} — note {0} ≠ ∅ | ||||
| Finite / Infinite | Cardinality is / is not a natural number | {1,2,3} vs N | ||||
| Equal sets | A = B iff A ⊆ B and B ⊆ A | {1,2} = {2,1,1} | ||||
| Equivalent sets | A | = | B | (same size, elements may differ) | {1,2,3} and {a,b,c} | |
| Subset | A ⊆ B iff every x ∈ A is also in B | {1,2} ⊆ {1,2,3} | ||||
| Proper subset | A ⊂ B iff A ⊆ B and A ≠ B | {1,2} ⊂ {1,2,3} | ||||
| Universal set U | The set of all objects under discussion | All BCA students | ||||
| Disjoint sets | A ∩ B = ∅ | Even and odd integers |
Key facts: ∅ ⊆ A for every set A, and A ⊆ A (so every non-empty set has at least two subsets).
1.3 Power Set and Cartesian Product
The power set P(A) is the set of all subsets of A. If |A| = n, then |P(A)| = 2^n, because each of the n elements is independently in or out of a subset.
Example: A = {1, 2, 3} → P(A) = { ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }, and |P(A)| = 2^3 = 8.
The Cartesian product A × B = {(a, b) | a ∈ A, b ∈ B} is the set of ordered pairs. |A × B| = |A| · |B|, and in general A × B ≠ B × A because pairs are ordered.
Example: A = {1, 2}, B = {x, y, z} → A × B has 2 · 3 = 6 pairs: (1,x), (1,y), (1,z), (2,x), (2,y), (2,z).
1.4 Set Operations
| Operation | Definition | For A = {1,2,3}, B = {3,4} in U = {1..6} | |
|---|---|---|---|
| Union A ∪ B | {x | x ∈ A or x ∈ B} | {1,2,3,4} |
| Intersection A ∩ B | {x | x ∈ A and x ∈ B} | {3} |
| Difference A − B | {x | x ∈ A and x ∉ B} | {1,2} |
| Symmetric difference A ⊕ B | (A − B) ∪ (B − A) | {1,2,4} | |
| Complement A' | U − A | {4,5,6} |
Laws of set algebra (each has a dual obtained by swapping ∪↔∩ and ∅↔U): commutative, associative, distributive A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), identity (A ∪ ∅ = A), idempotent (A ∪ A = A), absorption A ∪ (A ∩ B) = A, involution (A')' = A, and De Morgan's laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'.
1.5 Worked Example 1 — Proving De Morgan's Law
Prove: (A ∪ B)' = A' ∩ B'. We show mutual inclusion using the element method:
- Let x ∈ (A ∪ B)'. Then x ∉ A ∪ B, i.e., it is not true that (x ∈ A or x ∈ B).
- By De Morgan's law of logic, x ∉ A and x ∉ B.
- Hence x ∈ A' and x ∈ B', so x ∈ A' ∩ B'. Therefore (A ∪ B)' ⊆ A' ∩ B'.
- Conversely, let x ∈ A' ∩ B'. Then x ∉ A and x ∉ B, so x cannot belong to A ∪ B, i.e., x ∈ (A ∪ B)'. Therefore A' ∩ B' ⊆ (A ∪ B)'.
- Both inclusions hold, so the sets are equal. ∎
1.6 Worked Example 2 — Inclusion–Exclusion (Venn Counting)
For finite sets, |A ∪ B| = |A| + |B| − |A ∩ B| (the overlap is counted twice, so subtract it once).
Problem: In a class of 60 students, 32 like Java, 27 like Python, and 15 like both. How many like (a) at least one, (b) only Java, (c) neither?
- |J ∪ P| = 32 + 27 − 15 = 44 like at least one language.
- Only Java = |J| − |J ∩ P| = 32 − 15 = 17.
- Neither = 60 − 44 = 16.
For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ C|.
1.7 Common Mistakes & CS Applications
- ∈ vs ⊆: 1 ∈ {1,2} but {1} ⊆ {1,2}. Writing 1 ⊆ {1,2} is wrong.
- ∅ ≠ {∅}: the second is a singleton containing the empty set; |{∅}| = 1.
- A − B ≠ B − A in general; set difference is not commutative.
- Applications: SQL UNION/INTERSECT/EXCEPT are literal set operations; a 32-bit integer used as a bitset performs A ∪ B as bitwise OR and A ∩ B as AND in one CPU instruction; type systems model subtyping as ⊆; De Morgan's laws let compilers rewrite negated compound conditions.
🎯 Exam Focus
- Define power set. If A = {a, {b}}, list P(A) and state |P(A × A)|.
- Prove De Morgan's law (A ∩ B)' = A' ∪ B' using the element method.
- Prove that A − (B ∪ C) = (A − B) ∩ (A − C).
- Out of 120 students, 65 read C, 45 read C++, 42 read Java, 20 read C and C++, 25 read C and Java, 15 read C++ and Java, and 8 read all three. How many read none of the three?
- If |A| = m and |B| = n, how many subsets of A × B exist? Justify.
- State the absorption laws and verify A ∪ (A ∩ B) = A with a membership table.