Chapter 1 · Relations and Functions

Example 13: Onto on {1, 2, 3} forces one-one

ExamplesTypes of functions · Section 1.3

The question

Show that an onto function $f : \{1, 2, 3\} \to \{1, 2, 3\}$ is always one-one.

Exam answer

Since $f$ is onto, its range is the whole codomain:

\{f(1), f(2), f(3)\} = \{1, 2, 3\}

Suppose $f$ is not one-one. Then two different elements $a, b$ of $\{1, 2, 3\}$ have $f(a) = f(b)$ ⁠. So the range $\{f(1), f(2), f(3)\}$ has at most two elements, and $f$ is not onto. This is a contradiction.

Hence $f$ is one-one.

Want the reason behind every step, the basics and the checks?

The one idea this problem is built on

Count the outputs. Three inputs can produce at most three different outputs. To be onto, $f$ must produce all three elements of the codomain, so it needs three different outputs, and therefore no two inputs may share one. If two inputs did share an output, only two values would be left at most, and one element of the codomain would be missed. The proof is this counting argument, written as a proof by contradiction.

Given, to show, and the plan

Given: A function $f$ from $\{1, 2, 3\}$ to $\{1, 2, 3\}$ that is onto: each of 1, 2, 3 is $f$ of something.
To show: $f$ is one-one: different inputs have different images.
Plan: (1) Note that the range is $\{f(1), f(2), f(3)\}$ ⁠, so it has at most three elements. (2) Suppose, for contradiction, that $f$ is not one-one. (3) Show the range then has at most two elements. (4) That contradicts onto, so $f$ must be one-one. (5) Confirm by listing all 27 functions.

Basics you need

1Range of a function on a finite set

For $f$ on $\{1, 2, 3\}$ ⁠, the range is the set of images $\{f(1), f(2), f(3)\}$ ⁠. Repeated values are listed once, so this set has 3, 2 or 1 elements. Basics: what a function is

2Onto means range = codomain

$f : X \to Y$ is onto exactly when its range is all of $Y$ (Remark after Definition 6). Here that means $\{f(1), f(2), f(3)\} = \{1, 2, 3\}$ ⁠. Basics: one-one and onto

3Not one-one

$f$ is not one-one exactly when there are two different inputs $a \ne b$ with $f(a) = f(b)$ ⁠.

4Proof by contradiction

To prove a statement, assume it is false and deduce something impossible. Then the assumption must be wrong, so the statement is true. Basics: proving and disproving

5Counting functions

A function from a 3-element set to a 3-element set chooses one of 3 images for each of 3 inputs, so there are $3 \times 3 \times 3 = 27$ such functions. Basics: counting choices

Solution

What onto means here

The domain has only three elements, so $f$ is completely described by the three values $f(1), f(2), f(3)$ ⁠, and
$\text{Range of } f = \{f(1),\ f(2),\ f(3)\}.$
Since $f$ is onto, this range must equal the whole codomain:
$\{f(1),\ f(2),\ f(3)\} = \{1, 2, 3\}.$
In particular the range must contain three different elements.

Translating "onto" into a statement about the set of images turns the question into counting: how many different values can three inputs produce? A set written as $\{f(1), f(2), f(3)\}$ lists each value once, even if, say, $f(1) = f(2)$ ⁠, so its size is the number of different images.

$f$ is onto if and only if the range of $f$ equals the codomain (Remark after Definition 6, Section 1.3).
Assume the opposite: $f$ is not one-one

Suppose, for contradiction, that $f$ is not one-one. Then there are two different elements of the domain with the same image. Call them $a$ and $b$ ⁠, with $a \ne b$ and $f(a) = f(b)$ ⁠, and let $c$ be the third element of $\{1, 2, 3\}$ ⁠. (The book takes $a = 1$ ⁠, $b = 2$ ⁠, $c = 3$ as an illustration; the argument below does not depend on which pair it is.)

We want to prove "onto $\Rightarrow$ one-one". Proof by contradiction assumes "onto" (given) together with "not one-one" and looks for something impossible. Naming the pair $a, b$ instead of fixing $1, 2$ makes it clear that every possible pair is covered: there are three possible pairs ( $\{1,2\}, \{1,3\}, \{2,3\}$ ⁠), and the same reasoning works for each.

"Not one-one" is the negation of "for all $x_1, x_2$ ⁠: $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$ ". It says: there exist $x_1 \ne x_2$ with $f(x_1) = f(x_2)$ ⁠. Basics: proving and disproving
Then the range has at most two elements

The range is $\{f(a), f(b), f(c)\}$ ⁠. Because $f(a) = f(b)$ ⁠, the first two entries are the same element, so
$\text{Range of } f = \{f(a),\ f(c)\}.$
This set has at most two elements (exactly two if $f(c) \ne f(a)$ ⁠, one if $f(c) = f(a)$ ⁠). The image of $c$ can be only one element, so nothing else is added.

Left: when two inputs share an image (here $f(1) = f(2) = 1$ ⁠, $f(3) = 2$ ⁠), only two outputs are used and the codomain element 3 is missed. Right: an onto function ( $f(1) = 2$ ⁠, $f(2) = 3$ ⁠, $f(3) = 1$ ⁠) uses all three outputs, so each receives exactly one arrow.

This is the counting heart of the proof. Three arrows leave the domain, and two of them land on the same point, so at most two points of the codomain are hit. This is the textbook's sentence "the image of 3 under $f$ can be only one element", made general.

A function assigns exactly one image to each input, so $c$ contributes exactly one element to the range. Basics: what a function is
Contradiction, so $f$ is one-one

A set with at most two elements cannot equal $\{1, 2, 3\}$ ⁠, which has three. So at least one element of the codomain is not in the range, and $f$ is not onto. This contradicts the given fact that $f$ is onto. The assumption of Step 2 must therefore be false: $f$ is one-one.

The assumption "not one-one" led to "not onto", which is impossible because $f$ is onto. In a proof by contradiction, the only way out is to reject the assumption. Equivalently, we have shown the contrapositive: "not one-one $\Rightarrow$ not onto", which is logically the same as "onto $\Rightarrow$ one-one".

A statement $P \Rightarrow Q$ and its contrapositive $\text{not } Q \Rightarrow \text{not } P$ are always both true or both false.
Confirm by listing every function

There are only $3^3 = 27$ functions from $\{1, 2, 3\}$ to itself, so we can sort all of them by the size of their range:

Size of range Number of functions Onto? One-one?

3 6 yes yes

2 18 no no

1 3 no no

Total 27 6 onto 6 one-one

The 6 onto functions are exactly the 6 one-one functions (the six ways of arranging 1, 2, 3, counted $3 \times 2 \times 1 = 6$ ⁠). Every one of the other 21 functions repeats a value and misses an element. This agrees with the proof.

A finite set allows a complete check, which is a good habit when it is small. It does not replace the proof, because the proof explains why it must be so, and the same argument extends to any finite set, while a list does not.

Range sizes: 3 functions are constant (range size 1); $3 \cdot 2 \cdot 1 = 6$ use all three values; the remaining $27 - 3 - 6 = 18$ use exactly two. Basics: counting choices

Size of range	Number of functions	Onto?	One-one?
3	6	yes	yes
2	18	no	no
1	3	no	no
Total	27	6 onto	6 one-one

Result

If an onto $f : \{1, 2, 3\} \to \{1, 2, 3\}$ were not one-one, two inputs would share an image and the range $\{f(1), f(2), f(3)\}$ would have at most two elements, so $f$ would not be onto, a contradiction. Hence every onto function from $\{1, 2, 3\}$ to itself is one-one. (By the Remark after Example 14, the same holds for every finite set $X$ and $f : X \to X$ ⁠.)

Check it with numbers

Brute force over all 27 functions (Step 5): exactly 6 are onto, and all 6 are one-one. Try a specific non-one-one function: $f(1) = 3,\ f(2) = 1,\ f(3) = 3$ ⁠. Its range is $\{3, 1\}$ ⁠, which misses 2, so it is not onto, just as Step 3 predicts.

Common mistakes

Checking a single example. Showing one onto function is one-one proves nothing about the others. The argument must work for every onto $f$ ⁠, which is why we use arbitrary $a, b, c$ ⁠.
Fixing the pair as 1 and 2 without comment. The shared pair could be $\{1, 3\}$ or $\{2, 3\}$ ⁠. Either say "say 1 and 2, the other cases are identical" (as the book does) or use letters.
Extending the result to infinite sets. It is false there: Example 10 gives an onto function $\N \to \N$ that is not one-one.
Confusing domain and codomain sizes. The argument uses that both have three elements. For $f : \{1, 2, 3\} \to \{1, 2\}$ ⁠, onto functions exist and none of them is one-one.

What to take away

For functions between finite sets, think in terms of counting: $n$ inputs produce at most $n$ different outputs, and fewer if any two collide.
Proof by contradiction (or the contrapositive) is natural here: "not one-one" quickly gives "not onto".
For a finite set $X$ and $f : X \to X$ ⁠, onto $\iff$ one-one. Example 14 proves the other direction. For infinite sets both directions can fail: Example 8 is one-one but not onto, and Example 10 is onto but not one-one.

Every fact used, and where it comes from

Fact	Used in	Source
Definition of one-one, and its negation	Steps 2, 4	Definition 5, Section 1.3 (Lesson: types of functions)
Onto $\iff$ range = codomain	Steps 1, 4	Definition 6 and the Remark after it, Section 1.3
Each input has exactly one image	Step 3	Definition of a function
Proof by contradiction; contrapositive	Steps 2, 4	Logic
27 functions: 6 with range size 3, 18 with size 2, 3 with size 1	Step 5	Multiplication principle (Lesson: counting functions and relations)
Same result for any finite set $X$	Result	Remark after Example 14, Section 1.3

Found an error, or want more?

Tell us if something on this page is wrong or unclear, or if you would like a fuller explanation, another method or a new feature. Send feedback on this problem →

Example 13: Onto on {1, 2, 3} forces one-one

Basics you need

Solution

What onto means here

Assume the opposite: fff is not one-one

Then the range has at most two elements

Contradiction, so fff is one-one

Confirm by listing every function

Every fact used, and where it comes from

Assume the opposite: $f$ is not one-one

Contradiction, so $f$ is one-one