Chapter 1 · Relations and Functions

Example 8: $f(x)=2x$ on $\N$ ⁠: one-one but not onto

ExamplesTypes of functions · Section 1.3

The question

Show that the function $f : \N \to \N$ ⁠, given by $f(x) = 2x$ ⁠, is one-one but not onto.

Exam answer

One-one: Let $x_1, x_2 \in \N$ with $f(x_1) = f(x_2)$ ⁠. Then

\begin{aligned} f(x_1) = f(x_2) &\Rightarrow 2x_1 = 2x_2 \\ &\Rightarrow x_1 = x_2 \end{aligned}

Thus $f$ is one-one.

Not onto: Take $1 \in \N$ ⁠. If $f(x) = 1$ ⁠, then $2x = 1$ ⁠, so $x = \frac12 \notin \N$ ⁠. So 1 has no pre-image in $\N$ ⁠. Thus $f$ is not onto.

Hence $f$ is one-one but not onto.

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

The one idea this problem is built on

Doubling never sends two different numbers to the same place, because we can always undo it by halving: if $2x_1 = 2x_2$ ⁠, halve both sides and $x_1 = x_2$ ⁠. So $f$ is one-one. But the outputs of doubling a natural number are only the even numbers $2, 4, 6, \dots$ To land on an odd number such as 1 we would need $x = \tfrac12$ ⁠, which is not in the domain $\N$ ⁠. So $f$ is not onto. Whether a function is onto depends on the sets it is defined between, not only on its formula.

Given, to show, and the plan

Given: The rule $f(x) = 2x$ ⁠, with domain $\N = \{1,2,3,\dots\}$ and codomain $\N$ ⁠.
To show: (a) $f$ is one-one: $f(x_1) = f(x_2)$ forces $x_1 = x_2$ ⁠. (b) $f$ is not onto: some element of the codomain $\N$ is not an image.
Plan: (1) Confirm $f$ really maps $\N$ into $\N$ and list a few values. (2) Prove one-one for arbitrary $x_1, x_2$ ⁠. (3) Disprove onto with one explicit element, 1, and show why nothing maps to it. (4) Describe the full range, to see exactly what is missed.

Basics you need

1Domain and codomain

In $f : X \to Y$ ⁠, the domain $X$ is the set of allowed inputs and the codomain $Y$ is the set in which outputs are allowed to land. Here both are $\N = \{1, 2, 3, \dots\}$ ⁠, so inputs like $\tfrac12$ or $0$ are not allowed. Basics: what a function is

2One-one (injective)

$f$ is one-one if for every $x_1, x_2 \in X$ ⁠, $f(x_1) = f(x_2)$ implies $x_1 = x_2$ ⁠. In words: different inputs always give different outputs. Basics: one-one and onto

3Onto (surjective)

$f$ is onto if for every $y \in Y$ there is some $x \in X$ with $f(x) = y$ ⁠. Equivalently, the range of $f$ equals the whole codomain. To show onto fails, it is enough to find one $y \in Y$ that no input reaches.

4Proving and disproving

A "for every" claim (like one-one) is proved with arbitrary letters, never with a few examples. A "for every" claim (like onto) is disproved by one counterexample. Basics: proving and disproving

5Even numbers

A natural number is even when it equals $2k$ for some $k \in \N$ ⁠. The odd numbers $1, 3, 5, \dots$ are exactly those that are not of this form. Basics: integers, even and odd

Solution

Check that $f$ maps $\N$ into $\N$ ⁠, and list some values

If $x$ is a natural number, then $2x = x + x$ is a natural number too, so every output lies in the codomain $\N$ ⁠. Each input gives exactly one output, so $f$ is a genuine function $\N \to \N$ ⁠. A few values:

$x$ 1 2 3 4 5 6

$f(x) = 2x$ 2 4 6 8 10 12

Two things stand out: the outputs never repeat, and the odd numbers $1, 3, 5, \dots$ never appear.

Each input $x$ sends one arrow to $2x$ ⁠. No output receives two arrows (one-one), but every odd output, shown in rose, receives none (not onto).

Computing a few values first shows what to expect before we try to prove anything: the table already suggests "one-one: yes" and "onto: no". The check that outputs lie in $\N$ matters because the question names the codomain $\N$ ⁠; if some output fell outside it, $f$ would not be a function $\N \to \N$ at all.

$\N$ is closed under addition: the sum of two natural numbers is a natural number. Since $2x = x + x$ ⁠, doubling stays inside $\N$ ⁠.
One-one: equal outputs force equal inputs

Take arbitrary $x_1, x_2 \in \N$ and suppose $f(x_1) = f(x_2)$ ⁠. Then
$\begin{aligned} f(x_1) = f(x_2) &\Rightarrow 2x_1 = 2x_2 \\ &\Rightarrow x_1 = x_2. \end{aligned}$
(The second implication divides both sides by 2.)

So whenever two inputs have the same image, they are the same input. Hence $f$ is one-one.

Definition 5 is a statement about every pair $x_1, x_2$ ⁠, so we use letters that could stand for any natural numbers. We start from the hypothesis $f(x_1) = f(x_2)$ and derive the conclusion $x_1 = x_2$ ⁠. Dividing by 2 is valid because $2 \ne 0$ ⁠: if two numbers are equal, half of one equals half of the other.

Cancellation: if $c \ne 0$ and $c\,a = c\,b$ ⁠, then $a = b$ ⁠. Here $c = 2$ ⁠. This is exactly the step that would fail for a constant function like $g(x) = 0\cdot x$ ⁠, which is not one-one.
Not onto: nothing maps to 1

To be onto, every element of the codomain $\N$ must be an image. Look at $1 \in \N$ ⁠. If some $x$ had $f(x) = 1$ ⁠, then
$2x = 1 \quad\Longrightarrow\quad x = \frac{1}{2}.$
But $\tfrac12$ is not a natural number, so it is not in the domain. The equation $2x = 1$ has only this one solution, so no $x \in \N$ satisfies $f(x) = 1$ ⁠. Hence 1 is not the image of any element of the domain, and $f$ is not onto.

"Onto" says for every $y$ in the codomain there is a preimage. One $y$ without a preimage destroys that claim, so a single counterexample is a complete proof. We must show the preimage is missing, not just that we failed to find one: solving $2x = 1$ gives the only possible candidate, $x = \tfrac12$ ⁠, and it lies outside $\N$ ⁠. (A different argument works too: for every $x \in \N$ ⁠, $2x \ge 2 > 1$ ⁠.)

When solving $f(x) = y$ to test onto, always check that the solution belongs to the domain. The algebra happily produces $\tfrac12$ ⁠; the domain $\N$ is what rules it out. Basics: one-one and onto
Describe the range exactly

The range of $f$ is the set of all its outputs:
$\begin{aligned} \text{Range of } f &= \{2x : x \in \N\} \\ &= \{2, 4, 6, 8, \dots\}, \end{aligned}$
the set of even natural numbers. Every even number $2k$ is reached (by $x = k$ ⁠), and no odd number is reached, because for an odd $y$ the only solution of $2x = y$ is $x = \tfrac{y}{2}$ ⁠, which is not a whole number. So the range is a proper part of $\N$ ⁠, and by the Remark after Definition 6 ( $f$ is onto exactly when the range equals the codomain), $f$ is not onto. Infinitely many elements of the codomain are missed, not just 1.

Stating the range shows the full picture behind the single counterexample. It also explains which change of sets would make $f$ onto: if the codomain were the set of even natural numbers, $f$ would be onto (and then a bijection).

Range versus codomain: the codomain is declared in the question ( $f : \N \to \N$ ⁠); the range is what the rule actually produces. Onto means they coincide.
Conclude, and compare with Example 9

$f$ is one-one (Step 2) and not onto (Step 3). So $f : \N \to \N,\ f(x) = 2x$ is one-one but not onto.

The very next example in the book, Example 9, uses the same formula $f(x) = 2x$ on $\R$ instead of $\N$ ⁠. There, $x = \tfrac12$ is allowed, $f$ becomes onto, and the function is a bijection. The formula is the same; the sets changed the answer.

This example is also the textbook's evidence, in the Remark after Example 14, that on an infinite set a one-one function from the set to itself need not be onto. For finite sets that cannot happen (Examples 13 and 14).

$x$	1	2	3	4	5	6
$f(x) = 2x$	2	4	6	8	10	12

Result

$f(x) = 2x$ from $\N$ to $\N$ is one-one, since $2x_1 = 2x_2 \Rightarrow x_1 = x_2$ ⁠, and not onto, since $1 \in \N$ would need the preimage $x = \tfrac12 \notin \N$ ⁠. Its range is the set of even natural numbers $\{2, 4, 6, \dots\}$ ⁠.

Play this problem

Balloon Pop, in the chapter’s Games tab. Machine 1 is f(x) = 2x: hunt for a balloon nothing can hit. Play Balloon Pop ↗

Check it with numbers

Take the inputs $1, 2, \dots, 100$ ⁠. Their images $2, 4, \dots, 200$ are 100 different numbers, as one-one predicts. Among the numbers $1, 2, \dots, 200$ ⁠, exactly the 100 odd ones are never hit, and the smallest of them is 1, as the counterexample says. Also $f(37) = 74$ ⁠, and $74$ has no other preimage: $2x = 74$ only for $x = 37$ ⁠.

Common mistakes

Writing $x = \tfrac{y}{2}$ and declaring $f$ onto. That is the argument for $\R$ (Example 9). On $\N$ the preimage $\tfrac y2$ must itself be a natural number, and for odd $y$ it is not.
Proving one-one with examples. " $f(1) = 2$ ⁠, $f(2) = 4$ ⁠, all different" checks a few pairs only. The proof must use arbitrary $x_1, x_2$ ⁠.
Running the implication backwards. One-one is $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$ ⁠. The direction $x_1 = x_2 \Rightarrow f(x_1) = f(x_2)$ is true for every function and proves nothing.
Forgetting that $0 \notin \N$ here. The book's $\N$ starts at 1. That does not change this answer, but it matters in other questions.

What to take away

One-one: assume $f(x_1) = f(x_2)$ and work towards $x_1 = x_2$ ⁠. For $f(x) = ax$ with $a \ne 0$ ⁠, cancelling $a$ does it in one line.
Not onto: name one element of the codomain and show that the only candidate preimage lies outside the domain.
One-one and onto are properties of the triple (rule, domain, codomain). Change the sets and the answer can change.

Every fact used, and where it comes from

Fact	Used in	Source
Definition of one-one (injective)	Step 2	Definition 5, Section 1.3 (Lesson: types of functions)
Definition of onto (surjective)	Steps 3, 4	Definition 6, Section 1.3
$f$ onto $\iff$ range of $f$ = codomain	Step 4	Remark after Definition 6, Section 1.3
$\N$ closed under addition, so $2x \in \N$	Step 1	Properties of natural numbers
Cancelling a non-zero factor: $2x_1 = 2x_2 \Rightarrow x_1 = x_2$	Step 2	Arithmetic
$2x = 1 \iff x = \tfrac12$ ⁠, and $\tfrac12 \notin \N$	Step 3	Solving a linear equation
Infinite sets: one-one need not imply onto	Step 5	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 8: f(x)=2xf(x)=2xf(x)=2x on N\NN⁠: one-one but not onto

Basics you need

Solution

Check that fff maps N\NN into N\NN⁠, and list some values

One-one: equal outputs force equal inputs

Not onto: nothing maps to 1

Describe the range exactly

Conclude, and compare with Example 9

Every fact used, and where it comes from

Example 8: $f(x)=2x$ on $\N$ ⁠: one-one but not onto

Check that $f$ maps $\N$ into $\N$ ⁠, and list some values