3.2 Function Inversion, Composition & Counting of Special Mappings

Back to Discrete Mathematics Notes

📚Module 03: Functions & Pigeonhole PrincipleTopic 3.2: Function Inversion, Composition & Special Mappings⏱️5 min read

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

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Assembly Line Processing & Reversible Operations

Think of function composition and inversion like an automated manufacturing pipeline:

1. Composition ($g \circ f$): Stage 1 ($f$) wraps an item in protective bubble wrap; Stage 2 ($g$) places the wrapped item into a cardboard shipping box. The combined workflow ($g \circ f$) takes the raw item and delivers the boxed package. Notice the order: you apply $f$ first, then $g$!
2. Inversion ($f^{-1}$): The reverse disassembly procedure. If you packed a box, the inverse opens it and extracts the original item. You can only invert a procedure if it is bijective:
   • If two different items were packed into identical boxes (not injective), unpacking cannot tell which item was original!
   • If some boxes came from thin air without an item (not surjective), unpacking those boxes fails!
3. The Reversal Law: If you put on socks ($f$) and then put on shoes ($g$), to undo the process you must take off your shoes first ($g^{-1}$), and then take off your socks ($f^{-1}$). Hence: $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

💻 Bridging to Computer Science: Unix Pipes, Functional Programming & Compilers

In software systems:

• Unix Pipelines: cat log.txt | grep ERROR | wc -l is the pure composition of three functions: $(h \circ g \circ f)(x)$.
• Functional Programming: High-order functions like map, filter, and compose directly execute mathematical composition.
• Cryptography & Decryption: Symmetric and asymmetric decryption keys compute $f^{-1}(c) = m$.
• Database Query Plans: A multi-table join plan is composed of relational operators whose inversion allows transactional rollback.

📑Table of Contents

• 🔄 Function Composition: Chaining Transformations
  • Concrete Evaluation Trace of Composition
  • Fundamental Properties of Function Composition
• ⚡ Composition Preservation & The Backward Deduction Rule
• ↩️ Inverse Functions & The Reversal Law
• 🔢 Exhaustive Counting Formulas for Finite Sets
  • Master Function Counting Reference Table
• 📝 Step-by-Step Worked Examples
  • Example 1: Verifying the Backward Deduction Rule
  • Example 2: Counting All Surjective Functions
• 🎯 Exam & Interview Pitfall Check

---

🔄 Function Composition: Chaining Transformations

📖Definition 3.3: Function Compositiondefinition

Let $f: A \to B$ and $g: B \to C$ be functions. The composition of $g$ and $f$, denoted by:

$$g \circ f: A \to C$$

is a function from $A$ to $C$ defined for all $x \in A$ by:

$$(g \circ f)(x) = g(f(x))$$

Domain & Codomain Requirement: For $g \circ f$ to be defined, the Range of $f$ must be a subset of the Domain of $g$:

$$\text{Range}(f) \subseteq \text{Domain}(g)$$

Architecture Flow

The Two-Stage Function Composition Pipeline

Sequential evaluation from input element x to final transformed output g(f(x))

📥Input Set A

Element x

Domain input value fed into initial mapping f.

→

Apply f(x)

⚙️Intermediate Set B

Image f(x)

Codomain of f serving as input domain for downstream mapping g.

→

Apply g(·)

🎯Output Set C

Final Output g(f(x))

Resulting element in Codomain C representing (g ∘ f)(x).

Concrete Evaluation Trace of Composition

Consider sets $A = \{1, 2, 3, 4\}$, $B = \{1, 2, 3, 4, 5, 6\}$, and $C = \{1, 2, 3, 4, 5\}$. Let functions $f: A \to B$ and $g: B \to C$ be defined by:

$$f = \{(1, 3), (2, 1), (3, 4), (4, 6)\} \quad \text{and} \quad g = \{(1, 5), (2, 3), (3, 4), (4, 1), (5, 3), (6, 2)\}$$

We trace each input element $x \in A$ through the intermediate image $f(x) \in B$ to the final output $g(f(x)) \in C$:

Input $x \in A$	First Stage $f(x) \in B$	Second Stage $g(f(x)) \in C$	Composite Pair in $(g \circ f)$
$1$	$f(1) = 3$	$g(3) = 4$	$(1, 4)$
$2$	$f(2) = 1$	$g(1) = 5$	$(2, 5)$
$3$	$f(3) = 4$	$g(4) = 1$	$(3, 1)$
$4$	$f(4) = 6$	$g(6) = 2$	$(4, 2)$

$$(g \circ f) = \{(1, 4), (2, 5), (3, 1), (4, 2)\} \subseteq A \times C$$

---

Fundamental Properties of Function Composition

📐Theorem 3.1: Algebraic Laws of Function Compositiontheorem

1. Associativity: Function composition is strictly associative. If $f: A \to B$, $g: B \to C$, and $h: C \to D$, then: $$h \circ (g \circ f) = (h \circ g) \circ f$$
2. Non-Commutativity: In general, function composition is NOT commutative: $$g \circ f \neq f \circ g$$ (Often, if $g \circ f$ is defined, $f \circ g$ may not even be defined because domain and codomain boundaries do not align).
3. Identity Element: For any function $f: A \to B$: $$f \circ I_A = f \quad \text{and} \quad I_B \circ f = f$$ where $I_A(x) = x$ and $I_B(y) = y$ are the identity mappings on sets $A$ and $B$.

---

⚡ Composition Preservation & The Backward Deduction Rule

How do injectivity and surjectivity propagate across chained mappings? The following theorems establish the exact forward and backward dependencies:

Direction & Hypothesis	Guaranteed Conclusion	Non-Guaranteed Counter-Trap	Core Intuition
Forward: $f$ and $g$ are Injective	$(g \circ f)$ is Injective	—	Collision-free pipeline: if neither stage collides, the composite cannot collide.
Forward: $f$ and $g$ are Surjective	$(g \circ f)$ is Surjective	—	Complete coverage: every target in $C$ has a pre-image in $B$, which has a pre-image in $A$.
Backward: $(g \circ f)$ is Injective	$f$ MUST be Injective	$g$ does NOT need to be injective	If $f$ collides at step 1, $g$ can never un-collide them. But collisions in $g$ outside $\text{Range}(f)$ are irrelevant!
Backward: $(g \circ f)$ is Surjective	$g$ MUST be Surjective	$f$ does NOT need to be surjective	The final stage $g$ must cover all of $C$. Unreached elements in intermediate set $B$ don't harm coverage of $C$.
Backward: $(g \circ f)$ is Bijective	$f$ is Injective AND $g$ is Surjective	Neither $f$ nor $g$ is individually forced to be bijective	The first stage guarantees no collisions; the final stage guarantees full coverage.

The Golden Exam Rule

$$(g \circ f) \text{ is One-to-One} \implies \mathbf{f} \text{ (first function) must be One-to-One}$$$$(g \circ f) \text{ is Onto} \implies \mathbf{g} \text{ (second function) must be Onto}$$

Always remember: Injectivity tests the input end ($f$), while Surjectivity tests the output end ($g$)!

---

↩️ Inverse Functions & The Reversal Law

📖Definition 3.4: Inverse Functiondefinition

Let $f: A \to B$ be a function. An inverse function $f^{-1}: B \to A$ exists if and only if $f$ is a bijection (both injective and surjective).

When $f$ is bijective, $f^{-1}$ is uniquely defined by:

$$f^{-1}(b) = a \iff f(a) = b$$

Satisfying the identity compositions:

$$f^{-1} \circ f = I_A \quad \text{and} \quad f \circ f^{-1} = I_B$$

📐Theorem 3.2: The Reversal Law of Inversiontheorem

If $f: A \to B$ and $g: B \to C$ are both bijective functions, then $(g \circ f): A \to C$ is bijective, and its inverse is given by the socks-and-shoes reversal law:

$$(g \circ f)^{-1} = f^{-1} \circ g^{-1}$$

Proof Derivation: Multiply $(g \circ f)$ by $(f^{-1} \circ g^{-1})$ on the right:

$$(g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ (f \circ f^{-1}) \circ g^{-1} = g \circ I_B \circ g^{-1} = g \circ g^{-1} = I_C$$

Similarly, on the left:

$$(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = f^{-1} \circ I_B \circ f = f^{-1} \circ f = I_A$$

Because the inverse is unique, $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

---

🔢 Exhaustive Counting Formulas for Finite Sets

Let domain set $A$ have $|A| = m$ elements and codomain set $B$ have $|B| = n$ elements:

Master Function Counting Reference Table

Function Category	Cardinality Constraint	Counting Formula	Derivation Principle
Total Functions	Any $m \ge 0, n \ge 1$	$\mathbf{n^m}$	Each of the $m$ domain elements independently chooses any of the $n$ codomain targets ($n \times n \times \dots \times n$).
Injective Functions (1-to-1)	$m \le n$ ($m \gt n \implies 0$)	$\mathbf{P(n, m) = \frac{n!}{(n - m)!}}$	Targets chosen without replacement: $n(n - 1)(n - 2)\dots(n - m + 1)$. When $m \gt n$, collisions forced by Pigeonhole Principle.
Surjective Functions (Onto)	$m \ge n$ ($m \lt n \implies 0$)	$\mathbf{n! \cdot S(m, n) = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)^m}$	Principle of Inclusion-Exclusion (PIE): total functions minus functions missing $\ge 1$ target, plus functions missing $\ge 2$ targets, etc.
Bijective Functions	$m = n$ ($m \neq n \implies 0$)	$\mathbf{n!}$	Perfect permutation of $n$ elements into $n$ slots ($P(n, n) = n!$).
Strictly Increasing ($A, B \subset \mathbb{R}$)	$m \le n$ ($m \gt n \implies 0$)	$\mathbf{\binom{n}{m}}$	Choosing any $m$ targets from $n$ has exactly $1$ unique sorting in strictly increasing order.

📐Formula 3.1: Detailed Surjective Function Expansion (PIE)formula

The number of surjective functions from set $A$ ($|A| = m$) to set $B$ ($|B| = n$) where $m \ge n$ is given by:

$$\text{Onto}(m, n) = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)^m$$

Expanded explicitly:

$$\text{Onto}(m, n) = n^m - \binom{n}{1}(n-1)^m + \binom{n}{2}(n-2)^m - \binom{n}{3}(n-3)^m + \dots + (-1)^{n-1}\binom{n}{n-1}(1)^m$$

Connection to Stirling Numbers of the Second Kind: $S(m, n)$ counts the number of ways to partition $m$ distinct items into $n$ unlabeled non-empty groups:

$$\text{Onto}(m, n) = n! \cdot S(m, n)$$

---

📝 Step-by-Step Worked Examples

Example 1: Verifying the Backward Deduction Rule

Problem Statement: Let $f: A \to B$ and $g: B \to C$. Prove that if $g \circ f$ is injective, then $f$ must be injective. Provide a concrete counter-example showing that $g$ does not need to be injective.

Step-by-Step Solution:

1. Step 1: Direct Proof that $f$ must be injective

   • We must show: $f(x_1) = f(x_2) \implies x_1 = x_2$.
   • Suppose $f(x_1) = f(x_2)$ for $x_1, x_2 \in A$.
   • Apply function $g$ to both sides: $$g(f(x_1)) = g(f(x_2))$$
   • By definition of composition, this is: $$(g \circ f)(x_1) = (g \circ f)(x_2)$$
   • Since $g \circ f$ is given to be injective, $(g \circ f)(x_1) = (g \circ f)(x_2)$ implies: $$x_1 = x_2$$
   • Hence, $f$ must be injective!

2. Step 2: Concrete Counter-Example showing $g$ need not be injective

   • Let $A = \{1\}$, $B = \{a, b\}$, and $C = \{z\}$.
   • Define $f: A \to B$ by $f(1) = a$ (injective).
   • Define $g: B \to C$ by $g(a) = z$ and $g(b) = z$. Notice that $g$ is NOT injective because $g(a) = g(b) = z$ while $a \neq b$.
   • Now compute $(g \circ f): A \to C$: $$(g \circ f)(1) = g(f(1)) = g(a) = z$$
   • Since $A$ has only 1 element, $(g \circ f)$ is trivially injective!
   • Thus, $(g \circ f)$ is injective even though $g$ is not.

Key Takeaway: Injectivity of $g \circ f$ guarantees injectivity of the first function ($f$), while surjectivity of $g \circ f$ guarantees surjectivity of the second function ($g$).

---

Example 2: Counting All Surjective Functions

Problem Statement: Let $A = \{1, 2, 3, 4\}$ and $B = \{x, y, z\}$. Find:

1. The total number of functions from $A$ to $B$.
2. The total number of injective functions from $A$ to $B$.
3. The total number of surjective functions from $A$ to $B$.

Step-by-Step Solution:

1. Step 1: Total Functions

   • Here $m = |A| = 4$ and $n = |B| = 3$.
   • Total functions = $n^m = 3^4 = 81$.

2. Step 2: Injective Functions

   • Since $|A| = 4 \gt |B| = 3$, by the Pigeonhole Principle at least two domain elements must map to the same target.
   • Therefore, number of injective functions = $0$.

3. Step 3: Surjective Functions (PIE Formula)

   • Using the formula $\text{Onto}(m, n) = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)^m$: $$\text{Onto}(4, 3) = \binom{3}{0} 3^4 - \binom{3}{1} (3-1)^4 + \binom{3}{2} (3-2)^4 - \binom{3}{3} (3-3)^4$$
   • Calculate each term:
     • Term 1: $1 \cdot 3^4 = 81$
     • Term 2: $-3 \cdot 2^4 = -3 \cdot 16 = -48$
     • Term 3: $+3 \cdot 1^4 = +3 \cdot 1 = +3$
     • Term 4: $-1 \cdot 0^4 = 0$
   • Summing the terms: $$\text{Onto}(4, 3) = 81 - 48 + 3 - 0 = 36$$
   • Verification via Stirling numbers: $$S(4, 3) = 6 \implies 3! \cdot S(4, 3) = 6 \cdot 6 = 36$$

Key Takeaway: Always check the cardinalities: if $m \lt n$, onto functions are $0$; if $m \gt n$, one-to-one functions are $0$.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If $f: A \to B$ and $g: B \to A$ satisfy $g(f(x)) = x$ for all $x \in A$, is $f$ necessarily bijective? Key Focus Points: No! $g(f(x)) = x$ means $(g \circ f) = I_A$, which proves that $f$ is injective and $g$ is surjective. However, $f$ does NOT have to be surjective, and $g$ does NOT have to be injective! For $f$ to be bijective, both $(g \circ f) = I_A$ and $(f \circ g) = I_B$ must hold simultaneously.

Question 2: How many functions from set $A$ ($|A| = n$) to itself are strictly increasing if $A \subset \mathbb{R}$? Key Focus Points: Exactly $1$! For any subset of $n$ elements chosen from the codomain, there is only one way to arrange them in strictly increasing order. Since $|A| = |B| = n$, all $n$ elements must be selected, giving $\binom{n}{n} = 1$ unique function (the identity function $f(x) = x$).

Common Interview Traps: Architectural Trade-Offs

Trap 1: Evaluating $(g \circ f)(x)$ in the wrong order Why it fails: In $(g \circ f)(x)$, students often mistakenly evaluate $g(x)$ first. In mathematical notation, $(g \circ f)(x) = g(f(x))$: the rightmost function ($f$) acts on $x$ first! Always read compositions from right to left.

Trap 2: Forgetting the Reversal Law for Inverses Why it fails: When inverting a pipeline $(g \circ f)^{-1}$, writing $g^{-1} \circ f^{-1}$ is invalid. The outer layer must be unpacked first, yielding $f^{-1} \circ g^{-1}$.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic3.1 Function Mappings: Injective, Surjective & Bijective ClassificationsNext Topic →3.3 The Generalized Pigeonhole Principle & Classical Combinatorial Proofs