
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Surjection, Injection and Bijection Function
Functions are nothing but mapping relationships between different sets. To fully understand functions, we need to understand three key concepts: surjection, injection, and bijection. In this chapter, we will see each of these function types with examples and see how they differ from one another.
Functions in Sets and Relations
A function is a rule that takes elements from one set (domain) and assigns them to elements in another set (codomain). Every element in the domain must map to exactly one element in the codomain. However, the reverse is not necessarily true. For example, imagine we assign every student in a class a locker. Each student gets exactly one locker, but some lockers may remain unused.
Here is another example. Take a look at the following mapping: Here, each number from left has a square on the right −

Surjection Functions That Are "Onto"
A surjective function, also known as an "onto" function. It is a function where every element in the codomain is the image of at least one element in the domain. In simpler words, there are no unused elements in the codomain.
Formally, a function is surjective if every element of the codomain is the image of at least one element from the domain. Nothing in the codomain is left out.

Example of Surjection
Let us consider the function f : {1, 2, 3} → {a, b, c} defined by: f(1) = a, f(2) = b, f(3) = c
Here, every element in the codomain {a, b, c} has been "hit" by some element from the domain {1, 2, 3}. This means f is a surjective function because there are no elements left out in the codomain.
The following mapping presents another example −

Example of Non-Surjective
Now, consider a function g : {1, 2, 3} → {a, b, c} where: g(1) = a, g(2) = a, g(3) = c.
In this case, the element b from the codomain is never "hit" by any element from the domain. This means g is not surjective because something in the codomain is left out.
Surjections are important when we want to ensure that every possible output is covered. There is no leaving "gaps."
Injection Functions That Are "One-to-One"
On the other hand, the injective function, or "one-to-one" function, shows that no two different elements in the domain map to the same element in the codomain. This means every element in the codomain is the image of at most one element in the domain.
Formally, a function is injective if every element of the codomain is the image of at most one element from the domain. There are no "repeated" images in the codomain.

Example of Injection
Let us consider f : Z → Z (where Z represents all integers) is defined by: f(n) = 3n
For every integer n, f(n) produces a unique result. No two different integers will give the same value after being multiplied by 3. Therefore, this function is injective. It does not "reuse" codomain elements for different domain inputs.
Example of Non-Injective
Consider a function h : {1, 2, 3} → {a, b} defined by: h(1) = a, h(2) = a, h(3) = b
In this case, both h(1) and h(2) are mapped to a. Since two different domain elements are assigned to the same codomain element, h is not injective. Injection fails when there is "overlap" in the codomain.

Bijection The Perfect Function
Next comes the bijection functions. It is both injective and surjective. In other words, every element in the domain maps to a unique element in the codomain, and every element in the codomain is covered. This makes bijections "perfect" functions because they pair every element in the domain with one (and only one) element in the codomain, with no repeats and no leftovers.
Formally, a function is bijective if it is both injective and surjective, meaning it’s a one-to-one correspondence between the domain and codomain.
Example of Bijection
Consider the function f : {1, 2, 3} → {a, b, c}, defined as: f(1) = a, f(2) = b, f(3) = c.
This is a bijection because every element in the domain has a unique match in the codomain, and every codomain element is used. There are no repeated values and no leftover elements.

Example of Non-Bijective Function
If we modify f such that f(2) = a, then the function is no longer bijective. It might still be surjective (depending on the other values), but it is no longer injective because two elements in the domain share the same codomain value.

Combining Concepts: Injective vs Surjective
We understood the idea of injective and surjective. But these are essential to understand that injective and surjective functions are not opposites.
A function can be injective but not surjective; surjective but not injective; both; or neither.
- A function can be injective but miss out some elements in the codomain, making it not surjective.
- A function can be surjective but reuse elements of the codomain, making it not injective.
- A bijection is both injective and surjective, satisfying both properties.
Conclusion
In this chapter, we explained the concept of surjection, injection, and bijection functions in discrete mathematics. Surjection functions cover every element in the codomain. Injection functions avoid reusing codomain elements. Bijection functions do both. We also touched on inverse functions and how they only exist for bijections.