Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Functions: injective, surjective and bijective

Clear definitions and proofs for functions, focusing on injective (one-to-one), surjective (onto) and bijective maps, with examples, common mistakes and exam guidance.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Small, precise maps between sets control how data and signals move in engineering systems. Knowing when a function is injective, surjective or bijective tells you if information is preserved, if every required output can occur, and whether an inverse (undo) exists — important for hashing, encoding/decoding, reversible computations and many algorithms.

Key ideas

Start with basic terms. Define each before using it.

  • Set: a collection of distinct objects. (Standard set theory assumed.)
  • Domain: for a function f, the set of inputs. Denote by A.
  • Codomain: for a function f, the set of possible outputs specified with the function. Denote by B.
  • Function: A function f from A to B (written f: A → B) is a relation with the property that every element x ∈ A is related to exactly one element y ∈ B. We write y = f(x). (Assumption: A and B are sets.)
  • Image (or value): For x ∈ A, the element f(x) ∈ B is the image of x.
  • Range (or image set): The set {f(x) | x ∈ A} ⊆ B. Range depends on f and A.

Precise definitions of the three types:

  • Injective (one-to-one): A function f: A → B is injective if for every x1,x2 ∈ A, f(x1) = f(x2) implies x1 = x2. Equivalently: distinct inputs give distinct outputs.

  • Surjective (onto): A function f: A → B is surjective if for every y ∈ B there exists x ∈ A such that f(x) = y. Equivalently: the range equals the codomain: {f(x) | x ∈ A} = B.

  • Bijective: A function f: A → B is bijective if it is both injective and surjective. Equivalently: f is a one-to-one correspondence between A and B.

Important theorems and facts (state, assumptions, and standard proofs):

  1. Existence of inverse
  • Theorem: A function f: A → B has a function g: B → A such that g(f(x)) = x for all x ∈ A and f(g(y)) = y for all y ∈ B if and only if f is bijective.
  • Proof sketch: (->) If such g exists, f must be injective because f(x1)=f(x2) implies g(f(x1))=g(f(x2)) so x1 = x2; f must be surjective because for any y ∈ B take x = g(y) then f(x) = f(g(y)) = y. (<-) If f is bijective, define g by letting g(y) be the unique x with f(x)=y; this g is well-defined and satisfies both equalities. Uniqueness of inverse follows by functional composition arguments. Moreover, existence of a left-inverse (g ∘ f = id_A) implies f is injective, and existence of a right-inverse (f ∘ h = id_B) implies f is surjective (id_A and id_B are identity functions).
  1. Composition properties
  • If f: A → B and g: B → C are injective then g ∘ f is injective.
  • If f and g are surjective then g ∘ f is surjective.
  • If f and g are bijective then g ∘ f is bijective and (g ∘ f)^{-1} = f^{-1} ∘ g^{-1}.
  • Proofs are direct from definitions; for example, injective composition: (g ∘ f)(x1) = (g ∘ f)(x2) ⇒ g(f(x1)) = g(f(x2)) ⇒ since g injective f(x1) = f(x2) ⇒ x1 = x2.
  1. Finite sets and counting
  • For finite sets A and B with |A| = n and |B| = n, f: A → B is bijective iff it is injective iff it is surjective. More generally, for finite sets, an injection A → B implies |A| ≤ |B| and a surjection A → B implies |A| ≥ |B| (Pigeonhole Principle). There are n! distinct bijections from A to B.
  • Reason: by the multiplication principle: choose images for elements of A in n, n-1, ..., 1 ways, giving n!.

Diagrams to draw in answers

  • To show injective vs non-injective: draw two horizontal ovals labeled A (left) and B (right). Put elements as points in each oval. Draw arrows from elements of A to their images in B. For injective example show arrows from distinct A points to distinct B points. For non-injective, show two A points arrowing to the same B point and label them x1,x2 with f(x1)=f(x2).
  • To show surjective vs non-surjective: draw as above; for surjective ensure every element in B has at least one incoming arrow; for non-surjective show some b ∈ B with no arrow.

Formulas

f: A → B — f is a function from set A (domain) to set B (codomain). No SI unit. Applies generally to sets. Range(f) = { f(x) | x ∈ A } — range (image) of f; subset of B. f is injective ⇔ (∀ x1,x2 ∈ A) [ f(x1) = f(x2) ⇒ x1 = x2 ] — definition of injective. f is surjective ⇔ (∀ y ∈ B)(∃ x ∈ A) [ f(x) = y ] — definition of surjective. f is bijective ⇔ f is injective ∧ f is surjective — definition of bijective. (g ∘ f)(x) = g(f(x)) — composition of f:A→B and g:B→C. If f is bijective then f^{-1}: B → A — inverse function exists and is unique. Number of bijections from an n-element set to itself = n! — n factorial (assumes finite n).

Worked examples

Example 1 — Injective but not surjective (integer linear map) Question: Let f: Z → Z be f(x) = 2x, where Z is integers. Show f is injective and not surjective. Answer (step-by-step):

  1. Injective: Suppose f(x1) = f(x2). Then 2x1 = 2x2. Divide both sides by 2 to get x1 = x2. Hence by definition f is injective.
  2. Not surjective: To be surjective every integer y must be 2x for some integer x. Take y = 1. There is no integer x with 2x = 1. So 1 ∉ Range(f). Hence f is not surjective. Final: f is injective but not surjective. (Units: none.)

Example 1b — Surjective but not injective (integer division by 2) Question: Let f: Z → Z be f(x) = ⌊x/2⌋. Show f is surjective and not injective. Answer: Surjective: for any y ∈ Z, take x = 2y (or x = 2y+1); then f(x) = y. Not injective: f(0) = 0 = f(1) but 0 ≠ 1. Final: f is surjective but not injective.

Example 2 — Make x^2 bijective by restricting domain Question: f: R → R defined by f(x) = x^2. Is f injective/surjective? Can you restrict domain to make it bijective onto [0,∞)? Answer:

  1. Not injective on R because f(1) = 1 = f(-1) but 1 ≠ -1.
  2. Not surjective onto R because negative numbers are not squares; e.g. -1 ∉ Range(f).
  3. Restrict domain to A = [0,∞) and codomain to B = [0,∞). Define g: [0,∞) → [0,∞) by g(x) = x^2. Then g is injective: if x1^2 = x2^2 with x1,x2 ≥ 0 then x1 = x2. g is surjective: for any y ≥ 0 take x = √y (nonnegative) then g(x) = y. Hence g is bijective and inverse is g^{-1}(y) = √y.

Example 3 — Counting bijections (finite) Question: How many bijections exist from set A = {1,2,3,4} to itself? Answer: Number of bijections = 4! = 24. Reason: choose image of 1 in 4 ways, of 2 in 3 remaining ways, 3 in 2 ways, 4 in 1 way ⇒ 4·3·2·1 = 24. Bold answer: 24.

Common mistakes

  • Assuming inverse exists just because f is one-to-one on its domain but forgetting surjectivity to the declared codomain.
  • In proofs, using examples instead of general argument (example shows possibility, not proof).
  • For compositions: assuming (g ∘ f) injective implies g injective or f injective without justification. Correct facts: if g ∘ f is injective then f must be injective. If g ∘ f is surjective then g must be surjective.

For your exam

Kinds of questions you will see:

  • Definitions and short notes (define injective/surjective/bijective and give examples/counterexamples).
  • Proofs: show a given f is injective/surjective, or prove the theorem "f invertible iff bijective".
  • Derivations: prove composition properties (injective/surjective), show inverse composition rule.
  • Numericals/counting: count bijections between finite sets (n!).
  • Diagram questions: draw mapping diagrams to illustrate injective/surjective cases.

What a full-marks answer includes:

  • Precise definitions (use the quantifier forms). Define domain and codomain.
  • Clear assumptions (specify sets and any restrictions like domain = R or domain = [0,∞)).
  • Formal proofs using the definitions (for existence proofs, give explicit construction of inverse when bijection is claimed).
  • Correct diagrams where asked; label sets and elements and arrows.
  • For counting, show multiplication principle steps.

Quick check

  1. Let f: {1,2,3} → {a,b,c} with f(1)=a, f(2)=b, f(3)=a. Is f injective? Surjective?
  2. If f: A → B is bijective, what is f^{-1}(f(x)) equal to for x ∈ A?
  3. How many bijections exist from a 5-element set to itself? Answers: 1. Not injective (1 and 3 map to a); not surjective if some element of codomain missing (here c has no preimage) — so not surjective. 2. f^{-1}(f(x)) = x. 3. 5! = 120.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?