Let A and B be two sets each with a finite number of elements. Assume that there is an injective map

Q: Wait, why do we need to prove $n=m$? Isn't it obvious?

In mathematics, especially in JEE Advanced, 'obvious' is a dangerous word. We must bridge the gap between intuition and formal logic. While it feels intuitive, we must formally demonstrate that the existence of these two injections forces the cardinalities to be identical, which is the bedrock of the proof.

Q: Does this logic hold if the sets are infinite?

That is a brilliant question! For finite sets, yes, the logic is straightforward. However, if sets are infinite, this becomes the famous Cantor-Bernstein-Schröder Theorem. The proof for infinite sets is much more complex and requires set-theoretic construction, but for your JEE syllabus, focusing on the finite case is perfect.

Q: Why does injection imply surjection for finite sets?

Think of it as a seating arrangement. If you have $n$ chairs and $n$ people, and everyone sits in a unique chair (injection), can any chair be left empty? No! Because there are exactly as many people as chairs, every chair must be occupied. Thus, the mapping is surjective.

Question

Let $A$ and $B$ be two sets each with a finite number of elements. Assume that there is an injective mapping from $A$ to $B$ and that there is an injective mapping from $B$ to $A$. Prove that there is a bijective mapping from $A$ to $B$.

Sigma Percentile · Accepted Answer

### Analyzing the Setup

Let us begin by visualizing our sets. Imagine $A$ and $B$ as two separate containers holding a finite number of distinct objects.

This finiteness is our anchor, allowing us to count the elements. Let the number of elements in set $A$ be $n$, and the number of elements in set $B$ be $m$.

Mathematically, we define this as:
$$|A| = n, \quad |B| = m$$

### The Logic of Injection

The problem provides a powerful tool: an injective mapping $f: A 	o B$. An injective, or one-to-one, function ensures that every element in $A$ maps to a unique, distinct partner in $B$.

No two elements in $A$ can share the same partner. If every element in $A$ demands its own unique space in $B$, then $B$ must have at least as much "room" as $A$.

If $A$ had more elements than $B$, we would inevitably run out of unique partners in $B$. Therefore, we must conclude:
$$n \leq m$$

### The Squeeze

The problem also provides a second, equally powerful condition: an injective mapping $g: B 	o A$. We apply the exact same logic in reverse.

If every element in $B$ maps to a unique partner in $A$, then $A$ must have enough elements to accommodate all of $B$. This implies that the size of $B$ cannot exceed the size of $A$:
$$m \leq n$$

We now have two profound inequalities: $n \leq m$ and $m \leq n$. Since $n$ and $m$ are integers representing counts of objects, the only mathematical possibility that satisfies both conditions simultaneously is:
$$n = m$$

### The Grand Finale

We have established that $|A| = |B|$. In the realm of finite sets, this is a significant realization.

When two finite sets have the exact same number of elements, any injective mapping between them is automatically surjective. Because every element in $A$ maps to a unique element in $B$, and there are no elements left over in $B$, every element in $B$ must be covered.

A function that is both injective and surjective is, by definition, a **bijection**. We have proven that a bijective mapping exists, confirming the **Schröder-Bernstein theorem for finite sets**.

Animated Solution for Mathematics - Functions: Let $A$ and $B$ be two sets each with a finite number of elements. Assume that there is an injective mapping from $A$ to $B$ and that there is an injective mapping from $B$ to $A$ . Prove that there is a bijective mapping from $A$ to $B$ .

Visualized Solution

Defining Sets $A$ and $B$

Elements of the Sets

Assigning Cardinality

First Condition: Injective Mapping $A \to B$

Implication of Injection $A \to B$

Second Condition: Injective Mapping $B \to A$

Implication of Injection $B \to A$

Combining the Inequalities

Equal Cardinality

Bijection for Finite Sets

Conclusion

The Sigma Insight: Classification of Functions

Analyzing the Setup

The Logic of Injection

The Squeeze

The Grand Finale

Similar Questions

Let $A = {0, 1, 2, 3, 4, 5, 6, 7}$ . Then the number of bijective functions $f : A \to A$ such that $f (1) + f (2) = 3 - f (3)$ is equal to

Consider two sets $A = {x \in Z : ∣ (∣ x - 3∣ - 3) ∣ \leq 1}$ and $B = {x \in R - {1, 2} : \frac{( x - 2 ) ( x - 4 )}{x - 1} lo g_{e} (∣ x - 2∣) = 0}$ . Then the number of onto functions $f : A \to B$ is equal to

Let $A$ be a set of $n$ distinct elements. Then the total number of distinct functions from $A$ to $A$ is ......... and out of these ......... are onto functions.

Let a function $f : N \to N$ be defined by $f (n) = ⎩ ⎨ ⎧ 2 n, n - 1, \frac{n + 1}{2}, n = 2, 4, 6, 8, \dots n = 3, 7, 11, 15, \dots n = 1, 5, 9, 13, \dots$ then, $f$ is

Let $A = {x \in R : x is not a positive integer}$ . Define a function $f : A \to R$ as $f (x) = \frac{2 x}{x - 1}$ then $f$ is

Let $A = {a, b, c}$ and $B = {1, 2, 3, 4}$ . Then the number of elements in the set $C = {f : A \to B ∣2 \in f (A) and f is not one-one}$ is

If the functions $f (x)$ and $g (x)$ are defined on $R \to R$ such that $f (x) = {0, x, x \in rational x \in irrational$ ; $g (x) = {0, x, x \in irrational x \in rational$ then $(f - g) (x)$ is

A function $f$ from the set of natural numbers to integers defined by $f (n) = {\frac{n - 1}{2}, - \frac{n}{2}, when n is odd when n is even$ is

Let $E = {1, 2, 3, 4}$ and $F = {1, 2}$ . Then the number of onto functions from $E$ to $F$ is

Let $f (x) = {- a x + a if - a \leq x \leq 0 if 0 < x \leq a$ where $a > 0$ and $g (x) = (f (∣ x ∣) - ∣ f (x) ∣) /2$ . Then the function $g : [- a, a] \to [- a, a]$ is

Visualized Solution

Defining Sets .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } A and .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } B

Elements of the Sets

Assigning Cardinality

First Condition: Injective Mapping .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } A→B

Implication of Injection .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } A→B

Second Condition: Injective Mapping .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } B→A

Implication of Injection .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } B→A