COMP233 · Chapter 7 Interactive Companion

Functions

What a function is, one-to-one and onto, bijections and inverses, composition, and the pigeonhole principle. Sections 7.1–7.3 and 9.4.
Back to COMP233

About this chapter

A function is the most-used object in mathematics and computing: a rule that turns each input into exactly one output. Chapter 6 built sets and Cartesian products; a function is just a special subset of a product X × Y, so this chapter stands directly on the last one.

The thread. Section 7.1 pins down what a function is (every input gets one output) and the vocabulary of image, range and inverse image. Section 7.2 asks two questions about the output side: can two inputs collide (one-to-one?) and is every target hit (onto?). Both at once is a bijection, which can be run backward to give an inverse. Section 7.3 chains functions together (composition), and 9.4 turns “not one-to-one” into a powerful counting tool, the pigeonhole principle.

Scope for the exam. Per the lecture notes, 7.1 and 7.2 are the examinable core – spend most of your practice time there. 7.3 (composition) and 9.4 (pigeonhole) are enrichment: useful, elegant, and worth knowing, but not primary exam targets.
Recorded lecture

Introduction to Functions (Section 7.1)

The full recorded session for section 7.1. Watch it alongside this companion: the “is it a function?” arrow-diagram checker, the function evaluator and the equality-of-functions demonstrator below let you practise each idea as it is introduced.

Section 7.1Introduction to functions

Definition · function
A function f : X → Y is a relation from the domain X to the co-domain Y satisfying two rules:
1. total – every x ∈ X is related to some element of Y, and
2. single-valued – no x is related to more than one element of Y.
So each x has a unique image f(x).

In an arrow diagram the two rules read simply: every left-hand element has exactly one arrow leaving it. The right side is unconstrained – a co-domain element may receive zero, one, or many arrows.

  • image of x: the value f(x).
  • range: { y ∈ Y | y = f(x) for some x }. Always range ⊆ co-domain, often strictly.
  • inverse image of y: { x ∈ X | f(x) = y }; it may be empty, one, or many.

7.1.1 Is it a function? – arrow-diagram checker

Enter a domain X, a co-domain Y, and the rule as x:y arrows. The checker applies the two rules (total and single-valued), and if it is a function reports the range and every inverse image. Try breaking it: drop an input (rule 1 fails) or give one input two arrows like c:2, c:3 (rule 2 fails). Based on Examples 7.1.1–7.1.2.

7.1.2 A zoo of functions – evaluator

Functions are everywhere: numbers, strings, subsets, bit-tuples. Pick one, give it an input, and see the output together with its domain, co-domain and range. These are Examples 7.1.6–7.1.11 from the notes.

Reading a diagram (Example 7.1.2). With f(a)=2, f(b)=4, f(c)=2: the range is {2, 4}; the inverse image of 2 is {a, c}; of 4 is {b}; of 1 is ∅ (nothing maps to 1). As ordered pairs, f = {(a,2),(b,4),(c,2)}. Two arrows reaching 2 is allowed; 1 and 3 being missed is allowed – only the left side is constrained.

7.1.3 Equality of functions (Theorem 7.1.1)

Two functions are equal exactly when they have the same domain, the same co-domain, and agree on every input.
Theorem 7.1.1 · a test for equality
If F : X → Y and G : X → Y are functions, then F = G  ⇔  F(x) = G(x) for all x ∈ X. (A function is its set of ordered pairs, so F and G contain the same pairs precisely when they agree at every input.)

Example 7.1.3(a) – two rules, one function. On J₃ = {0,1,2} take f(x) = (x²+x+1) mod 3 and g(x) = (x+2)² mod 3. The table below is computed live – the f and g columns are identical, so by Theorem 7.1.1, f = g even though the rules look nothing alike.

7.1.4 When a rule fails to be a function (well-defined)

A rule defines a function only if it gives every input exactly one unambiguous output. Two classic failures:
Not a function · the unit circle
Try f : R → R by “f(x) is the y with x²+y²=1”. At x=2 no real y works (rule 1 fails); at x=0 both y=1 and y=−1 work (rule 2 fails). The vertical line misses the circle, or meets it twice.
Not a function · reading a numerator (Example 7.1.12)
Try f : Q → Z by f(m/n) = m. The same number has many names: 1/2 = 3/6, yet the rule gives f(1/2)=1 but f(3/6)=3. One input, two outputs – not a function. “Well-defined” is really what being a function means.

Practice exercises · Section 7.1

Epp, 4th ed. §7.1 (p. 393): recommended 2, 6, 7, 9, 18, 19, 20, 41, 42, 43. Two are worked here; more in Taught solutions.
Exercise 7.1 A
Let X = {1,2,3}, Y = {a,b,c,d} and f = {(1,c),(2,a),(3,c)}. State the domain, co-domain and range; find the inverse image of c and of b.
Domain {1,2,3}, co-domain {a,b,c,d}. Each input has exactly one image, so f is a function. Range = {a, c} (the outputs actually used). Inverse image of c = {1, 3} (both map to c); inverse image of b = ∅ (nothing maps to b, which is fine – b is just outside the range).
Exercise 7.1 B
Is the rule h : Z → Z, h(n) = n / 2, a function? Explain using the two rules.
No. The single-valued rule is fine, but the total rule fails: for an odd integer such as n = 3, 3/2 is not in the co-domain Z, so 3 has no image. The rule does define a function Z → Q (or on the even integers), but not Z → Z. Domain and co-domain are part of the function.

Section 7.2One-to-one and onto functions, inverses

In 7.1 the constraint was only on the left (domain) side. Now two questions about the right (co-domain) side:

Definition · one-to-one (injective)
F : X → Y is one-to-one if distinct inputs give distinct outputs:
∀ x₁, x₂ ∈ X,   F(x₁) = F(x₂) ⇒ x₁ = x₂.
It is not one-to-one iff ∃ x₁ ≠ x₂ with F(x₁) = F(x₂) (a collision).
TO PROVE one-to-one
Suppose F(x₁)=F(x₂) for arbitrary inputs; work algebraically to x₁=x₂.
TO DISPROVE one-to-one
Exhibit two specific unequal inputs with the same output. One pair is enough.

Example 7.2.2. f : R → R, f(x)=4x−1 is one-to-one (4x₁−1=4x₂−1 ⇒ x₁=x₂). But g : Z → Z, g(n)=n² is not: g(2)=g(−2)=4 yet 2 ≠ −2 – squaring forgets the sign.

Definition · onto (surjective)
F : X → Y is onto if every co-domain element is hit:
∀ y ∈ Y,   ∃ x ∈ X with F(x) = y.   Equivalently range = co-domain.
It is not onto iff some y is missed by every x.

Example 7.2.5. f : R → R, f(x)=4x−1 is onto: given y, take x=(y+1)/4 ∈ R. But h : Z → Z, h(n)=4n−1 is not onto: y=0 needs n=1/4 ∉ Z. Same rule, different domain, opposite verdict – one-to-one and onto are independent properties.

7.2.1 One-to-one / onto / bijection checker

Define a finite function with x:y arrows. The checker reports whether it is one-to-one (and names a colliding pair if not), onto (and names a missed target if not), and therefore a bijection. Based on Examples 7.2.1 and 7.2.4 – try G, which is onto but not one-to-one.

7.2.2 The linear-function lab – f(x) = m·x + c

Set the slope m, intercept c, and the domain/co-domain. The lab reports one-to-one and onto with reasons, and gives the inverse formula when it exists. This is Examples 7.2.2, 7.2.5 and 7.2.13 in one place – compare 4x−1 over R (a bijection) with the same rule over Z (one-to-one but not onto).
Theorem 7.2.2 · inverse functions
If F : X → Y is a bijection (one-to-one and onto), it has an inverse F⁻¹ : Y → X with F⁻¹(y) = x ⇔ y = F(x). Onto makes F⁻¹ defined everywhere; one-to-one makes it single-valued. To find it from a formula, solve y = F(x) for x (e.g. f(x)=4x−1 ⇒ f⁻¹(y)=(y+1)/4); from a diagram, reverse the arrows.

Bijections count. A bijection X ↔ Y proves |X| = |Y|. Example 7.2.8 pairs the four subsets of {a,b} with the four length-2 bit strings (∅↔00, {a}↔10, {b}↔01, {a,b}↔11) – a perfect matching, so a subset and a bit string are “the same data”.

7.2.3 Logarithms (Theorem 7.2.1) & change of base

The exponential exp₃(x)=bᵛ and the logarithm log₃ are both one-to-one and onto, so each is the inverse of the other: log₃ x = y ⇔ bᴆ = x. The calculator uses change of base (Theorem 7.2.1d), log₃ x = (ln x)/(ln b), which is how a calculator with only ln finds any log.
7.2.1 (a) log₃(xy) = log₃ x + log₃ y · product → sum
7.2.1 (b) log₃(x/y) = log₃ x − log₃ y · quotient → difference
7.2.1 (c) log₃(xᵃ) = a·log₃ x · power → coefficient
7.2.1 (d) logᶜ x = (log₃ x)/(log₃ c) · change of base
Laws of exponents · the engine behind the log laws
bᵘ·bᵛ = bᵘ⁺ᵛ  ·  (bᵘ)ᵛ = bᵘᵛ  ·  bᵘ/bᵛ = bᵘ⁻ᵛ  ·  (bc)ᵘ = bᵘcᵘ. Each of the four log laws is just one of these read backwards through the inverse log₃ = (exp₃)⁻¹: logs report exponents, so “multiply the powers” becomes “add the logs”. Why this matters in computing: logarithms turn exponential questions into linear ones – the engine behind measuring information (bits), algorithmic complexity (log₂ n levels of a balanced tree), and scale.
Proof · product rule 7.2.1(a)
log₃(xy) = log₃ x + log₃ y for b ≠ 1, x, y > 0.
Let u = log₃ x and v = log₃ y, so by definition x = bᵘ and y = bᵛ. Then xy = bᵘ·bᵛ = bᵘ⁺ᵛ (exponent law), so reading the definition backward, log₃(xy) = u + v = log₃ x + log₃ y. Check (b=10): log(100·1000)=log 100000 = 5 and log 100 + log 1000 = 2 + 3 = 5. ✓ Laws (b) and (c) follow the same way from the quotient and power laws.
Proof · change of base 7.2.1(d)
logᶜ x = (log₃ x)/(log₃ c) – and why a calculator with only ln can find log₂ 5.
Let u = log₃ c, v = logᶜ x, w = log₃ x, so c = bᵘ, x = cᵛ, x = bᵅ. Then x = cᵛ = (bᵘ)ᵛ = bᵘᵛ, and also x = bᵅ. Since exp₃ is one-to-one, uv = w, i.e. (log₃ c)(logᶜ x) = log₃ x, giving logᶜ x = (log₃ x)/(log₃ c). Use it: log₂ 5 = (ln 5)/(ln 2) ≈ 1.6094/0.6931 ≈ 2.3219. The one-to-oneness of exp is not just a box to tick – it is the proof tool that turns an exponent equality into a log identity.

7.2.4 Log-law verifier – see both sides agree

Pick a law from Theorem 7.2.1, choose a base and values, and the tool computes the left and right sides independently and checks they are equal (to rounding). This is a numeric sanity check, not a proof – the proofs above are the real reason they hold.

Practice exercises · Section 7.2

Epp, 4th ed. §7.2 (p. 413): recommended 1, 8, 12, 13, 17, 18, 23, 25, 27, 33, 35, 43. The examinable core – practise these most.
Exercise 7.2 A
Define f : R → R by f(x) = 3x + 5. Prove it is one-to-one and onto, and find f⁻¹.
One-to-one. Suppose f(x₁)=f(x₂). Then 3x₁+5 = 3x₂+5 ⇒ 3x₁=3x₂ ⇒ x₁=x₂. Onto. Given y ∈ R, set x = (y−5)/3 ∈ R; then f(x) = 3·(y−5)/3 + 5 = y. So f is a bijection. Inverse. Solve y = 3x+5: f⁻¹(y) = (y−5)/3. Check: f⁻¹(f(x)) = (3x+5−5)/3 = x. ✓
Exercise 7.2 B
Is g : R → R, g(x) = x² one-to-one? onto? What if the domain and co-domain are changed to R≥₀ (the non-negative reals)?
Over R → R: not one-to-one (g(2)=g(−2)=4) and not onto (no x gives g(x) = −1, since squares are ≥ 0). Restricting to g : R≥₀ → R≥₀ repairs both: distinct non-negatives have distinct squares (one-to-one), and every y ≥ 0 is (√y)² (onto), so it becomes a bijection with inverse √y. Domain and co-domain decide everything.

Section 7.3Composition of functions · enrichment

Definition · composition
Given f : X → Y and g : Y → Z with range(f) ⊆ domain(g), the composition g ∘ f : X → Z is (g ∘ f)(x) = g(f(x)). Read “g circle f”: f acts first, then g – apply right-to-left. Two machines in series: x enters f, its output feeds straight into g.

Order is part of the operation (Example 7.3.1). For f(n)=n+1 and g(n)=n²: (g∘f)(n)=(n+1)² but (f∘g)(n)=n²+1. At n=1 these give 4 and 2. So composition is not commutative.

7.3.1 Composition tracer (finite)

Give f (as X → Y arrows) and g (as Y → Z arrows). The tracer follows each input all the way across, x → f(x) → g(f(x)), builds g ∘ f, and warns if range(f) ⊈ domain(g) so the composition is undefined. Based on Example 7.3.2.

7.3.2 Order matters – numeric composition

Pick two integer functions and an input. The tool computes both (g ∘ f)(x) and (f ∘ g)(x) so you can see they usually differ.
Theorem 7.3.1 · identity
f ∘ Iₓ = f and Iₖ ∘ f = f. The identity is the “1” of composition.
Theorem 7.3.2 · inverse
If f is a bijection: f⁻¹ ∘ f = Iₓ and f ∘ f⁻¹ = Iₖ. A true two-sided undo.
Theorem 7.3.3
one-to-one ∘ one-to-one is one-to-one.
Theorem 7.3.4
onto ∘ onto is onto. So bijection ∘ bijection is a bijection.

Why 7.3.3 holds. If g(f(x₁))=g(f(x₂)), then g one-to-one gives f(x₁)=f(x₂), then f one-to-one gives x₁=x₂.

Practice exercises · Section 7.3

Epp, 4th ed. §7.3. Enrichment – lighter than 7.1/7.2.
Exercise 7.3 A
For f, g : R → R with f(x)=2x and g(x)=x+3, find g ∘ f and f ∘ g, and confirm they differ.
(g ∘ f)(x) = g(f(x)) = g(2x) = 2x + 3.   (f ∘ g)(x) = f(g(x)) = f(x+3) = 2(x+3) = 2x + 6. They differ for every x (e.g. at x=0: 3 vs 6), confirming composition is not commutative. Both are themselves bijections (composition of bijections), with inverses (y−3)/2 and (y−6)/2 respectively.

Section 9.4The pigeonhole principle · enrichment

The pigeonhole principle
If n pigeons fly into m holes and n > m, then at least one hole holds two or more.
In function language: a function from a finite set to a smaller finite set cannot be one-to-one – two inputs must share an image. This is exactly “not one-to-one” from 7.2, used as a counting tool.

The recipe every time: name the pigeons, name the holes, check pigeons > holes. The conclusion is then automatic; the art is choosing the holes. Examples: 13 people share a birth-month (13 > 12); 3 socks guarantee a matched pair from 2 colours; among 8 integers {1..8}, picking 5 forces a pair summing to 9 (holes {1,8},{2,7},{3,6},{4,5}); every fraction’s decimal terminates or repeats (only b possible remainders).

9.4.1 Pigeonhole calculator

Enter pigeons n and holes m. The tool reports whether a collision is forced, the guaranteed fullest hole ≥ ⌈n/m⌉, the least pigeons needed to force a shared hole, and – using the generalized form with your k – whether some hole must hold ≥ k+1.
Generalized pigeonhole principle
If n pigeons go into m holes and k < n/m for a positive integer k, then some hole holds ≥ k+1. The basic principle is the case k=1. The fullest hole always holds ≥ ⌈n/m⌉.

Example 9.4.5. Among 85 people, must 4 share a last initial? Holes = 26, take k=3: 3 < 85/26 ≈ 3.27, so some initial is shared by ≥ 4. Contrapositive view (Example 9.4.6 style): if at most 3 shared each initial, at most 3×26 = 78 people – but there are 85 > 78, contradiction. “At most k per hole ⇒ at most k·m total” is often the cleanest route.

Contrapositive form · the counting route
“At most k per hole” ⇒ “at most k·m in total”. To prove some hole has ≥ k+1, assume the opposite (every hole has ≤ k), add up the maximum that allows (k·m), and show the real total overshoots it. This is usually the cleanest written proof.

9.4.2 Pigeonhole visualiser – watch the collision become unavoidable

Spread n pigeons into m holes as evenly as possible (the best case for avoiding a crowd). Even then, the fullest hole is forced to hold ≥ ⌈n/m⌉. Increase n past m and a doubled-up hole appears; push further and watch the floor rise.

9.4.3 Why every fraction repeats – the remainder demo (Example 9.4.4)

Long-divide a/b. Each remainder is one of only b values (0 … b−1), so by pigeonhole a remainder must eventually repeat – and from that point the digits cycle forever. The tool shows each step r → digit and marks where the cycle closes.

Practice exercises · Section 9.4

Epp, 4th ed. §9.4: try 1–12 (basic) and 13–20 (generalized). Enrichment, not a primary exam target.
Exercise 9.4 A
A drawer holds 10 black and 10 white socks. Pulling blindly, how many must you take to be sure of a matched pair? Does the count of each colour matter?
3 socks. Pigeons = socks pulled, holes = the 2 colours. Two socks could be one of each colour, but a third has only 2 colours to land in, so 3 > 2 forces two of the same colour. The number of socks per colour is irrelevant – only the number of colours (holes) matters. In general, with m colours you need m+1 socks to force a pair.

WorkedTaught solutions to recommended exercises

A selection from Epp’s recommended problems, solved in the style used in lecture. Attempt each on paper first.
§7.1 · reading a diagram
Let f : {a,b,c} → {1,2,3,4} with f(a)=2, f(b)=4, f(c)=2. Give the range and the inverse image of each element of the co-domain.
Range = {2, 4}. Inverse images: f⁻¹(1) = ∅, f⁻¹(2) = {a, c}, f⁻¹(3) = ∅, f⁻¹(4) = {b}. The inverse images partition the domain: {a,c} ∪ {b} = {a,b,c}, and the empty ones correspond to co-domain elements outside the range.
§7.1 · equality of functions
On J₃ = {0,1,2}, are f(x) = (x²+x+1) mod 3 and g(x) = (x+2)² mod 3 equal?
Yes. Same domain and co-domain; check every input. f(0)=1, f(1)=(3)mod3=0, f(2)=(7)mod3=1. g(0)=4mod3=1, g(1)=9mod3=0, g(2)=16mod3=1. The values agree at 0, 1, 2, so by Theorem 7.1.1, f = g – even though the rules look different. (The widget 7.1.3 computes this table live.)
§7.1 · well-defined?
Is f : Q → Z given by f(m/n) = m + n well defined?
No. A rational has many names. Take 1/2 = 2/4. The rule gives f(1/2) = 1+2 = 3 but f(2/4) = 2+4 = 6. One input, two outputs – the single-valued rule fails, so this is not a function. Any rule that reads the numerator or denominator separately runs into this, because those are properties of the name, not of the number.
§7.2 · one-to-one and onto from a formula
Define f : Z → Z by f(n) = 2n + 1. Is it one-to-one? onto?
One-to-one: if 2n₁+1 = 2n₂+1 then n₁ = n₂. ✓ Not onto: f(n) is always odd, so even targets are missed; e.g. y = 2 needs n = 1/2 ∉ Z. So f is one-to-one but not onto. (Its range is the odd integers; restricting the co-domain to the odd integers would make it a bijection.)
§7.2 · bijection and inverse
Show h : R − {2} → R − {1}, h(x) = x/(x−2), is a bijection and find h⁻¹.
Solve y = x/(x−2) for x: y(x−2) = x ⇒ yx − 2y = x ⇒ x(y−1) = 2y ⇒ x = 2y/(y−1) (valid for y ≠ 1). Every y ≠ 1 gives exactly one x ≠ 2, so h is one-to-one and onto, hence a bijection, with h⁻¹(y) = 2y/(y−1). The excluded points (x=2 and y=1) are exactly the values that would divide by zero.
§7.2 · logarithm laws
Using Theorem 7.2.1, write log₂(8x/y³) in terms of log₂ x and log₂ y.
log₂(8x/y³) = log₂(8x) − log₂(y³) (quotient) = log₂ 8 + log₂ x − 3·log₂ y (product, then power) = 3 + log₂ x − 3 log₂ y, since log₂ 8 = 3.
§9.4 · pigeonhole
Show that among any 5 integers chosen from {1,2,…,8}, two of them sum to 9.
Partition {1,…,8} into the four “sum-to-9” pairs (the holes): {1,8}, {2,7}, {3,6}, {4,5}. Choosing 5 integers (pigeons) into 4 holes forces two chosen numbers into the same pair (since 5 > 4) – and that pair sums to 9. With only 4 chosen it can fail: {1,2,3,4} has no pair summing to 9. The whole trick is choosing the partition so that “two in one hole” means exactly what you want.
§9.4 · generalized / contrapositive
42 students share 12 computers; each uses one and no computer serves more than 6. Show at least 5 computers serve 3 or more students.
Contradiction (contrapositive count). Suppose at most 4 computers serve ≥ 3 students. Then at least 8 computers serve ≤ 2 each. Maximum students served: the 8 light computers carry ≤ 2×8 = 16; the other 4 carry ≤ 6×4 = 24; total ≤ 40. But there are 42 > 40 – contradiction. So at least 5 computers serve 3 or more.
§7.2 · change of base (Examples 7.2.6–7)
A calculator has only ln. Evaluate log₂ 10 to four decimal places.
By change of base (7.2.1d), log₂ 10 = (ln 10)/(ln 2) = 2.302585…/0.693147… ≈ 3.3219. Sanity check: 2³ = 8 < 10 < 16 = 2⁴, so log₂ 10 sits between 3 and 4. ✓ Any base gives the same ratio.
§7.2 · one-to-one / onto from a formula
Is the floor function f : R → Z, f(x) = ⌊x⌋ one-to-one? onto?
Not one-to-one: ⌊1.2⌋ = ⌊1.7⌋ = 1, two inputs share an image. Onto: for any integer n, f(n) = ⌊n⌋ = n, so every target is hit. So f is onto but not one-to-one – the two properties are independent.
§9.4 · basic (remainders)
Show that among any 100 integers, two leave the same remainder on division by 99.
Pigeons = the 100 integers; holes = the 99 possible remainders 0,1,…,98 modulo 99. Since 100 > 99, two integers a, b share a remainder – and then a − b is divisible by 99. (The map “integer → its remainder” from a 100-set to a 99-set cannot be one-to-one.)
§9.4 · generalized
Show that in any group of 30 students, at least 3 share a birth month.
Holes m = 12 months, pigeons n = 30. Take k = 2: since 2 < 30/12 = 2.5, the generalized principle forces some month to hold ≥ k+1 = 3. Contrapositive check: at most 2 per month would allow only 2×12 = 24 < 30 students. The fullest month holds ≥ ⌈30/12⌉ = 3.

Chapter recap – functions, end to end

  • 7.1 – a function f : X → Y gives every input exactly one image (total + single-valued); know image, range, co-domain, inverse image, equality (Thm 7.1.1), and what “well-defined” means.
  • 7.2 – one-to-one (no collisions) and onto (nothing missed) are independent; both together make a bijection, which has an inverse (Thm 7.2.2). Logs are the inverse of exponentials; know the four log laws and change of base (Thm 7.2.1).
  • 7.3 – composition (g∘f)(x)=g(f(x)), f first; not commutative; identity and inverse behave as expected; one-to-one and onto are preserved.
  • 9.4 – the pigeonhole principle is “a function to a smaller set is not one-to-one”, turned into a counting tool; generalized and contrapositive forms count the fullest hole.
Exam focus. 7.1 and 7.2 are the examinable core – reading diagrams, proving/disproving one-to-one and onto, finding inverses, and the logarithm laws. 7.3 and 9.4 are enrichment. What’s next: Chapter 8 (Relations) generalises functions – a function is a relation with the two special rules, and equivalence relations relax them.