Example 14: One-one on {1, 2, 3} forces onto

Basics you need

Solution

1. One-one makes the three images different

   The inputs $1, 2, 3$ are pairwise distinct: $1 \ne 2$⁠, $1 \ne 3$⁠, $2 \ne 3$⁠. Since $f$ is one-one, distinct inputs have distinct images, so

   $$\begin{gathered} f(1) \ne f(2), \quad f(1) \ne f(3), \\ f(2) \ne f(3). \end{gathered}$$

   So $f(1), f(2), f(3)$ are three different elements of the codomain.

   We use one-one in its "distinct inputs give distinct images" form, which is how Definition 5 first states it. Applying it to each of the three pairs of inputs gives all three inequalities. Nothing about which one-one function $f$ is was used, so this holds for every one-one $f$ on $\{1, 2, 3\}$⁠.
   The contrapositive of "$f(x_1) = f(x_2) \Rightarrow x_1 = x_2$" is "$x_1 \ne x_2 \Rightarrow f(x_1) \ne f(x_2)$". A statement and its contrapositive are always equivalent. Basics: proving and disproving

2. Three different elements of $\{1, 2, 3\}$ are all of it

   Let $S = \{f(1), f(2), f(3)\}$⁠, the range of $f$⁠. Every image lies in the codomain, so $S \subseteq \{1, 2, 3\}$⁠. By Step 1, $S$ has exactly three elements.

   Suppose some $k \in \{1, 2, 3\}$ were missing from $S$⁠. Then $S$ would be contained in $\{1, 2, 3\}$ with $k$ removed, a set of only two elements, so $S$ would have at most two elements. That contradicts $S$ having three. So no element is missing:

   $$\{f(1),\ f(2),\ f(3)\} = \{1, 2, 3\}.$$
   This is the textbook's sentence "three elements of $\{1, 2, 3\}$ must be taken to 3 different elements of the co-domain", with the final counting step written out. The intuition is seating three people on three chairs with no two sharing a chair: no chair can be left empty.
   A subset of a finite set with the same number of elements as the set is the whole set. This is the step that fails for infinite sets (see Step 4).

3. Conclude: $f$ is onto

   Step 2 says the range of $f$ is the whole codomain $\{1, 2, 3\}$⁠. Equivalently, every $y \in \{1, 2, 3\}$ equals $f(x)$ for some $x \in \{1, 2, 3\}$⁠. So $f$ is onto.

   By the Remark after Definition 6, onto means range = codomain, which is exactly what Step 2 established. Since $f$ was an arbitrary one-one function, every one-one $f : \{1, 2, 3\} \to \{1, 2, 3\}$ is onto. Combined with Example 13, such a function is one-one if and only if it is onto, and in that case it is bijective.
   $f : X \to Y$ is onto if and only if Range of $f$ = $Y$⁠.

4. Confirm by listing all one-one functions, and compare with $\N$

   A one-one $f$ has 3 choices for $f(1)$⁠, then 2 for $f(2)$ (it must differ from $f(1)$⁠), then 1 for $f(3)$⁠: $3 \times 2 \times 1 = 6$ functions. All six are drawn below, and in each one every output receives exactly one arrow, so each is onto.

   For an infinite set the conclusion can fail. In Example 8, $f(x) = 2x$ from $\N$ to $\N$ is one-one, yet the range $\{2, 4, 6, \dots\}$ misses every odd number. Step 2 has no analogue there: a subset of $\N$ can be "as large as" $\N$ (infinite) without being all of $\N$⁠.

   Listing all six functions confirms the proof completely for this small set. The comparison with $\N$ is the point of the textbook's Remark after this example: for every finite set $X$⁠, a function $X \to X$ is one-one exactly when it is onto, and this "characteristic difference between a finite and an infinite set" is why Examples 8 and 10 exist.
   For a finite set $X$ with $n$ elements, a one-one $f : X \to X$ has $n$ different images in an $n$-element set, so by the same counting it is onto. Basics: counting choices

Every fact used, and where it comes from