Introduction:
In the field of mathematics, particularly in set theory and discrete
mathematics, understanding the nature of functions is fundamental. Functions
describe how elements of one set (called the domain) relate to elements of
another set (called the codomain). Among the various classifications, three
types of functions are particularly important: injective (one-to-one), surjective
(onto), and bijective (one-to-one and onto).
This report aims to deeply analyze these three function types, compare them,
provide rigorous definitions, use mathematical notation, and illustrate their
practical relevance with multiple real-life examples.
Basic Concepts of Functions:
A function f from a set A to a set B, written as f : A → B, is a relation that
assigns each element in set A to exactly one element in set B. In other words:
Every input must have an output.
No input has more than one output.
Injective Functions (One-to-One)
Definition:
A function f:A→Bf: A \to Bf:A→B is injective if different elements in the domain
map to different elements in the codomain.
Formally:
∀a1, a2∈A, f(a1) = f(a2) ⇒ a1 = a2
Or contrapositive:
a1 ≠ a2 ⇒ f(a1) ≠ f(a2)
Graphical Understanding:
In a mapping diagram, no two arrows from different domain elements point to
the same codomain element.
Mathematical Example:
Let A = {1,2,3}, B = {4,5,6,7}
Define function f(x) = x + 3
Then:
f(1) = 4
f(2) = 5
f(3) = 6
Each element of A maps to a distinct value in B → Injective
Real-World Examples:
1. Roll Numbers of Students:
o Each student has a unique roll number.
o No two students share the same roll number.
o This mapping is injective.
2. Email IDs:
o A user has only one unique email address.
o No two users have the same email.
3. PAN Card Numbers:
o Each citizen has a unique Permanent Account Number.
o This system is designed to be injective.
Surjective Functions (Onto)
Definition:
A function f:A→B is surjective if every element of B is the image of at least
one element of A.
Formally:
∀b ∈ B, ∃a ∈ A such that f(a) = b
Graphical Understanding:
All elements of the codomain have at least one arrow pointing to them.
Mathematical Example:
Let A = {1,2,3} B = {x,y}
Define f such that:
f(1) = x,
f(2) = y,
f(3) = y
Here, all elements in B (x and y) are hit at least once → Surjective
Real-World Examples:
1. Job Assignments:
o Suppose each job must be filled, even if one person does two jobs.
o Every job (codomain) is assigned → Surjection.
2. Classroom Bench Allocation:
o Every bench is occupied (some by two students).
o Each bench is covered → Surjection.
3. Color Codes for Status:
o If all possible colors (green, yellow, red) are in use, the mapping of
system states to colors is surjective.
Bijective Functions (One-to-One and Onto)
Definition:
A function f : A → B is bijective if it is both injective and surjective. This means:
Every element in A maps to a unique element in B.
Every element in B is covered by the mapping.
Formally:
∀b ∈ B, ∃!a ∈ A such that f(a)=b
Graphical Understanding:
Each element of A maps to a unique element of B, and B has no leftover
elements.
Mathematical Example:
Let A = {1,2,3} B = {a,b,c}
Define:
f(1) = a,
f(2) = b,
f(3) = c
Each A maps to unique B, and all B are used → Bijective
Real-World Examples:
1. Aadhar Number Mapping:
o Each citizen has a unique Aadhar.
o Every Aadhar maps to exactly one citizen → Bijective.
2. Inventory SKU Codes:
o Each item has a unique SKU.
o No duplication and no gaps → Bijective.
3. One-to-One Student Seat Allocation:
o Each student gets one unique seat, and every seat is filled →
Bijective.
Visual Summary
Property Injective Surjective Bijective
Uniqueness Yes Not required Yes
Partial or
Coverage of Codomain Full Full
Full
Not
Invertible Not always Always
always
ℤ
f(x) = x + 1 over
Example Function f(x) = 2x f( x) = x^3
Invertibility and Function Types
Injective: Can define a left inverse.
Surjective: Can define a right inverse.
Bijective: Inverse function exists and is well-defined.
Example:
Let f(x) = x + 3 over real numbers.
Injective? Yes.
Surjective? Yes (over real numbers).
Bijective? Yes.
Inverse: f^−1(x) = x – 3
Importance in Computer Science
1. Hash Functions (Injective):
o Attempt to avoid collisions, hence designed to be as injective as
possible.
2. Memory Management (Surjective):
o Every addressable memory unit must be used efficiently → surjection
helps.
3. Data Encryption and Decryption (Bijective):
o Encoding and decoding rely on bijective functions for perfect
reversibility.
4. Database Relationships:
o One-to-One → Bijective
o One-to-Many → Not Injective
o Many-to-One → Not Injective
Application Scenarios
Function
Domain Use Case
Type
Secure encryption and
Cryptography Bijective
decryption
Student Enrollment Injective Unique ID assignment
Job Portal Matching Surjective Ensuring all jobs are filled
Unique URLs for different
URL Shorteners Injective
content
Compiler Design Bijective Token mapping and parsing
Conclusion
The concepts of injective, surjective, and bijective functions form a
fundamental pillar in discrete mathematics and its applications in computer
science, data structures, cryptography, and logic. Understanding these types of
functions allows for deeper insight into how systems map data, allocate
resources, and maintain consistency.
By using both formal definitions and real-world parallels, this report has shown
not only how to identify function types but also why they matter in theoretical
and applied domains.
