Exercise 1.2 · Q6: A function from {1, 2, 3} to {4, 5, 6, 7}

Basics you need

Solution

1. Read off the function and check it is a function from $A$ to $B$

   Each ordered pair $(a, b)$ in $f$ says $f(a) = b$⁠:

   $$f(1) = 4, \qquad f(2) = 5, \qquad f(3) = 6.$$

   Each element of $A = \{1,2,3\}$ appears as a first entry exactly once, and every second entry $4, 5, 6$ belongs to $B = \{4,5,6,7\}$⁠. So $f$ really is a function from $A$ to $B$⁠, as the question says.

   Before testing a property of a function, make sure you are reading it correctly. The first entry of each pair is the input and the second is the output. Checking that every input occurs exactly once confirms that $f$ gives each element of $A$ one and only one image; checking that the outputs lie in $B$ confirms that $B$ is a legitimate codomain.
   A function is a set of ordered pairs in which each element of the domain is a first entry exactly once (Basic 1). Basics: what a function is

2. Compare the images of every pair of distinct inputs

   There are only three pairs of different inputs (Basic 4). We check all of them:

   Inputs $x_1 \ne x_2$	Images	Different?
   $1,\ 2$	$f(1) = 4,\ f(2) = 5$	$4 \ne 5$ ✓
   $1,\ 3$	$f(1) = 4,\ f(3) = 6$	$4 \ne 6$ ✓
   $2,\ 3$	$f(2) = 5,\ f(3) = 6$	$5 \ne 6$ ✓

   In every case, distinct inputs have distinct images.

   Definition 5 is a "for all" statement: every pair of distinct inputs must have distinct images. On an infinite domain we would need an algebraic argument. Here the domain is finite and tiny, so we can do something even more convincing: check every single pair. Because the list of pairs is complete, the check is a full proof, not just evidence.
   One-one: distinct elements of the domain have distinct images (Definition 5). Checking all cases of a finite list proves a "for all" statement about that list. Basics: proving and disproving

3. Conclude

   The three images $4, 5, 6$ are pairwise different, so no two elements of $A$ share an image. Hence $f$ is one-one.

   A quick way to say the same thing: $A$ has 3 elements, and the set of images $\{4, 5, 6\}$ also has 3 elements. If two inputs had shared an image, there would be fewer than 3 distinct images.

   The counting argument is a useful shortcut for finite sets: a function on a finite set is one-one exactly when the number of distinct images equals the number of elements in the domain. Both arguments say the same thing; the table makes every comparison visible.

4. A side remark: $f$ is not onto, and that is fine

   The element $7\in B$ is not a second entry of any pair in $f$⁠, so no element of $A$ maps to 7. So $f$ is not onto, and therefore not bijective. The question only asks us to show one-one, and that is what we have proved.

   In fact no function from $A$ to $B$ can be onto: three inputs can produce at most three distinct images, but $B$ has four elements.

   This remark guards against a common confusion. "One-one" is about inputs not colliding; "onto" is about outputs not being missed. They are independent properties, and here one holds while the other fails. The textbook's Examples 13 and 14 show that for a function from a finite set to itself the two come together, but $A$ and $B$ here are different sets of different sizes, so that result does not apply.
   Onto: every element of the codomain is the image of some element of the domain (Definition 6). Basics: one-one and onto

Every fact used, and where it comes from