3.1 Functions as Special Relations

A function f: A → B is a relation from A to B in which every element of A is related to exactly one element of B. A is the domain, B the codomain, and the range f(A) = {f(a) | a ∈ A} ⊆ B is the set of values actually hit.

Not every relation is a function: R = {(1, x), (1, y)} fails (1 has two images); R = {(1, x)} on domain {1, 2} fails (2 has no image).

3.2 Types of Functions

Counts, for |A| = m, |B| = n: total functions = n^m; injections require m ≤ n and number P(n, m); bijections require m = n and number n!.

Note: f(x) = x^2 on R → R is neither injective (f(2) = f(−2) = 4) nor surjective (−1 is never hit). Restricting to f: [0, ∞) → [0, ∞) makes it bijective — injectivity and surjectivity depend on the declared domain and codomain, not just the formula.

3.3 Composition of Functions

Given f: A → B and g: B → C, the composition (g ∘ f)(x) = g(f(x)) maps A → C. Composition is associative but not commutative.

Numeric check: f(x) = x^2 and g(x) = x + 1.

• (f ∘ g)(x) = f(x + 1) = (x + 1)^2, so (f ∘ g)(2) = 9.
• (g ∘ f)(x) = x^2 + 1, so (g ∘ f)(2) = 5. Hence f ∘ g ≠ g ∘ f.

Useful theorems: if f and g are both injective, g ∘ f is injective; if both surjective, g ∘ f is surjective.

3.4 Worked Example 1 — Prove Bijective and Find the Inverse

Problem: Show f: R → R, f(x) = 3x + 2 is a bijection and find f⁻¹.

1. Injective: suppose f(x1) = f(x2). Then 3x1 + 2 = 3x2 + 2 → 3x1 = 3x2 → x1 = x2. ✔
2. Surjective: take any y ∈ R. Solve y = 3x + 2 → x = (y − 2)/3, which is a real number, and f((y − 2)/3) = y. ✔
3. Therefore f is bijective and the inverse exists: f⁻¹(y) = (y − 2)/3.
4. Verify: (f⁻¹ ∘ f)(x) = f⁻¹(3x + 2) = (3x + 2 − 2)/3 = x. ✔ (A function has an inverse iff it is bijective.)

3.5 Floor and Ceiling

⌊x⌋ = greatest integer ≤ x; ⌈x⌉ = least integer ≥ x. So ⌊3.7⌋ = 3, ⌈3.2⌉ = 4, and — the classic trap — ⌊−1.5⌋ = −2, not −1. These appear throughout CS: a binary search on n elements makes at most ⌈log2(n + 1)⌉ comparisons; n items packed k-per-page need ⌈n/k⌉ pages.

3.6 The Pigeonhole Principle (PHP)

Simple form: if n + 1 or more objects are placed into n boxes, some box holds at least 2 objects. Generalized form: if N objects go into k boxes, some box holds at least ⌈N/k⌉ objects.

3.7 Worked Example 2 — Pigeonhole Arguments

(a) Among any 5 integers, two leave the same remainder on division by 4. The possible remainders are the 4 boxes {0, 1, 2, 3}; with 5 integers (pigeons), two must share a box. Consequence: their difference is divisible by 4.

(b) In a group of 100 people, at least ⌈100/12⌉ = 9 share a birth month. Boxes = 12 months, pigeons = 100 people; some month contains at least 9.

(c) Hashing: a hash table with m = 1000 slots receiving 1001 keys must have a collision — no clever hash function can avoid it. This is also why lossless compression cannot shrink every file: there are 2^n files of n bits but only 2^n − 1 shorter outputs, so two files would collide.

3.8 Common Mistakes

• Confusing codomain with range: surjectivity compares them; they may differ.
• Computing g ∘ f in the wrong order — apply the rightmost function first.
• Claiming f(x) = x^2 has inverse √x on all of R: it has no inverse there because it is not injective.

🎯 Exam Focus

1. Define injective, surjective, and bijective functions. Give an example of a function that is surjective but not injective on Z.
2. Let f(x) = 2x + 3 and g(x) = x^2 − 1 on R. Compute f ∘ g, g ∘ f, and (f ∘ g)(2). Are they equal?
3. Prove that f: R − {2} → R − {1}, f(x) = x/(x − 2) is a bijection and find f⁻¹.
4. State and prove the generalized pigeonhole principle.
5. Show that among any 8 distinct integers, two differ by a multiple of 7.
6. How many functions and how many injections exist from a 3-element set to a 5-element set? (Answers: 5^3 = 125 and P(5,3) = 60.)