Example 10: Onto but not one-one on $\N$

Basics you need

Solution

1. Check that $f$ is a well-defined function $\N \to \N$

   Every natural number is either 1, or 2, or greater than 2, and exactly one of these holds. So exactly one rule applies to each input. The outputs lie in $\N$⁠: $f(1) = f(2) = 1 \in \N$⁠, and if $x > 2$ then $x \ge 3$⁠, so $x - 1 \ge 2$ is a natural number. A few values:

   $x$	1	2	3	4	5	6	7
   rule used	$f(1)=1$	$f(2)=1$	$3-1$	$4-1$	$5-1$	$6-1$	$7-1$
   $f(x)$	1	1	2	3	4	5	6

   The two special values $f(1)$ and $f(2)$ are there for a reason: the rule $x - 1$ cannot be used at $x = 1$⁠, because $1 - 1 = 0 \notin \N$⁠. Checking that each piece stays inside $\N$ shows the definition makes sense. The table and diagram then suggest the answer before we prove it.
   In this book $\N = \{1, 2, 3, \dots\}$ does not contain 0. That is exactly why $f(1)$ needs its own definition.

2. Not one-one: 1 and 2 share an image

   From the definition, $f(1) = 1$ and $f(2) = 1$⁠. So

   $$f(1) = f(2) \qquad\text{but}\qquad 1 \ne 2.$$

   Two different inputs have the same image, so $f$ is not one-one.

   One-one claims that for every pair $x_1, x_2$⁠, equal images force equal inputs. A single pair that violates this is a complete disproof, so no general argument is needed. Here the pair is handed to us by the definition itself.
   "Many-one" is the book's name for a function that is not one-one (Definition 5). This $f$ is many-one.

3. Onto, case $y \ne 1$⁠: use the input $y + 1$

   Take an arbitrary $y \in \N$ with $y \ne 1$⁠, so $y \ge 2$⁠. We want $x$ with $f(x) = y$⁠. Only the piece $x - 1$ produces values $\ge 2$⁠, so solve $x - 1 = y$⁠, giving the candidate $x = y + 1$⁠. Check it:

   • $y + 1 \in \N$⁠, and $y + 1 \ge 3 > 2$⁠, so the piece $f(x) = x - 1$ is the one that applies to it.
   • $f(y + 1) = (y + 1) - 1 = y$⁠. ✓

   So every $y \ge 2$ is an image.

   The check "$y + 1 > 2$" is essential and easy to skip. The formula $x - 1$ is only valid for $x > 2$⁠, so before using it on $y+1$ we must confirm that $y + 1$ is in that piece. It is, because $y \ge 2$⁠. (The book chooses $x = y + 1$ and checks $f(y+1) = y + 1 - 1 = y$⁠.)
   With a piecewise function, the candidate preimage must fall in the piece whose formula you used to find it.

4. Onto, case $y = 1$⁠: use the input 1

   The remaining element of the codomain is $y = 1$⁠. The recipe of Step 3 would give $x = 2$⁠, but 2 is not in the piece $x > 2$⁠, so we cannot use that formula. Instead, the definition gives directly

   $$f(1) = 1.$$

   (So does $f(2) = 1$⁠.) Hence 1 is also an image. Every $y \in \N$ is either 1 or at least 2, and both cases are done, so $f$ is onto.

   The two cases $y = 1$ and $y \ge 2$ together cover all of $\N$⁠, so proving each one proves onto for every $y$⁠. The value 1 needs separate treatment for the same reason $f(1)$ and $f(2)$ needed separate definitions: the general formula does not reach it.
   Proof by cases: split the possibilities into cases that cover everything, then prove each. Basics: proving and disproving

5. Conclude, and compare with Examples 8, 13 and 14

   $f$ is onto (Steps 3 and 4) and not one-one (Step 2). So $f$ is onto but not one-one.

   For a function from a finite set to itself this could never happen: Example 13 shows that onto forces one-one on $\{1, 2, 3\}$⁠. The textbook's Remark after Example 14 points to this example and Example 8 as proof that on an infinite set like $\N$⁠, onto and one-one can come apart.

   Why the infinite set allows it: $f$ "wastes" one input by sending both 1 and 2 to 1, yet still has infinitely many inputs left to cover the infinitely many outputs $2, 3, 4, \dots$ A finite set has no such spare supply.

Every fact used, and where it comes from