Example 7: Roll numbers: one-one but not onto

Basics you need

Solution

1. $f$ really is a function from A to $\N$

   Each student of the class is given exactly one roll number, and roll numbers are natural numbers. So every $x\in A$ is assigned exactly one value $f(x)\in\N$⁠, which is what a function $A\to\N$ requires.

   Before asking whether $f$ is one-one or onto, it is worth confirming that $f$ is a function. Here that is a fact about how schools work: no student is left without a roll number, and no student has two.
   A function assigns exactly one output to each input (Basic 1).

2. One-one: different students have different roll numbers

   Take any two students $x_1, x_2 \in A$ with $x_1 \ne x_2$⁠. A roll number is issued to identify one student, so no two different students of the class share a roll number. Hence

   $$x_1 \ne x_2 \;\Rightarrow\; f(x_1) \ne f(x_2).$$

   Equivalently, if $f(x_1) = f(x_2)$⁠, the two students have the same roll number, so they are the same student: $x_1 = x_2$⁠. Therefore $f$ is one-one.

   One-one is a claim about every pair of different inputs, so we take an arbitrary pair $x_1 \ne x_2$⁠. The mathematical content is just Definition 5; the fact that makes it true comes from the situation described (the purpose of a roll number is to tell students apart). The contrapositive form "$f(x_1)=f(x_2) \Rightarrow x_1=x_2$" is the form the textbook writes after "i.e." in Definition 5, so we show that both forms give the same conclusion.
   "$x_1\ne x_2 \Rightarrow f(x_1)\ne f(x_2)$" and "$f(x_1)=f(x_2) \Rightarrow x_1=x_2$" say the same thing (one is the contrapositive of the other). Basics: how to prove and disprove

3. Not onto: 51 is nobody's roll number

   As the textbook says, we may assume the roll numbers are $1, 2, \dots, 50$ (see Step 4 for why this assumption costs nothing). Then the range of $f$ is

   $$\text{range of } f = \{f(x) : x\in A\} = \{1, 2, 3, \dots, 50\}.$$

   The natural number $51$ is in the codomain $\N$ but not in this set: no student has roll number 51, so there is no $x\in A$ with $f(x) = 51$⁠. Hence $f$ is not onto. (So are $52, 53, \dots$⁠; one is enough.)

   "Onto" is a "for every $y$ in the codomain" claim, so to deny it we need one $y$ that is missed. The textbook's solution writes "image of any element of X under $f$"; the domain in this example is called A, so read X as A there (it is a slip in the book's wording, not a change in the mathematics).
   Remark after Definition 6: $f : X\to Y$ is onto if and only if range of $f$ = Y. Here range $= \{1,\dots,50\} \ne \N$⁠.

4. Why "without loss of generality" is safe

   Suppose the school used any other 50 different natural numbers as roll numbers, say $r_1 < r_2 < \dots < r_{50}$⁠. Then the range of $f$ is $\{r_1, \dots, r_{50}\}$⁠, and the natural number $r_{50} + 1$ is larger than every roll number, so it is not a roll number at all. Again some element of $\N$ is not an image, and $f$ is not onto.

   More simply: a set of 50 students has at most 50 images, and $\N$ is infinite, so the range can never be all of $\N$⁠.

   The phrase "without loss of generality" means "the special case we pick does not affect the conclusion". This step shows why: the argument does not depend on which 50 numbers are used. Only the particular missing number (51, or $r_{50}+1$⁠) changes.
   A function defined on a set of $n$ elements has at most $n$ different outputs (Basic 4). Every finite set of natural numbers has a largest element, and one more than it is a natural number not in the set.

5. Conclude

   $f$ is one-one (Step 2) and not onto (Steps 3 and 4). So $f$ is one-one but not onto, and in particular it is not bijective (Definition 7).

   One-one and onto are separate properties. Here the first holds and the second fails, purely because the codomain $\N$ is much larger than the domain. If we shrank the codomain to $B = \{1,\dots,50\}$⁠, the same rule would be a bijection $A\to B$⁠: the properties depend on the codomain, not just on the rule.
   Bijective means one-one and onto (Definition 7). Lesson: types of functions

Every fact used, and where it comes from