Q.Show that a one-one function $f: \{1, 2, 3\} \to \{1, 2, 3\}$ must be onto.

Concept: Pigeonhole Principle – if you put $n$ items into $n$ boxes with no two items in the same box, every box must be used.

Reasoning:

1. Domain $\{1,2,3\}$ has 3 elements; codomain $\{1,2,3\}$ also has 3 elements.
2. Since $f$ is one-one, each of the 3 domain elements maps to a distinct element in the codomain. …

The key idea here is that when you have a function from a finite set to itself, injectivity (one-one) and surjectivity (onto) become equivalent. This is not true for infinite sets, but for finite sets, it’s a direct consequence of counting.

Let’s see why.

---

1. Understand what’s given

We have $f: \{1,2,3\} \to \{1,2,3\}$, and $f$ is one-one (injective). That means:

• Different inputs give different outputs.
• So $f(1), f(2), f(3)$ are three distinct elements from the set $\{1,2,3\}$.

The codomain has exactly three elements: 1, 2, and 3.

2. Apply the Pigeonhole Principle in reverse

The Pigeonhole Principle usually says: if you put more pigeons than holes, some hole gets at least two pigeons. Here, we have the opposite situation — we have exactly as many pigeons as holes (3 inputs, 3 possible outputs), and the function is one-one, so no two pigeons share a hole.

3. Conclude surjectivity

If each of the three boxes (1, 2, 3) gets exactly one ball, then every box is occupied. That means every element of the codomain $\{1,2,3\}$ appears as $f(x)$ for some $x$ in the domain. So $f$ is onto (surjective). …

Method: One-one implies onto for a finite set mapped to itself

Use this when the domain and codomain are the same finite set (or equal-sized finite sets) and injectivity is given.

Steps

Step 1: Record equal finite sizes

Write $|A|=|B|=n$. The finiteness and the equal sizes are essential — the result is false for infinite sets.

Step 2: Use one-one to count the image

Injectivity sends the $n$ distinct inputs to $n$ distinct outputs, so the image $f(A)$ has exactly $n$ elements. …

Common Mistakes

Mistake 1: Believing one-one always implies onto

Why it's wrong: it holds only for finite sets of equal size; $f(n)=n+1$ on $\mathbb{N}$ is one-one but not onto ($1$ is never reached). Correct approach: rely on the finiteness and equal size of $\{1,2,3\}$.

Mistake 2: Not connecting image size to the whole set …