Source: CS 18200 Foundations of Computer Science, Purdue University
Tags: set operations, set difference, complement, Cartesian product, power set, set identity proof, element argument, injective, surjective, bijective, ceiling function, function composition, inverse function, summation formulas
Difficulty: Intermediate
Prerequisites: Propositional logic study notes (for reading set identity proofs). Familiarity with basic set notation ({}, ∈, ⊆).
Sets are the building blocks of discrete mathematics. Nearly every structure in computer science (graphs, relations, databases, type systems) is defined in terms of sets. Functions formalise the idea of a mapping from one set to another, which is the abstraction behind every procedure, hash map, and database lookup. This section ties the two together: you learn to manipulate sets algebraically, then study the properties of mappings between them. Mastering set proofs and function classification (injective, surjective, bijective) is essential before moving on to relations, counting, and algorithm analysis later in the course.
Set operations (union, intersection, difference, complement, Cartesian product, power set) follow rules that parallel propositional logic. Proving set identities typically uses an element-chasing argument: pick an arbitrary element from one side and show it belongs to the other. Functions between sets can be injective (one-to-one), surjective (onto), or bijective (both), and these properties determine whether inverses exist.
Set difference (A − B)
The set of elements in A that are not in B. Formally, A − B = {x : x ∈ A ∧ x ∉ B}. In simple terms, start with A and remove anything that also appears in B.
Complement (Ā or A^c)
The set of elements in the universal set U that are not in A. Think of it as "everything outside A."
Cartesian product (A × B)
The set of all ordered pairs (a, b) where a ∈ A and b ∈ B. If |A| = m and |B| = n, then |A × B| = mn.
Power set (P(A))
The set of all subsets of A, including the empty set and A itself. If |A| = n, then |P(A)| = 2ⁿ. In simple terms, every possible combination of including or excluding each element.
Injective (one-to-one)
A function f : A → B is injective if different inputs always produce different outputs. Formally, f(x₁) = f(x₂) implies x₁ = x₂.
Surjective (onto)
A function f : A → B is surjective if every element of B is hit by some element of A. Formally, for every b ∈ B there exists a ∈ A such that f(a) = b.
Bijective (one-to-one correspondence)
A function that is both injective and surjective. Bijections have inverses. Think of it as a perfect pairing between elements of A and B.
Ceiling function (⌈x⌉)
The smallest integer greater than or equal to x. For instance, ⌈2.3⌉ = 3 and ⌈5⌉ = 5.
Function composition (h ∘ g)
Applying g first, then h. (h ∘ g)(x) = h(g(x)). The output of g feeds into h.
Inverse function (f⁻¹)
Exists only when f is a bijection. If f(a) = b, then f⁻¹(b) = a. For compositions, (h ∘ g)⁻¹ = g⁻¹ ∘ h⁻¹ (note the reversed order).
Given A = {1, 3, 6}, B = {6, 7}, and U = {1, 2, 3, 4, 5, 6, 7, 8, 9}:
B − Ā: First find Ā = U − A = {2, 4, 5, 7, 8, 9}. Then B − Ā = elements in B not in Ā = {6}. (7 is in both B and Ā, so it is removed.)
B × A: All ordered pairs with first element from B, second from A: {(6,1), (6,3), (6,6), (7,1), (7,3), (7,6)}. Six pairs, since |B| × |A| = 2 × 3 = 6.
P(B): All subsets of {6, 7}: {∅, {6}, {7}, {6, 7}}. Four subsets, since 2² = 4.
The standard technique: take an arbitrary element from one side, use definitions and set laws to show it belongs to the other side, then repeat in the opposite direction (or chain equalities).
Worked example: Show (A − B) − C = (A − C) − (B − C).
Strategy: start from the right side (A − C) − (B − C) and work toward the left.
Let s ∈ (A − C) − (B − C). By definition of set difference, s ∈ (A − C) and s ∉ (B − C).
Rewrite using complements: s ∈ A ∩ C̄ and s ∉ B ∩ C̄.
"s ∉ B ∩ C̄" means s ∈ complement of (B ∩ C̄) = B̄ ∪ C (De Morgan's).
Combine: s ∈ A ∩ C̄ ∩ (B̄ ∪ C).
Distribute C̄ into (B̄ ∪ C): get A ∩ ((C̄ ∩ B̄) ∪ (C̄ ∩ C)). Since C̄ ∩ C = ∅, this simplifies to A ∩ C̄ ∩ B̄.
Regroup: (A ∩ B̄) ∩ C̄ = (A − B) − C.
The key laws used: De Morgan's for sets, distributivity of intersection over union, and the complement-intersection identity X ∩ X̄ = ∅.
Worked example: f : ℝ⁺ → ℤ⁺ ∪ {0} defined by f(x) = ⌈x⌉ − 1.
Showing f is not injective:
Pick x₁ = 0.5 and x₂ = 1.
f(0.5) = ⌈0.5⌉ − 1 = 1 − 1 = 0.
f(1) = ⌈1⌉ − 1 = 1 − 1 = 0.
Same output, different inputs. Therefore f is not injective.
The ceiling function collapses nearby values into the same integer, which is why injectivity fails.
Showing f is surjective:
Let b ∈ ℤ⁺ ∪ {0}. Need to find some a ∈ ℝ⁺ with f(a) = b.
Choose a = b + 1. Then a is a positive real number and f(a) = ⌈b + 1⌉ − 1 = (b + 1) − 1 = b.
Every element of the codomain is hit, so f is surjective.
Given g : A → B and h : B → C:
h ∘ g is invertible when both g and h are bijections (and consequently A = C in terms of the domain/codomain pairing needed for the inverse to map C back to A).
The inverse reverses the order: (h ∘ g)⁻¹ = g⁻¹ ∘ h⁻¹. Think of it like removing layers: the last function applied is the first one undone.
Worked example: Evaluate ∑(i=7 to 19) [i + 2(1/2)ⁱ].
Split into two sums:
Arithmetic part: ∑(i=7 to 19) i = ∑(i=1 to 19) i − ∑(i=1 to 6) i = (19)(20)/2 − (6)(7)/2 = 190 − 21 = 169.
Geometric part: ∑(i=7 to 19) 2(1/2)ⁱ = 2[∑(i=0 to 19)(1/2)ⁱ − ∑(i=0 to 6)(1/2)ⁱ]. Apply the geometric series formula ∑(i=0 to n) rⁱ = (rⁿ⁺¹ − 1)/(r − 1).
After simplification, the result is 169 + (1/2)⁵ − (1/2)¹⁸.
Useful formulas to memorise:
∑(i=1 to n) i = n(n+1)/2
∑(i=0 to n) rⁱ = (rⁿ⁺¹ − 1)/(r − 1) for r ≠ 1
Arithmetic series: ∑(i=1 to n) i = n(n+1)/2
Geometric series: ∑(i=0 to n) rⁱ = (rⁿ⁺¹ − 1)/(r − 1), r ≠ 1
Set difference in terms of intersection: A − B = A ∩ B̄
De Morgan's laws for sets: complement of (A ∩ B) = Ā ∪ B̄, and complement of (A ∪ B) = Ā ∩ B̄
Power set cardinality: |P(A)| = 2^|A|
Cartesian product cardinality: |A × B| = |A| · |B|
Composition inverse: (h ∘ g)⁻¹ = g⁻¹ ∘ h⁻¹
Set operations are the backbone of database queries: SQL's UNION, INTERSECT, and EXCEPT map directly to ∪, ∩, and −. Understanding injective and surjective functions matters in cryptography (encryption functions should be bijections so decryption is possible) and in hash table design (hash functions are typically surjective but not injective, which is why collisions occur).
Students often confuse A − B with B − A. Set difference is not commutative. Always check which set you are "starting from."
When listing a Cartesian product, the order within each pair matters: (6, 1) and (1, 6) are different elements. A × B ≠ B × A unless A = B.
Students sometimes forget that the power set includes the empty set. P({6, 7}) has four elements, not three.
For surjectivity proofs, students sometimes pick an arbitrary element from the domain instead of the codomain. The proof requires starting with an arbitrary b in the codomain and finding a pre-image.
⚠️ Set identity proofs using the element-chasing method are a frequent exam question. Show every step and cite the law you are using (De Morgan's, distributivity, complement).
⚠️ Injectivity disproof requires a concrete counterexample (two specific inputs with the same output). Surjectivity proof requires a general construction for an arbitrary codomain element.
⚠️ Summation evaluation requires splitting sums and applying closed-form formulas. Memorise the arithmetic and geometric series formulas.
⚠️ The inverse of a composition reverses the order. This is tested both as a formula and conceptually.
True or false: P(∅) = ∅.
False. P(∅) = {∅}, which contains one element (the empty set itself).
Fill in the blank: |A × B| = ___ when |A| = 4 and |B| = 3.
True or false: A function f : A → B can be surjective even if |A| < |B|.
False. You need at least as many inputs as outputs to cover every element of B.
Fill in the blank: (h ∘ g)⁻¹ = ___ ∘ ___.
g⁻¹ ∘ h⁻¹.
Q: Let A = {a, b} and B = {1, 2, 3}. List all elements of A × B and state |P(A × B)|.
A: A × B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}. Since |A × B| = 6, we have |P(A × B)| = 2⁶ = 64.
Q: Prove or disprove: the function f : ℤ → ℤ defined by f(x) = x² is injective.
A: Disprove. f(1) = 1 and f(−1) = 1, but 1 ≠ −1. So f is not injective.
Q: Using the element-chasing method, show that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
A: Let x ∈ A ∩ (B ∪ C). Then x ∈ A and x ∈ B ∪ C. So x ∈ B or x ∈ C (or both). If x ∈ B, then x ∈ A ∩ B. If x ∈ C, then x ∈ A ∩ C. Either way, x ∈ (A ∩ B) ∪ (A ∩ C). The reverse direction is symmetric.
Q: Evaluate ∑(i=1 to 10) i.
A: 10(11)/2 = 55.
Set operations connect back to propositional logic (∩ corresponds to ∧, ∪ to ∨, complement to ¬) and forward to relations and graph theory, where a relation is defined as a subset of a Cartesian product. Functions and their properties (injectivity, surjectivity) reappear in counting and combinatorics when establishing bijections to prove two sets have the same cardinality. Summation evaluation is essential for the growth-of-functions analysis covered next.
set theory, set difference, set complement, Cartesian product, cross product, ordered pair, power set, subset, element-chasing proof, set identity, De Morgan's laws sets, injective function, one-to-one, surjective function, onto, bijection, ceiling function, floor function, function composition, inverse function, arithmetic series, geometric series, summation, CS 18200, discrete math sets, discrete math functions, Purdue