Classifying Functions: Injective, Surjective, and Bijective

Welcome to the next lesson in our journey through the mathematical foundations of computer science. In our previous sessions, we explored the concepts of sets, relations, and equivalence classes. We saw that an equivalence relation partitions a set into distinct groups of "equivalent" elements. This was our first step in formally classifying relationships.

Today, we will narrow our focus to a particularly important and structured type of relation: the function. You likely have an intuitive idea of what a function is from programming, but we will formalize this and learn to classify functions based on three crucial properties: injectivity, surjectivity, and bijectivity. Understanding these properties is essential, as they describe the nature of mappings that are at the heart of algorithms, data structures, and the very cryptographic systems you're interested in.

From Relations to Functions

First, let's briefly place functions in the context of what we've already learned. A function is a specific kind of binary relation. While a general relation between a set $A$ (the domain) and a set $B$ (the codomain) can have an element in $A$ related to multiple elements in $B$ , or none at all, a function is much more constrained.

A function $f : A \to B$ is a rule that assigns to each element $x \in A$ exactly one element $y \in B$ .

Think of a Python dictionary: every key must be present in the dictionary definition (it's total on its domain of keys) and each key can only map to a single value (it's univalent).

Now, let's explore the properties that make functions so powerful.

Injective Functions (One-to-One)

The first key property is injectivity. An injective function ensures that different inputs always lead to different outputs. There are no "collisions."

Discrete Math - 2.3.2 One-to-One and Onto Functions

To build your intuition, please watch this first segment from a video by Kimberly Brehm. It uses clear mapping diagrams to illustrate the concept of a one-to-one function.

Watch the segment from the beginning until the explanation of one-to-one. Focus on how a function fails to be one-to-one if two arrows from the domain point to the same element in the codomain.

Formally, a function $f : A \to B$ is injective (or one-to-one) if for all elements $x_{1}, x_{2}$ in the domain $A$ , if $x_{1} \neq = x_{2}$ , then $f (x_{1}) \neq = f (x_{2})$ .

When we need to prove that a function is injective, it's often easier to use the contrapositive of this statement:
A function $f$ is injective if for all $x_{1}, x_{2} \in A$ , if $f (x_{1}) = f (x_{2})$ , then $x_{1} = x_{2}$ .

This gives us a direct algebraic strategy: set the function's formula for two different inputs equal to each other and prove that the inputs must have been the same.

INJECTIVE, SURJECTIVE, and BIJECTIVE FUNCTIONS - DISCRETE MATHEMATICS

This video from TrevTutor provides excellent examples of how to apply this proof strategy.

Watch the section on injective functions from the beginning. Pay close attention to the two proofs: one for the linear function f(x) = 3x - 2 (which is injective) and one for f(x) = x^2 (which is not).

The fact that $f (x) = x^{2}$ is not injective is a classic example. Since $f (2) = 4$ and $f (- 2) = 4$ , we have two different inputs mapping to the same output. In the context of cybersecurity, functions that are deliberately not injective are fundamental. A cryptographic hash function, for instance, maps an arbitrarily large input to a fixed-size output. Since there are more possible inputs than outputs, collisions (different inputs producing the same hash) are a mathematical certainty, though good hash functions make them computationally infeasible to find.

Surjective Functions (Onto)

The second property, surjectivity, deals with the codomain. A function is surjective if it "covers" its entire codomain, meaning every possible element in the codomain is a valid output for some input.

Discrete Math - 2.3.2 One-to-One and Onto Functions

Let's return to Kimberly Brehm's video for a visual explanation of surjective, or "onto," functions.

Watch the segment from this timestamp. Notice how a function fails to be onto if there are elements left over in the codomain that are not mapped to.

Formally, a function $f : A \to B$ is surjective (or onto) if for every element $y \in B$ , there exists at least one element $x \in A$ such that $f (x) = y$ . This is equivalent to saying the function's range (the set of actual outputs) is equal to its codomain (the set of all possible outputs).

This definition reveals a subtle but critical point: a function's surjectivity depends entirely on how we define its domain and codomain. The same formula can produce a function that is surjective or not, depending on the sets we are mapping between.

6.3: Injections, Surjections, and Bijections

The following text, from a chapter on functions in Mathematics LibreTexts, illustrates this point perfectly using the formula f(x) = x^2 + 1.

Please read the section "The Importance of the Domain and Codomain." This includes three examples that show how changing the domain from \mathbb{R} to \mathbb{Z}^* or the codomain from \mathbb{R} to T = \{y \in \mathbb{R} \mid y \ge 1\} changes whether the function is injective or surjective.

This is a crucial lesson. When analyzing a function, you cannot just look at the formula; you must also consider the specified domain and codomain.

Bijective Functions (One-to-One Correspondence)

When a function is both injective and surjective, we call it bijective. This is a special case that represents a perfect, reversible mapping between two sets.

3.1. Functions — Discrete Structures for Computing

A bijective function is a "one-to-one correspondence". It is both injective (each input goes to a unique output) and surjective (all outputs in the codomain are used). This means the domain and codomain must have the same number of elements.

A function $f : A \to B$ is bijective if:

It is injective (one-to-one).
It is surjective (onto).

Because a bijection pairs up every element from the domain with a unique element in the codomain with no leftovers, it implies that the two sets, $A$ and $B$ , must have the same size (or cardinality).

Most importantly for computer science, a function is invertible if and only if it is bijective. If you have a perfect one-to-one correspondence, you can define an inverse function $f^{- 1} : B \to A$ that "undoes" the original mapping. This is the absolute foundation of most classical and modern ciphers. An encryption function must be a bijection on the space of possible messages to guarantee that a unique decryption operation exists for every possible ciphertext.

3.1. Functions — Discrete Structures for Computing

This resource from a Discrete Structures course explains the connection between bijections and inverse functions.

Read the section on "Inverse functions." Focus on the explanation of why a function must be both injective and surjective to have a well-defined inverse.

Let's Practice

Time to apply these definitions. For each function below, determine if it is injective, surjective, or bijective.

Problem 1: Let the domain and codomain be $Z_{5} = {0, 1, 2, 3, 4}$ . Consider the function $f : Z_{5} \to Z_{5}$ defined by $f (x) = (3 x + 1) (mod 5)$ .

Hint: Since the domain is small, you can test every input and see what outputs you get.

Problem 2: Consider the function $g : Z \to Z$ (from integers to integers) defined by $g (x) = x - 7$ .

Problem 3: Consider the function $h : N \to N$ (from natural numbers ${1, 2, 3, ...}$ to natural numbers) defined by $h (x) = x + 2$ .

Check your answers

Problem 1: $f (x) = (3 x + 1) (mod 5)$ on $Z_{5}$
Let's compute the output for each input:

$f (0) = (3 \cdot 0 + 1) (mod 5) = 1$
$f (1) = (3 \cdot 1 + 1) (mod 5) = 4$
$f (2) = (3 \cdot 2 + 1) (mod 5) = 7 (mod 5) = 2$
$f (3) = (3 \cdot 3 + 1) (mod 5) = 10 (mod 5) = 0$
$f (4) = (3 \cdot 4 + 1) (mod 5) = 13 (mod 5) = 3$
Injective? Yes. Every input maps to a unique output.
Surjective? Yes. The set of outputs is ${0, 1, 2, 3, 4}$ , which is the entire codomain $Z_{5}$ .
Conclusion: Since it is both injective and surjective, the function is bijective. This kind of linear function is the basis for the Affine cipher.

Problem 2: $g (x) = x - 7$ on $Z$

Injective? Yes. Assume $g (x_{1}) = g (x_{2})$ . Then $x_{1} - 7 = x_{2} - 7$ , which implies $x_{1} = x_{2}$ . So it is injective.
Surjective? Yes. Let $y$ be any integer in the codomain. Can we find an integer $x$ such that $g (x) = y$ ? We need to solve $x - 7 = y$ . This gives $x = y + 7$ . If $y$ is an integer, then $y + 7$ is also an integer. So for any target output $y$ , we can find an input $x = y + 7$ that produces it.
Conclusion: The function is bijective.

Problem 3: $h (x) = x + 2$ on $N$

Injective? Yes. Assume $h (x_{1}) = h (x_{2})$ . Then $x_{1} + 2 = x_{2} + 2$ , which implies $x_{1} = x_{2}$ . It is injective.
Surjective? No. The codomain is all natural numbers ${1, 2, 3, ...}$ . Can we produce the output $y = 1$ ? We would need $x + 2 = 1$ , which means $x = - 1$ . But $- 1$ is not in the domain $N$ . Similarly, we can't produce $y = 2$ , as that would require $x = 0$ , which is also not in $N$ . Since there are elements in the codomain that are never produced as outputs, the function is not surjective.
Conclusion: The function is injective only.

Conclusion

In this lesson, we have formalized our understanding of functions and learned how to classify them based on their structural properties. This is a significant step up from just using functions as computational recipes.

Key Takeaways:

An injective (one-to-one) function never maps two distinct inputs to the same output.
A surjective (onto) function hits every element in its codomain; its range and codomain are equal.
A bijective function is both injective and surjective, forming a perfect one-to-one correspondence.
Bijectivity is the property that makes a function invertible, a concept that is indispensable in cryptography and many other areas of computer science.
Whether a function has these properties depends critically on its specified domain and codomain, not just its formula.

We are now at the end of our first module on the fundamental language of mathematics. You've been introduced to logic, sets, relations, and now a detailed look at functions. In our next and final lesson for this module, we will switch gears slightly to some practical Python skills, ensuring you can accurately compute expressions involving integers, fractions, powers, and logarithms. After that, we will be ready to tackle our next major topic: the art of mathematical proof.