Free degree-level computing lessons for careful independent study.
Aplailasain by Static Carnival

Degree Level Programmes · Formal Computing Foundations · Lesson 19

Functions Revisited: Injective, Surjective and Bijective

Classify functions by how they use inputs and outputs.

Back to coursePreviousNext lesson

Lesson overview

Classify functions by how they use inputs and outputs.

CourseFundamentals of Computing
Topic strandFunctions
Assessment styleDigital exam practice
EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

  • Identify injective behaviour.
  • Identify surjective behaviour relative to a codomain.
  • Explain why bijections support reversible encoding.

Learning outcomes

  • By the end of this lesson, you can identify injective behaviour.
  • By the end of this lesson, you can identify surjective behaviour relative to a codomain.
  • By the end of this lesson, you can explain why bijections support reversible encoding.

Key vocabulary

injectivesurjectivebijectivecodomain

What this lesson is about

Injective functions do not collapse distinct inputs to the same output. Surjective functions reach every element of the codomain. Bijective functions do both.

These properties are about information preservation and coverage. They matter for encoding, decoding, indexing and reversible transformations.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

InjectiveFunction property. Different inputs cannot produce the same output. This protects distinguishability.
SurjectiveFunction property. Every element of the codomain is reached by at least one input.
BijectiveFunction property. Both injective and surjective. This supports reversible one-to-one correspondence.
EncodingPhrase. A mapping from original values into code values. Reversible encoding needs enough structure to decode unambiguously.

Formal notation and definitions

Injective: f(x₁) = f(x₂) ⇒ x₁ = x₂.Surjective: ∀y ∈ B, ∃x ∈ A such that f(x) = y.Bijective: injective and surjective.

How to read the symbols

f(x1)=f(x2)⇒x1=x2f(x_1)=f(x_2)\Rightarrow x_1=x_2Injective: equal outputs can only come from equal inputs.
∀y∈B,∃x∈A\forall y\in B,\exists x\in ASurjective: every codomain value is reached by some input.
bijectiveBoth injective and surjective; suitable for reversible one-to-one correspondence.

Use the domain and codomain when judging injective, surjective and bijective behaviour. The same formula can change property when the codomain changes.

Degree-level reasoning

A function is a rule with a contract: each domain element has exactly one output. Many computing bugs come from leaving the domain or codomain vague.

Properties such as injective and surjective only make sense relative to the specified domain and codomain.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

A bijective encoding gives each input exactly one code and each code exactly one input, making decoding unambiguous.

Objects: domain A, codomain B, inputs x1 and x2, outputs f(x), and the reached elements of B.

Model cue: Use mapping arrows from domain A to codomain B. Injective means no two domain elements land on the same codomain element; surjective means every codomain element is hit.

2. Mathematical working

Injective: f(x1)=f(x2)⇒x1=x2\text{Injective: } f(x_1)=f(x_2)\Rightarrow x_1=x_2Surjective: ∀y∈B, ∃x∈A such that f(x)=y\text{Surjective: } \forall y\in B,\ \exists x\in A\ \text{such that}\ f(x)=y
Plain text version
Injective: f(x₁) = f(x₂) ⇒ x₁ = x₂.
Surjective: ∀y ∈ B, ∃x ∈ A such that f(x) = y.
Bijective: injective and surjective.

Worked use: A reversible encoding must be injective so that two inputs do not produce the same code. It must also be surjective onto the chosen code space if every code is supposed to decode to a valid input.

3. How to read the working

  1. Read injectivity from left to right: if two inputs have the same output, they must have been the same input.
  2. Read surjectivity relative to the codomain B: every y in B must be hit by at least one input x in A.
  3. Keep domain A and codomain B visible, because changing either can change whether the function is surjective or bijective.
  4. Translate the result into information flow: injective protects distinguishability, surjective guarantees coverage of declared outputs.

4. Computing meaning and check

These properties describe information loss and coverage. A reversible encoding needs distinct inputs to stay distinct and every valid code to be accounted for.

Now check: Give a function that is injective but not surjective by specifying its domain and codomain.

Worked example

From scenario to formal reasoning

Scenario: A bijective encoding gives each input exactly one code and each code exactly one input, making decoding unambiguous.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

A reversible encoding must be injective so that two inputs do not produce the same code. It must also be surjective onto the chosen code space if every code is supposed to decode to a valid input.

Worked solution structure

How a strong answer should be written

  1. Define: State the domain and the objects under discussion. For this lesson, begin from Injective: f(x₁) = f(x₂) ⇒ x₁ = x₂.
  2. Apply: Use the relevant definition from functions; do not rely on the diagram, wording or intuition alone.
  3. Check: Test a boundary case, counterexample candidate or representation limit.
  4. Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is judging surjectivity without stating the codomain. Surjective means every codomain value is reached.

Guided practice

  1. Give a function that is injective but not surjective by specifying both domain and codomain.
  2. Change only the codomain and explain how surjectivity can change.
  3. Give an encoding example where two inputs share one output and explain why decoding becomes ambiguous.
  4. State why a bijection supports reversible encoding.

Quick checks

1. What does injective mean?

2. Surjectivity must be judged relative to:

Digital exam practice

Example exam task

Let f: {1,2} → {a,b,c} with f(1)=a and f(2)=b. Decide whether f is injective and surjective, then explain how changing the codomain to {a,b} changes the surjectivity judgement.

Notation toolkit

f(x1)=f(x2)⇒x1=x2f(x_1)=f(x_2)\Rightarrow x_1=x_2

Means: injectivity: shared output means same input

How to use: Use it to prove no two inputs collide.

∀y∈B ∃x∈A\forall y\in B\ \exists x\in A

Means: surjectivity: every codomain value is reached

How to use: Use it after stating the codomain.

A↔BA\leftrightarrow B

Means: a reversible one-to-one correspondence

How to use: Use it when explaining bijective encoding or decoding.

What a good answer is expected to show

A strong answer for this lesson defines domain A, codomain B, inputs x1 and x2, outputs f(x), and the reached elements of B, applies the functions method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

  1. Read injectivity from left to right: if two inputs have the same output, they must have been the same input.
  2. Read surjectivity relative to the codomain B: every y in B must be hit by at least one input x in A.
  3. Keep domain A and codomain B visible, because changing either can change whether the function is surjective or bijective.
  4. Translate the result into information flow: injective protects distinguishability, surjective guarantees coverage of declared outputs.

Model answer

Reveal model answer
f:{1,2}→{a,b,c},f(1)=a,f(2)=bf:\{1,2\}\to\{a,b,c\},\quad f(1)=a,\quad f(2)=binjective: f(x1)=f(x2)⇒x1=x2\text{injective: }f(x_1)=f(x_2)\Rightarrow x_1=x_2surjective: ∀y∈B,∃x∈A such that f(x)=y\text{surjective: }\forall y\in B,\exists x\in A\text{ such that }f(x)=y

Define f: {1,2} → {a,b,c} by f(1)=a and f(2)=b. It is injective because different inputs have different outputs, but it is not surjective because c is not reached. If the codomain is changed to {a,b}, the same rule becomes surjective. A bijection supports reversible encoding because every output has exactly one input.

Practise next

  1. Give a function that is injective but not surjective by specifying both domain and codomain.
  2. Change only the codomain and explain how surjectivity can change.

Self-marking criteria

  • Defines the function with explicit domain and codomain.
  • Justifies injectivity using equal-output reasoning.
  • Identifies a codomain value not reached.
  • Explains codomain dependence.
  • Connects bijection to reversible encoding.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Proof Techniques: Direct Proof and Counterexample.