SEM 6 › Discrete Mathematics › Week 03
Discrete Mathematics · Week 03

Functions

Definition of a function, domain, codomain and range, finding domains, one-to-one (injective), onto (surjective) and bijective functions, inverses, and composition.

ITE38221 video · 52 min📄 Lesson 3.pdf

1What is a function?

Many questions ask how one quantity depends on another: a company's profit vs production level, bacteria population vs time, vocabulary learned vs learning time. Functions describe these relationships.

Definition

A function f from A to B is a rule that assigns to each element of A one and only one element of B. We write f : A → B. Functions are also called mappings or transformations.

Term Meaning
Domain The set A: the inputs
Codomain The set B: where the outputs are allowed to land
Image If f(a) = b, then b is the image of a (and a is a preimage of b)
Range The set of all images, f(A) ⊆ B. The range can be smaller than the codomain
"f maps A to B" Another way of saying f : A → B
Two conditions for a function
  1. Every element of A has an image (nothing in A is left out).
  2. Each element of A has exactly one image (no element goes to two places).

Many elements of A may share the same image, and some elements of B may have no preimage. That's still a function.

Example 3.1 — f : ℤ → ℤ, f(x) = x²
  • Domain: all integers
  • Codomain: all integers
  • Range: the perfect squares {0, 1, 4, 9, …}

The range is not the whole codomain.

Finding the domain of a real function

Exclude anything that makes the formula undefined:

  • Square root of a negative number is not allowed: need inside ≥ 0.
  • Division by zero is not allowed: need denominator ≠ 0.
Find the domain

(a) f(x) = √(x − 1)

Need x − 1 ≥ 0, so x ≥ 1. Domain = [1, ∞).

(b) f(x) = 1 / (x² − 4)

Need x² − 4 ≠ 0, so x ≠ ±2. Domain = (−∞, −2) ∪ (−2, 2) ∪ (2, ∞).

2One-to-one (injective)

Definition

f is one-to-one (injective) if and only if f(a) = f(b) implies a = b for all a, b in the domain.

  • Lemma 3.2.1: equivalently, a ≠ b ⇒ f(a) ≠ f(b). Different inputs always give different outputs.
  • With quantifiers: ∀a ∀b (f(a) = f(b) → a = b)
Proving / disproving one-to-one

f(x) = 3x − 5 is one-to-one.

Let f(x₁) = f(x₂). Then 3x₁ − 5 = 3x₂ − 5, so 3x₁ = 3x₂, so x₁ = x₂. ∎

f(x) = x² is not one-to-one.

f(1) = f(−1) = 1, but 1 ≠ −1. One counterexample is enough.

3Onto (surjective) & bijection

Onto

f : A → B is onto (surjective) if for every b ∈ B there is an a ∈ A with f(a) = b. In other words, range = codomain: nothing in B is missed.

Example 3.2

f : ℝ → ℝ, f(x) = 3x − 5 is onto.

Given any y, solve 3x − 5 = y to get x = (y + 5)/3, which is a real number. So every y is hit. ✓

f : ℝ → ℝ, f(x) = x² is not onto.

ℝ contains negative numbers, and no real x has x² = −1. ✗

Bijection (one-to-one correspondence)

f is a bijection if it is both one-to-one and onto.

Example: the identity function ι_A : A → A, ι_A(x) = x, sends each element to itself. It is one-to-one and onto, so it's a bijection.

Type (Figure 3.3) One-to-one? Onto?
(a) ✓ ✗
(b) ✗ ✓
(c) ✓ ✓ (bijection)
(d) ✗ ✗
(e) one element sent to two elements Not a function —
🧪 Try it — Function mapping lab (finite sets)

Choose where each element of A goes. The diagram and classification update instantly. Change the sizes to see why a bijection needs |A| = |B|.

4Inverse functions

Definition

Let f be a bijection from A to B. The inverse function f⁻¹ assigns to each b ∈ B the unique a ∈ A with f(a) = b:

f⁻¹(b) = a ⇔ f(a) = b

  • Only bijections have inverses. If f isn't one-to-one, some b would need two outputs. If f isn't onto, some b would have none.
  • ⚠️ Don't confuse f⁻¹ with 1/f. f⁻¹ "undoes" f; 1/f is the reciprocal.
Example — f : ℝ → ℝ, f(x) = 3x − 5

f is a bijection (shown above), so it is invertible.

Let y = 3x − 5 and solve for x: x = (y + 5)/3.

So f⁻¹(y) = (y + 5)/3.

Check: f(f⁻¹(y)) = 3·(y + 5)/3 − 5 = y ✓

Note on the PDF

The lesson PDF works this example as "y = x + 1, so f⁻¹ = y − 1". That's the textbook example for f(x) = x + 1, pasted under the wrong function. For f(x) = x + 1 the inverse is indeed f⁻¹(y) = y − 1. For f(x) = 3x − 5 it is (y + 5)/3.

Recipe for an inverse: 1. Write y = f(x). 2. Solve for x in terms of y. 3. Swap the names if needed: f⁻¹(y) = …

5Composition of functions

Definition

Let g : A → B and f : B → C. The composition f ∘ g is defined by (f ∘ g)(a) = f(g(a)).

Apply g first, then f. f ∘ g is only defined when the range of g is a subset of the domain of f.

   A ──g──▶ B ──f──▶ C
   a  ↦  g(a)  ↦  f(g(a))      (f∘g)(a) = f(g(a))
Example — f(x) = x² − 1, g(x) = √x + 1

(a) g ∘ f. Put f(x) into g:

(g ∘ f)(x) = g(f(x)) = √(f(x)) + 1 = √(x² − 1) + 1

(b) f ∘ g. Put g(x) into f:

(f ∘ g)(x) = f(g(x)) = (g(x))² − 1 = (√x + 1)² − 1 = x + 2√x + 1 − 1 = x + 2√x

Order matters

In general f ∘ g ≠ g ∘ f, as the example shows.

For a bijection f : A → B:
(f⁻¹ ∘ f)(a) = f⁻¹(f(a)) = f⁻¹(b) = a and (f ∘ f⁻¹)(b) = f(f⁻¹(b)) = f(a) = b

So composing a function with its inverse gives the identity.

🧪 Try it — Composition calculator
Exam focus

Expect:

  • Domain / codomain / range for given functions
  • Finding domains (√ and division)
  • Proving one-to-one (assume f(x₁) = f(x₂), show x₁ = x₂) or disproving with a counterexample
  • Proving onto (solve y = f(x) for x and check x is in the domain)
  • Finding inverses
  • Computing f ∘ g and g ∘ f

6Quick revision sheet

Concept Remember it as
Function Each element of A → exactly one element of B; f : A → B
Domain / codomain / range Inputs / allowed outputs / actual outputs
x² on ℤ Range =
Domain rules √(…) ≥ 0; denominator ≠ 0
One-to-one f(a) = f(b) ⇒ a = b; x² fails (1, −1)
Onto Every b has a preimage; range = codomain
Bijection One-to-one + onto; identity ι_A
Inverse Only for bijections; f(x) = 3x − 5 ⇒ f⁻¹(y) = (y + 5)/3
f⁻¹ ≠ 1/f Undo vs reciprocal
Composition (f∘g)(a) = f(g(a)): g first; f∘g ≠ g∘f
f⁻¹∘f Identity

?Self-check quiz

11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousSets & Set OperationsNext →Sequences & Summations