3.1 Function Mappings: Injective, Surjective & Bijective Classifications

Back to Discrete Mathematics Notes

📚Module 03: Functions & Pigeonhole PrincipleTopic 3.1: Function Mappings: Injective, Surjective & Bijective⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Hotel Room Key Allocation

Think of a function as an automated hotel check-in kiosk assigning guests to hotel rooms:

1. The Function Contract: Every arriving guest (element in the Domain) must receive a key, and no guest can be assigned two different rooms at the same time. However, multiple guests could be booked into the same presidential suite, and some rooms in the hotel (the Codomain) might remain vacant.
2. Injective (One-to-One): Strict private rooms! Every guest gets their own exclusive room. No two distinct guests ever share a room.
3. Surjective (Onto): 100% hotel occupancy! Every single room in the hotel has at least one guest sleeping in it. Zero vacant rooms left.
4. Bijective (One-to-One & Onto): Perfect one-to-one pairing! Every guest has their own exclusive private room, and every room in the hotel is occupied. Guest count equals room count ($|A| = |B|$).

💻 Bridging to Computer Science: Hash Functions, Compilers & Cryptography

In computer science, functions govern computation:

• Hash Tables: A hash function $h: K \to B$ maps search keys to bucket indices. If $h$ is injective, it is a perfect hash function with zero collisions.
• Relational Databases & Primary Keys: Primary key lookups are strictly injective; foreign keys form general functions.
• Cryptography & Block Ciphers: Encryption algorithms like AES must be strictly bijective so that ciphertext can be uniquely decrypted back to plaintext without data loss.

📑Table of Contents

• 📐 Mathematical Formalism of Functions
  • Diagnostic: Relation vs Valid Function
• ⚡ High-Yield Invariants: Set Images & Pre-Images
• 🔍 Injective, Surjective & Bijective Classifications
• 📊 Master Function Feasibility & Cardinality Matrix
• 📝 Step-by-Step Worked Examples
  • Example 1: Verifying Function Invariants on Discrete Sets
  • Example 2: Analyzing Real-Valued Functions
• 🎯 Exam & Interview Pitfall Check

---

📐 Mathematical Formalism of Functions

A function is a special type of binary relation with two strict operational invariants: every input must participate, and each input must produce exactly one deterministic output.

📖Definition 3.1: Formal Function Definitiondefinition

Let $A$ and $B$ be non-empty sets. A function (or mapping) $f$ from $A$ to $B$, denoted:

$$f: A \to B$$

is a binary relation $f \subseteq A \times B$ satisfying two fundamental axioms:

1. Total Existence (Totality): Every element in the domain must participate in the mapping: $$\forall a \in A, \; \exists b \in B \text{ such that } (a, b) \in f$$
2. Uniqueness (Deterministic Output): No element in the domain can map to multiple distinct elements in the codomain: $$(a, b_1) \in f \land (a, b_2) \in f \implies b_1 = b_2$$

If $(a, b) \in f$, we write $f(a) = b$, where $b$ is the image of $a$, and $a$ is the pre-image of $b$.

Core Anatomical Sets:

• Domain ($\text{Dom } f$): The source set $A$ of all permissible inputs.
• Codomain ($\text{Codom } f$): The declared target universe $B$ where outputs land.
• Range / Image ($\text{Im } f$): The subset of actual outputs hit by inputs: $$\text{Range}(f) = \{ f(a) \mid a \in A \} \subseteq B$$

Fundamental Invariant: $\text{Range}(f) \subseteq \text{Codomain}(B)$.

Diagnostic: Relation vs Valid Function

To determine whether an arbitrary binary relation $R \subseteq X \times Y$ qualifies as a valid function, we test it against the two axioms:

Relation Instance	First Coordinate Invariant	Second Coordinate Invariant	Function Verdict	Operational Reason
$R_1 = \{(1, 2), (2, 3), (3, 4)\}$ on $X=\{1, 2, 3\}, Y=\{2, 3, 4, 5\}$	Every $x \in X$ appears exactly once	Exactly 1 target per input	Valid Function	Satisfies both Totality and Uniqueness. Notice $5 \in Y$ is untouched ($\text{Range} \subset Y$).
$R_2 = \{(1, 2), (4, 5), (5, 5), (5, 7)\}$ on $X=\{1, 2, 3, 4, 5\}, Y=\{2, 3, 4, 5, 6, 7\}$	Elements $2, 3 \in X$ are missing	Input $5$ maps to both $5$ and $7$	Invalid Function	Fails Totality (unmapped inputs) AND fails Uniqueness (one-to-many branching).
$R_3 = \{(1, 2), (2, 2), (3, 2)\}$ on $X=\{1, 2, 3\}, Y=\{2, 4\}$	Every $x \in X$ appears exactly once	All inputs share target $2$	Valid Function	Many-to-one is completely legal! Range is $\{2\} \subseteq Y$.

---

⚡ High-Yield Invariants: Set Images & Pre-Images

A frequent source of errors in discrete exams is assuming that set operations distribute identically across forward function images and inverse pre-images. The following invariants govern subsets $E, F \subseteq A$ and $S, T \subseteq B$ under $f: A \to B$:

📐Theorem 3.1: Set Image and Pre-Image Invariantstheorem

Let $f: A \to B$ be an arbitrary function. For any subsets $E, F \subseteq A$ and $S, T \subseteq B$:

1. Union commutes with forward image: $$f(E \cup F) = f(E) \cup f(F)$$
2. Intersection does NOT in general commute with forward image: $$f(E \cap F) \subseteq f(E) \cap f(F)$$ Equality $f(E \cap F) = f(E) \cap f(F)$ holds for all subsets $E, F$ if and only if $f$ is injective (one-to-one)!
3. Pre-images commute unconditionally with both Union and Intersection: $$f^{-1}(S \cup T) = f^{-1}(S) \cup f^{-1}(T)$$ $$f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$$
4. Cardinality Inequalities: $$|f(A \cup B)| \neq |f(A)| + |f(B)| \quad \text{and} \quad |f(A \cap B)| \neq \min\{|f(A)|, |f(B)|\}$$

Concrete Counter-Example: Why Forward Image Fails on Intersections

Let $A = \{1, 2\}$ and $B = \{k\}$. Define $f(1) = k$ and $f(2) = k$ (a non-injective function).
Choose disjoint subsets $E = \{1\}$ and $F = \{2\}$:

• Left Side: $E \cap F = \emptyset \implies f(E \cap F) = f(\emptyset) = \emptyset$.
• Right Side: $f(E) = \{k\}$ and $f(F) = \{k\} \implies f(E) \cap f(F) = \{k\}$.
• Notice that $\emptyset \subset \{k\}$. Therefore, $f(E \cap F) \subsetneq f(E) \cap f(F)$.
  When $f$ is injective, elements cannot share images, restoring strict equality!

---

🔍 Injective, Surjective & Bijective Classifications

Injective (One-to-One) vs Surjective (Onto) Mappings

The two foundational orthogonality dimensions of mathematical functions

Injective

Injection (One-to-One)

🏹

Dominant Architecture / DomainCollision-Free Output Distribution

• •Distinct domain elements map to distinct codomain elements.
• •Formal: f(x₁) = f(x₂) ⟹ x₁ = x₂ (Contrapositive: x₁ ≠ x₂ ⟹ f(x₁) ≠ f(x₂)).
• •Pre-images are unique: Every y ∈ B has at most one pre-image.
• •Necessary Cardinality Bound: |A| ≤ |B|.

"No two arrows ever strike the same target."

Surjective

Surjection (Onto)

🎯

Dominant Architecture / DomainExhaustive Codomain Coverage

• •Every element of the codomain is the image of at least one domain element.
• •Formal: ∀y ∈ B, ∃x ∈ A such that f(x) = y.
• •Full coverage: Range(f) = Codomain(B). Zero untouched elements.
• •Necessary Cardinality Bound: |A| ≥ |B|.

"Every point in the target set receives at least one incoming arrow."

📖Definition 3.2: Bijective Function (One-to-One Correspondence)definition

A function $f: A \to B$ is bijective (or a bijection, or a one-to-one correspondence) if and only if it is simultaneously:

1. Injective (One-to-One), and
2. Surjective (Onto).

Cardinality Invariant for Finite Sets: If $A$ and $B$ are finite sets, a bijection exists between $A$ and $B$ if and only if:

$$|A| = |B|$$

When $|A| = |B| = n$, every injective function is automatically surjective, and every surjective function is automatically injective!

---

📊 Master Function Feasibility & Cardinality Matrix

For finite sets $A$ with $|A| = m$ and $B$ with $|B| = n$, mapping feasibility is strictly determined by cardinality:

Cardinality Condition	Injective $f: A \to B$	Surjective $f: A \to B$	Bijective $f: A \to B$	Core Intuition & Governing Invariant
$m \lt n$ ($\vert A \vert \lt \vert B \vert$)	Possible	Impossible ($0$)	Impossible ($0$)	Plenty of targets for distinct assignments; impossible to cover $n$ targets with only $m$ domain elements.
$m \gt n$ ($\vert A \vert \gt \vert B \vert$)	Impossible ($0$)	Possible	Impossible ($0$)	By Pigeonhole Principle, collisions are inevitable; sufficient domain elements exist to cover all $n$ targets.
$m = n$ ($\vert A \vert = \vert B \vert$)	Possible	Possible	Possible	Equivalence Theorem: For finite sets of equal size, $\text{Injection} \iff \text{Surjection} \iff \text{Bijection}$.

---

📝 Step-by-Step Worked Examples

Example 1: Verifying Function Invariants on Discrete Sets

Problem Statement: Let $A = \{1, 2, 3\}$ and $B = \{a, b, c, d\}$. Determine whether each of the following relations is a function, and if so, classify whether it is injective, surjective, or bijective:

1. $R_1 = \{(1, a), (2, b), (3, c)\}$
2. $R_2 = \{(1, a), (2, b), (2, c), (3, d)\}$
3. $R_3 = \{(1, a), (3, b)\}$
4. $R_4 = \{(1, b), (2, b), (3, b)\}$

Step-by-Step Solution:

1. Analysis of $R_1$:

   • Totality: Every element in $A$ ($1, 2, 3$) appears as the first coordinate.
   • Uniqueness: No first coordinate is repeated. Thus, $R_1$ is a valid function $f: A \to B$.
   • Injectivity: $f(1) = a, f(2) = b, f(3) = c$. All images are distinct. Hence, $R_1$ is Injective.
   • Surjectivity: The codomain is $\{a, b, c, d\}$, but the range is $\{a, b, c\}$. Since $d \notin \text{Range}$, it is NOT Surjective.
   • Classification: Injective but not surjective.

2. Analysis of $R_2$:

   • Element $2 \in A$ appears twice with different outputs: $(2, b)$ and $(2, c)$.
   • Violates the Uniqueness Axiom.
   • Classification: Not a function.

3. Analysis of $R_3$:

   • Element $2 \in A$ does not appear as a first coordinate.
   • Violates the Totality Axiom.
   • Classification: Not a function (merely a partial function).

4. Analysis of $R_4$:

   • Totality: Every element in $A$ ($1, 2, 3$) has an image.
   • Uniqueness: Each has exactly one image ($b$). Thus, $R_4$ is a valid function.
   • Injectivity: $f(1) = f(2) = f(3) = b$, yet $1 \neq 2$. Not injective.
   • Surjectivity: Range is $\{b\} \neq B$. Not surjective.
   • Classification: Neither injective nor surjective (Many-to-one into function).

Key Takeaway: A valid function requires every element of the domain to have exactly one outgoing arrow.

---

Example 2: Analyzing Real-Valued Functions

Problem Statement: Determine whether the function $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 3x - 5$ is bijective.

Step-by-Step Solution:

1. Step 1: Test for Injectivity (One-to-One)

   • Assume $f(x_1) = f(x_2)$ for arbitrary $x_1, x_2 \in \mathbb{R}$: $$3x_1 - 5 = 3x_2 - 5$$
   • Add $5$ to both sides: $$3x_1 = 3x_2$$
   • Divide by $3$: $$x_1 = x_2$$
   • Since $f(x_1) = f(x_2) \implies x_1 = x_2$, the function is strictly Injective.

2. Step 2: Test for Surjectivity (Onto)

   • Let $y \in \mathbb{R}$ be an arbitrary element in the codomain. We must find an $x \in \mathbb{R}$ such that $f(x) = y$: $$y = 3x - 5 \implies 3x = y + 5 \implies x = \frac{y + 5}{3}$$
   • Since $y \in \mathbb{R}$, $\frac{y + 5}{3}$ is also a well-defined real number ($x \in \mathbb{R}$).
   • Verifying the image: $$f(x) = f\left(\frac{y + 5}{3}\right) = 3\left(\frac{y + 5}{3}\right) - 5 = (y + 5) - 5 = y$$
   • Every real number $y$ has a pre-image in the domain. Hence, $f$ is strictly Surjective.

3. Step 3: Conclusion

   • Because $f$ is both injective and surjective, $f$ is a Bijective function.

Key Takeaway: For algebraic functions, injectivity is proven by equating $f(x_1) = f(x_2)$ and solving for $x_1 = x_2$; surjectivity is proven by solving $y = f(x)$ for $x$ and verifying that the resulting expression is defined for all $y$ in the codomain.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If a function $f: A \to B$ is injective, does altering the codomain $B$ to equal $\text{Range}(f)$ always turn it into a bijection? Key Focus Points: Yes! By definition, an injection only fails to be surjective if there are elements in $B \setminus \text{Range}(f)$. If we restrict the codomain to $B' = \text{Range}(f)$, the mapping $f: A \to B'$ becomes both injective and surjective, hence a bijection.

Question 2: Can an infinite set have an injection into a proper subset of itself? Key Focus Points: Yes! This is Dedekind's definition of an infinite set. For example, $f: \mathbb{N} \to \mathbb{N}$ defined by $f(n) = 2n$ maps all natural numbers to the even natural numbers (a strict proper subset), and $f$ is strictly injective. For finite sets, this is impossible.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming $f(x) = x^2$ is always non-injective Why it fails: Injectivity depends strictly on the Domain, not just the algebraic rule! If $f: \mathbb{R} \to \mathbb{R}$ where $f(x) = x^2$, it is NOT injective because $f(-2) = f(2) = 4$. However, if $f: \mathbb{R}^+ \to \mathbb{R}$ (positive real numbers only), $f(x) = x^2$ is strictly injective because negative values do not exist in the domain! Always check the domain and codomain boundaries first.

Trap 2: Confusing Codomain with Range Why it fails: In function notation $f: A \to B$, set $B$ is the Codomain, NOT necessarily the Range. The Range is the actual set of outputs $\{f(a) \mid a \in A\}$. Confusing the two causes errors in surjectivity proofs.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic2.3 Relational Closures, Warshall's Algorithm & Equivalence PartitionsNext Topic →3.2 Function Inversion, Composition & Counting of Special Mappings