Prove Existence of Bijection from Injective Maps

📝 Question

Let \(A\) and \(B\) be two finite sets. Suppose there exists:

\[ f:A\to B \quad \text{(injective)} \]

\[ g:B\to A \quad \text{(injective)} \]

Prove that there exists a bijection from \(A\) to \(B\).

---

✅ Solution

🔹 Step 1: Use injectivity to compare sizes

Since \(f:A\to B\) is injective, no two elements of \(A\) map to the same element of \(B\).

Therefore,

\[ |A|\le |B| \]

Similarly, since \(g:B\to A\) is injective,

\[ |B|\le |A| \] —

🔹 Step 2: Conclude equality of cardinalities

From above:

\[ |A|\le |B| \quad \text{and} \quad |B|\le |A| \]

Hence,

\[ |A|=|B| \] —

🔹 Step 3: Conclude existence of bijection

If two finite sets have the same number of elements, then there exists a bijection between them.

Hence, there exists a bijective function:

\[ h:A\to B \] —

🔹 Theoretical Insight

This result is a special case of the Cantor–Schröder–Bernstein Theorem, which states:

If there exist injective functions \(f:A\to B\) and \(g:B\to A\), then there exists a bijection between \(A\) and \(B\).

This holds even for infinite sets. :contentReference[oaicite:0]{index=0}

—

🎯 Final Answer

\[ \boxed{\text{There exists a bijection from } A \text{ to } B} \] —

🚀 Exam Shortcut

• Injection \(A\to B\) ⇒ \(|A|\le |B|\)
• Injection \(B\to A\) ⇒ \(|B|\le |A|\)
• Combine ⇒ \(|A|=|B|\)
• Equal finite sets ⇒ bijection exists