Function Properties: Injections, Surjections, Bijections, and Inverses

Welcome to the next lesson in our journey through Discrete Mathematics. Last time, we explored the world of relations, classifying them based on properties like reflexivity, symmetry, and transitivity. We saw how these properties give rise to important structures like partial orders and lattices. Today, we will focus on a special, ubiquitous type of relation: the function.

While you've certainly worked with functions extensively in programming and mathematics, this lesson will formalize their properties from a discrete mathematics perspective, which is essential for your GATE preparation. Our goal is to master the ability to determine if a function is injective (one-to-one), surjective (onto), or bijective. We will then build on this to understand and compute function composition and inverse functions. These concepts are not just abstract; they form the theoretical bedrock for topics like algorithm analysis, cryptography, and database theory.

1. Functions as Special Relations

Let's begin by connecting to our previous lesson. A relation from a set $A$ to a set $B$ is any subset of the Cartesian product $A \times B$ . A function $f$ from a domain $A$ to a codomain $B$ , written $f : A \to B$ , is a relation that obeys one extra rule: every element in the domain $A$ must be mapped to exactly one element in the codomain $B$ .

Two key terms to always keep in mind are:

Codomain: The set $B$ of all possible output values.
Range: The subset of the codomain $B$ containing all the actual output values produced by the function.

The distinction between the codomain and the range is central to understanding the types of functions we'll discuss next.

2. Injective, Surjective, and Bijective Functions

The properties of a function are defined by how it maps elements from the domain to the codomain. Let's explore the three fundamental classifications: injective, surjective, and bijective. We will use a video from TrevTutor that provides clear definitions, proofs, and graphical intuition for each.

INJECTIVE, SURJECTIVE, and BIJECTIVE FUNCTIONS - DISCRETE MATHEMATICS

This video provides a comprehensive introduction to injective, surjective, and bijective functions. Pay close attention to the proof techniques and the importance of the domain and codomain in determining these properties.

Please watch the video in three parts: Injective (One-to-One) Functions: Watch from the beginning until this point. A function is injective if every distinct input maps to a distinct output. Formally, f(x_1) = f(x_2) \implies x_1 = x_2. Notice the proof strategy for f(x) = 3x - 2 and the counterexample for f(x) = x^2. Surjective (Onto) Functions: Continue watching from this segment. A function is surjective if its range is equal to its codomain, meaning every element in the codomain is a possible output. The video's discussion on how changing the domain/codomain from real numbers to integers affects surjectivity is a critical point for GATE. Bijective Functions: Finally, watch this short section. A function is bijective if it is both injective and surjective. This creates a perfect pairing between the elements of the domain and codomain.

Let's consolidate these definitions:

Injective (One-to-One): No two inputs map to the same output. Think of it as "no collisions". For a function $f : A \to B$ to be injective, if $A$ and $B$ are finite sets, we must have $∣ A ∣ \leq ∣ B ∣$ . A common visual check is the Horizontal Line Test: if any horizontal line intersects the function's graph more than once, it is not injective.
Surjective (Onto): Every possible output is actually produced. The range equals the codomain. For a function $f : A \to B$ to be surjective, if $A$ and $B$ are finite sets, we must have $∣ A ∣ \geq ∣ B ∣$ .
Bijective (One-to-One and Onto): A perfect correspondence. Every input has a unique output, and every output is mapped to by exactly one input. For finite sets, a bijection can only exist if $∣ A ∣ = ∣ B ∣$ . This is a very useful first check in multiple-choice questions.

GATE-Style Example

Consider the function $f : Z \to Z$ where $f (x) = x^{2}$ . (Here, $Z$ is the set of all integers).

Is it injective? No. For example, $f (2) = 4$ and $f (- 2) = 4$ , but $2 \neq = - 2$ . We have a "collision".
Is it surjective? No. The codomain is all integers ( $Z$ ), but the range is only non-negative perfect squares ${0, 1, 4, 9, ...}$ . There is no integer $x$ such that $f (x) = x^{2} = 3$ , for instance. So the range is not equal to the codomain.

Since it is neither injective nor surjective, it is not bijective.

3. Inverse and Composite Functions

Now that we can classify functions, we can explore operations on them. The two most important are finding a function's inverse and composing functions together.

Inverse Functions

A function has an inverse if and only if it is bijective. An inverse function, denoted $f^{- 1}$ , essentially "undoes" the original function. If $f$ maps $x$ to $y$ , then $f^{- 1}$ maps $y$ back to $x$ .

To formalize this and see how to find an inverse, let's watch the following resource.

Discrete Math - 2.3.3 Inverse Functions and Composition of Functions

This video by Kimberly Brehm clearly explains the condition for a function to be invertible (it must be a bijection) and provides a step-by-step method for finding the inverse.

Focus on these two parts: Definition and Condition: Watch the introductory segment here. It clearly states that a function must be a bijection (both one-to-one and onto) to have an inverse. Finding the Inverse: The example from this section is excellent. It first checks if f(x) = x+3 is a bijection and then demonstrates the algebraic method for finding its inverse, f^{-1}(x) = x-3.

The standard procedure to find the inverse of a function $y = f (x)$ is:

Verify Bijectivity: Confirm the function is both injective and surjective.
Solve for x: Rearrange the equation $y = f (x)$ to express $x$ in terms of $y$ . This gives you $x = f^{- 1} (y)$ .
Rewrite: Conventionally, we write the inverse function with $x$ as the input variable, so you can replace $y$ with $x$ in the final expression.

As you saw in the video, the process of proving surjectivity by solving for $x$ directly gives you the formula for the inverse.

Function Composition

Function composition is the process of applying one function to the result of another. It's like chaining operations in a pipeline. The composition of $g$ with $f$ , denoted $g \circ f$ , is defined as $(g \circ f) (x) = g (f (x))$ . You apply $f$ first, then apply $g$ to the output of $f$ .

The same video provides a clear walkthrough of composition.

Discrete Math - 2.3.3 Inverse Functions and Composition of Functions

Continuing with the same video, we'll now look at function composition.

Please watch the final parts of the video: Concept of Composition: The section from this timestamp illustrates how composition maps an element from the initial domain to the final codomain through an intermediate step. Computing Compositions: The detailed example starting from this point is crucial. It shows how to compute (f \circ g)(x) and (g \circ f)(x) and demonstrates that, in general, function composition is not commutative (i.e., f \circ g \neq g \circ f).

Let's work through a quick example. Let $f, g : R \to R$ be defined by $f (x) = x + 2$ and $g (x) = 3 x$ .

Find $(g \circ f) (x)$ : $(g \circ f) (x) = g (f (x)) = g (x + 2) = 3 (x + 2) = 3 x + 6$
Find $(f \circ g) (x)$ : $(f \circ g) (x) = f (g (x)) = f (3 x) = (3 x) + 2 = 3 x + 2$

As you can see, the order of composition matters.

Finally, inverse and composition are related: for any bijective function $f$ , applying the function and its inverse in either order gets you back to where you started.

(f \circ f^{- 1}) (x) = x and (f^{- 1} \circ f) (x) = x

Conclusion

In this lesson, we dissected the concept of a function, moving from a simple mapping to a structured object with verifiable properties. Understanding these properties is a prerequisite for many advanced topics and a frequent source of marks in the GATE exam.

Here are the key takeaways:

A function can be classified based on its mapping properties:
- Injective (one-to-one): Distinct inputs have distinct outputs.
- Surjective (onto): The range equals the codomain.
- Bijective: Both injective and surjective.
A function has an inverse if and only if it is bijective. The inverse reverses the function's mapping.
Function composition, $(g \circ f) (x) = g (f (x))$ , involves applying functions sequentially and is generally not commutative.

We have now added functions to our discrete mathematics toolkit, building upon the foundation of relations. In the next lesson, we will venture into Algebraic Structures. We will discover how sets, combined with binary operations (like function composition), can form powerful structures like monoids and groups, which have deep connections to automata theory and cryptography. You will see that the set of all bijections on a set, under the operation of composition, actually forms a group

Recommended resources