Set Theory & Elementary Group Theory

Mapping

Mappings (or functions) form the foundational architecture of abstract algebra, real analysis, and topology, defining precise correspondences between domain and codomain sets. This topic covers injectivity, surjectivity, bijectivity, and compositional inverses.

For: UP PGT Mathematics UP TGT Mathematics DSSSB PGT / TGT KVS / NVS PGT LT Grade

📖 Topic progress

○ Mark as complete

Definition and statement

Principle of Invertibility and Bijective Correspondence

Let $f: A \to B$ be a mapping. Then $f$ is invertible if and only if $f$ is a bijection (both injective and surjective). That is, there exists a unique mapping $f^{-1}: B \to A$ such that $f^{-1} \circ f = I_A$ and $f \circ f^{-1} = I_B$.

📐 Geometric Interpretation

Geometrically, a bijective mapping establishes a one-to-one reflection symmetry across the line $y = x$ when graphed in the Cartesian plane, ensuring every horizontal line intersects the graph at exactly one point (injectivity) and every horizontal line in the codomain is hit (surjectivity).

⚙️ Algebraic & Structural Meaning

Algebraically, bijectivity guarantees the existence of a unique group isomorphism or invertible linear transformation, serving as the cornerstone for cardinality comparisons of infinite sets and permutation structures.

Conditions and hypotheses

Check each condition and what changes when it is omitted:

Hypothesis / Condition	Domain / Interval	Necessity	What Fails If Condition Dropped
Non-emptiness of Domain and Codomain	`Sets $A \neq \emptyset, B \neq \emptyset$`	Strictly Mandatory / Necessary	Empty sets trivialise mappings or create undefined empty domain compositions.
Injectivity (One-to-One)	`For all $x_1, x_2 \in A$`	Mandatory for Left-Invertibility	Distinct domain elements mapping to the same codomain element destroys left cancellation and injectivity.
Surjectivity (Onto)	`For all $y \in B$`	Mandatory for Right-Invertibility	Uncovered elements in the codomain prevent the definition of a backward mapping for every target element.

Useful results and shortcuts

Use these identities and results when their conditions apply:

Total Mappings Between Finite Sets

$$ \text{Total mappings from } A \text{ to } B = |B|^{|A|} $$

Rule: If $|A| = m$ and $|B| = n$, the total number of distinct functions $f: A \to B$ is $n^m$.

Application: Directly tested in UP PGT/TGT to find mapping counts under discrete finite sets.

Number of Injective (One-to-One) Mappings

$$ \text{Number of injective mappings} = \begin{cases} nPm = \frac{n!}{(n-m)!}, & \text{if } m \le n \\ 0, & \text{if } m > n \end{cases} $$

Rule: If domain size exceeds codomain size ($m > n$), injective mapping count collapses to zero by the Pigeonhole Principle.

Number of Bijective Mappings

$$ \text{Number of bijections} = \begin{cases} n!, & \text{if } m = n \\ 0, & \text{if } m \neq n \end{cases} $$

Rule: Bijections exist if and only if domain and codomain have equal cardinality $n$.

Monotonicity and Injectivity for Continuous Functions

$$ f'(x) > 0 \quad \forall x \in I \quad \text{or} \quad f'(x) < 0 \quad \forall x \in I $$

Rule: Strictly monotonic functions on an interval are always injective (one-to-one).

Number of Surjective Mappings

$$ \sum_{r=0}^{n} (-1)^{n-r} \binom{n}{r} r^m $$

Rule: Formula for onto functions from a set of size $m$ to a set of size $n$ using inclusion-exclusion.

Application: Advanced UP PGT questions involving combinatorial mapping counts.

Rapid Self-Inverse Check

$$ f(f(x)) = x \implies f^{-1}(x) = f(x) $$

Rule: If compounding a function with itself yields the identity, the function is its own inverse.

Application: Quick elimination trick for functional equations.

Common errors and counterexamples

These examples show how a conclusion can fail when a condition is missing:

⚠️ COMMON ERROR #01

Forgetting Codomain Restrictions in Surjectivity

Common Pitfall: Assuming a function given as $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2$ is surjective because its range is non-negative real numbers.

Counterexample: $f: \mathbb{R} \to \mathbb{R}, f(x) = x^2$

Why it fails: Negative reals in the codomain have no pre-image; hence range $\neq$ codomain.

🛡️ Exam Defense: Always verify Range $\subseteq$ Codomain equality before declaring surjectivity.

⚠️ COMMON ERROR #02

Applying Polynomial Injectivity Tests Incorrectly

Common Pitfall: Assuming even-degree polynomials are injective over $\mathbb{R}$ because they are continuous.

Counterexample: $f(x) = x^4 - 2x^2$

Why it fails: Fails the horizontal line test; multiple domain elements yield identical outputs.

🛡️ Exam Defense: Check derivative sign changes; if $f'(x) = 0$ has real roots in the domain, injectivity on $\mathbb{R}$ is broken.

Comparison

Concept / Theorem	Hypotheses / Assumptions	Key Formula / Outcome	Geometric Meaning	Exam Identification Clue
Injective Mapping	$f(a) = f(b) \implies a = b$	$x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$	Horizontal line intersects graph at most once	Strictly increasing/decreasing or algebraic uniqueness
Surjective Mapping	Range = Codomain	$\forall y \in B, \exists x \in A \text{ s.t. } f(x) = y$	Every horizontal line in codomain intersects graph	Codomain explicitly equals range
Bijective Mapping	Both Injective and Surjective	Invertible ($f^{-1}$ exists)	One-to-one correspondence, symmetric about $y=x$	Permutation or exact cardinality match
Constant Mapping	$f(x) = c$ for fixed $c$	Image set is singleton $\{c\}$	Horizontal straight line parallel to x-axis	Derivative identically zero

Solved examples

Each problem includes a full solution and a shorter method:

CANONICAL PROBLEM 01 Dual-Method Breakdown

Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = \frac{x}{x^2+1}$. Then $f(x)$ is:

(A) Injective only(B) Surjective only(C) Bijective(D) Neither injective nor surjective

📚 Method A: Formal Textbook Derivation

Step 1: Test injectivity: Let $f(x_1) = f(x_2) \implies x_1(x_2^2+1) = x_2(x_1^2+1) \implies (x_1-x_2)(1 - x_1 x_2) = 0$, which allows counterexamples like $f(2) = \frac{2}{5}$ and $f(1/2) = \frac{2}{5}$, so it is NOT injective. Step 2: Test surjectivity: Let $y = \frac{x}{x^2+1} \implies yx^2 - x + y = 0$. For real $x$, discriminant $\Delta = 1 - 4y^2 \ge 0 \implies y \in [-1/2, 1/2]$. Since range is $[-1/2, 1/2] \neq \mathbb{R}$, it is NOT surjective under codomain $\mathbb{R}$. Wait, standard textbook variant: if codomain is restricted, or re-evaluating standard PYQ where codomain is $[-1/2, 1/2]$, let's mark the precise standard option.

⚡ Method B: 25-Second Exam Shortcut

Check critical values: Maximum value is $1/2$ and minimum is $-1/2$ using calculus. Thus range is $[-1/2, 1/2]$.

💡 Tip: Always check whether the codomain matches the true calculated range.

CANONICAL PROBLEM 02 Dual-Method Breakdown

The number of bijective functions from a set $A$ containing 4 elements to itself is:

(A) $4$(B) $16$(C) $24$(D) $256$

📚 Method A: Formal Textbook Derivation

Step 1: Identify that for a finite set $A$ with $n$ elements, the number of bijective mappings from $A$ to $A$ is given by $n!$. Step 2: Substitute $n = 4$, yielding $4! = 24$.

⚡ Method B: 25-Second Exam Shortcut

Direct formula application: $n! = 4 \times 3 \times 2 \times 1 = 24$.

💡 Tip: Do not confuse with total mappings ($4^4 = 256$) or injective mappings.

Practice questions

Choose an answer to check it and see the solution:

MCQ 1: If $f: \mathbb{R} \to \mathbb{R}$ is defined by $f(x) = 3x + 5$, then $f$ is:

A Injective but not surjective

B Surjective but not injective

C Bijective

D Neither injective nor surjective

Derivation & Analysis:

Linear functions with non-zero slope ($f'(x) = 3 \neq 0$) are strictly monotonic, hence injective and surjective onto $\mathbb{R}$. Thus, $f$ is bijective.

MCQ 2: Let $A = \{1, 2, 3\}$ and $B = \{4, 5\}$. The number of functions from $A$ to $B$ is:

A 6

B 8

C 9

D 32

Derivation & Analysis:

Total functions = $|B|^{|A|} = 2^3 = 8$.

MCQ 3: If $f: \mathbb{N} \to \mathbb{N}$ is defined by $f(n) = n + 1$, then $f$ is:

A Injective and surjective

B Injective but not surjective

C Surjective but not injective

D Neither injective nor surjective

Derivation & Analysis:

$f(n_1) = f(n_2) \implies n_1 = n_2$ (Injective). But $1 \in \mathbb{N}$ has no pre-image since $n+1 = 1 \implies n = 0 \notin \mathbb{N}$ (Not Surjective).

MCQ 4: The number of one-to-one functions from a set containing 3 elements to a set containing 5 elements is:

A 15

B 60

C 125

D 243

Derivation & Analysis:

Number of injective mappings = $5P_3 = \frac{5!}{2!} = 60$.

MCQ 5: Let $f: \mathbb{R} \to \mathbb{R}$ be given by $f(x) = x^3$. Then $f$ is:

A One-to-one and onto

B One-to-one but not onto

C Onto but not one-to-one

D Neither one-to-one nor onto

Derivation & Analysis:

$f'(x) = 3x^2 \ge 0$ (strictly increasing, hence one-to-one) and cubic polynomials have range $\mathbb{R}$ (onto).

MCQ 6: If $f(x) = \frac{2x+1}{x-2}$, then the inverse function $f^{-1}(x)$ is:

A $\frac{2x+1}{x-2}$

B $\frac{2x-1}{x-2}$

C $\frac{2x+1}{x+2}$

D $\frac{x+2}{x-2}$

Derivation & Analysis:

Set $y = \frac{2x+1}{x-2} \implies y(x-2) = 2x+1 \implies xy - 2y = 2x+1 \implies x(y-2) = 2y+1 \implies x = \frac{2y+1}{y-2}$. Thus $f^{-1}(x) = \frac{2x+1}{x-2}$. Note that $f$ is self-inverse.

MCQ 7: Which of the following functions from $\mathbb{R}$ to $\mathbb{R}$ is invertible?

A $f(x) = x^2$

B $f(x) = \sin x$

C $f(x) = x^3 + 2$

D f(x) = |x|

Derivation & Analysis:

Only $f(x) = x^3 + 2$ is strictly monotonic and bijective on $\mathbb{R}$. The others fail injectivity.

MCQ 8: Let $f: \{1, 2, 3\} \to \{1, 2, 3\}$ be such that $f(1)=2, f(2)=3, f(3)=1$. Then $f^{-1}(2)$ is equal to:

A 1

B 2

C 3

D Does not exist

Derivation & Analysis:

Since $f(1) = 2$, by definition of inverse mapping, $f^{-1}(2) = 1$.

MCQ 9: If $f(x) = \log_e x$ for $x > 0$, then $f$ is:

A Not injective

B Bijective from $(0, \infty)$ to $\mathbb{R}$

C Surjective to $\mathbb{R}$ but not injective

D Bounded

Derivation & Analysis:

The natural logarithm is strictly increasing ($f'(x) = 1/x > 0$) and its range covers all of $\mathbb{R}$, making it bijective.

Q10

MCQ 10: Let $f: A \to B$ and $g: B \to C$ be two bijections. Then the composite mapping $(g \circ f): A \to C$ is:

A Not injective

B Not surjective

C Bijective

D Constant

Derivation & Analysis:

The composition of two bijective mappings is always bijective, with inverse $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

Common questions

No. A bijection between two finite sets requires them to have an identical cardinality ($|A| = |B|$).

Failing to check whether the given codomain matches the actual calculated range of the function when determining surjectivity.

Use the swap-and-solve method ($x$ becomes $y$ and $y$ becomes $x$), or test options by substituting numerical values.