Chapter 1 · Relations and Functions

Exercise 1.2 · Q9: Is the halving-and-rounding-up function bijective?

Exercise 1.2One-one and onto functions · Section 1.3

The question

Let $f : \N \to \N$ be defined by $f(n) = \begin{cases} \dfrac{n+1}{2}, & \text{if } n \text{ is odd} \\[2mm] \dfrac{n}{2}, & \text{if } n \text{ is even} \end{cases} \qquad \text{for all } n \in \N.$ State whether the function $f$ is bijective. Justify your answer.

Exam answer

$f(1) = \frac{1 + 1}{2} = 1$ and $f(2) = \frac22 = 1$ ⁠, but $1 \ne 2$ ⁠. So $f$ is not one-one.

Let $m \in \N$ ⁠. Then $2m \in \N$ is even, and $f(2m) = \frac{2m}{2} = m$ ⁠. So $f$ is onto.

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

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

The one idea this problem is built on

Work out a few values and the pattern is plain: $f(1)=1$ ⁠, $f(2)=1$ ⁠, $f(3)=2$ ⁠, $f(4)=2$ ⁠, and so on. The function pairs up neighbours, $2k-1$ and $2k$ ⁠, and sends both to $k$ ⁠. Every output is reached, so $f$ is onto. But every output is reached twice, so $f$ is not one-one. A bijection must be both, so $f$ is not bijective.

Given, to find, and the plan

Given: A rule $f$ with two cases, one for odd $n$ and one for even $n$ ⁠, from $\N = \{1,2,3,\dots\}$ to $\N$ ⁠.
To find: Whether $f$ is bijective, that is, both one-one (injective) and onto (surjective), with a justification.
Plan: (1) Confirm $f$ really is a function from $\N$ to $\N$ ⁠. (2) Tabulate values to see the pattern. (3) Test one-one. If it fails, a single counterexample settles it. (4) Test onto by solving $f(n)=m$ for an arbitrary $m$ ⁠. (5) Conclude.

Basics you need

1A function given "piece by piece"

A piecewise rule uses a different formula on different parts of the domain. To evaluate $f(n)$ ⁠, first decide which piece $n$ falls in (here: is $n$ odd or even?), then use only that piece. Basics: what a function is

2One-one (injective)

$f$ is one-one if different inputs always give different outputs: $f(x_1)=f(x_2) \Rightarrow x_1 = x_2$ ⁠. To show it fails, one pair $x_1 \ne x_2$ with $f(x_1)=f(x_2)$ is enough. Basics: one-one and onto

3Onto (surjective)

$f : A\to B$ is onto if every $y$ in the codomain $B$ is the image of something: for each $y\in B$ there is an $x\in A$ with $f(x)=y$ ⁠. To prove it, take an arbitrary $y$ and construct such an $x$ ⁠.

4Odd and even natural numbers

Every even natural number is $2k$ ⁠, and every odd natural number is $2k-1$ ⁠, for some $k\in\N$ ⁠. (So $1 = 2\cdot1-1$ ⁠, $3 = 2\cdot2-1$ ⁠, and so on.) Basics: even and odd

5Bijective

Bijective means one-one and onto. If either property fails, the function is not bijective. Basics: one counterexample disproves a "for all"

Solution

Check that $f$ really maps $\N$ into $\N$

The formulas contain divisions by 2, so first make sure the outputs are natural numbers, not fractions.
- If $n$ is odd, then $n+1$ is even, so $\frac{n+1}{2}$ is a whole number. It is at least $\frac{1+1}{2} = 1$ ⁠, so it is in $\N$ ⁠.
- If $n$ is even, then $\frac{n}{2}$ is a whole number, at least $\frac{2}{2} = 1$ ⁠, so it is in $\N$ ⁠.
Every natural number is either odd or even, never both, so exactly one formula applies to each $n$ ⁠. Hence $f$ assigns exactly one natural number to every natural number: it is a genuine function $\N\to\N$ ⁠.

The question says $f : \N \to \N$ ⁠, but with a piecewise formula it is worth confirming. If some output were $\tfrac{3}{2}$ ⁠, the codomain $\N$ would be wrong and the question would not make sense. The check also tells us that the two pieces never overlap or leave gaps.

Odd + 1 = even: if $n = 2k-1$ ⁠, then $n+1 = 2k$ ⁠. That is why $\frac{n+1}{2} = k$ comes out whole.

Tabulate values and spot the pattern

$n$	1	2	3	4	5	6	7	8	9	10
parity	odd	even	odd	even	odd	even	odd	even	odd	even
formula	$\frac{1+1}{2}$	$\frac22$	$\frac{3+1}{2}$	$\frac42$	$\frac{5+1}{2}$	$\frac62$	$\frac{7+1}{2}$	$\frac82$	$\frac{9+1}{2}$	$\frac{10}{2}$
$f(n)$	1	1	2	2	3	3	4	4	5	5

Each output appears exactly twice. In general, write the odd number as $2k-1$ and the even number just after it as $2k$ ⁠:

\begin{aligned} f(2k-1) &= \frac{(2k-1)+1}{2} = \frac{2k}{2} = k,\\[1mm] f(2k) &= \frac{2k}{2} = k. \end{aligned}

Each pair of neighbours

2k-1, 2k

lands on the same output

k

⁠. Every output receives an arrow (onto), but every output receives two (not one-one).

Before trying to prove anything about a strange-looking function, compute a few values. The table shows what to expect: two-to-one behaviour, so one-one should fail and onto should hold. The general formula

f(2k-1)=f(2k)=k

confirms the pattern holds for every

k

⁠, not just the ten we listed.

Writing odd numbers as

2k-1

and even numbers as

2k

(Basic 4) turns "odd" and "even" into algebra we can substitute into the formulas.

One-one? No: one counterexample settles it

From the table,
$f(1) = \frac{1+1}{2} = 1 \qquad\text{and}\qquad f(2) = \frac{2}{2} = 1.$
So $f(1) = f(2)$ although $1 \ne 2$ ⁠. Two different inputs share an output, so $f$ is not one-one.

"One-one" is a claim about every pair of inputs: whenever the outputs agree, the inputs must agree. A claim about every pair is destroyed by a single pair that breaks it. So we do not need the general argument here; the specific pair 1, 2 is a complete and rigorous disproof.

To disprove "for all", give one counterexample. To prove "for all", you need a general argument. Basics: proving and disproving
Onto? Yes: build an input for any output

Take an arbitrary $m \in \N$ ⁠. We need some $n\in\N$ with $f(n) = m$ ⁠. From Step 2 we know where to look: $m$ is the output of the even number $2m$ ⁠. Choose $n = 2m$ ⁠. This is a natural number, and it is even, so the second formula applies:
$f(2m) = \frac{2m}{2} = m.$
So every $m\in\N$ is an image under $f$ ⁠, and $f$ is onto. (The odd number $2m-1$ works too, since $f(2m-1) = \frac{2m}{2} = m$ ⁠. That second preimage is exactly why $f$ is not one-one.)

"Onto" says every element of the codomain is hit. That is a "for every $m$ " claim, so a few examples will not do. We take a general $m$ and produce an input that works. Guessing the input is legitimate, provided we then check it: we confirm that $2m$ is in the domain $\N$ and that $f(2m)$ really equals $m$ ⁠.

To prove onto: for an arbitrary $y$ in the codomain, find $x$ in the domain with $f(x)=y$ ⁠. Always check that the $x$ you find actually lies in the domain. Basics: one-one and onto
Conclude

A bijection must be both one-one and onto. $f$ is onto (Step 4) but not one-one (Step 3), so $f$ is not bijective.

Note how this compares with finite sets. In Examples 13 and 14 the textbook shows that for a function from a finite set to itself, one-one and onto always come together. This exercise is a reminder that on an infinite set like $\N$ they can split apart: here we have onto without one-one. (Example 10 is another such case.)

Result

No, $f$ is not bijective. It is onto, because every $m\in\N$ equals $f(2m)$ ⁠. It is not one-one, because $f(1) = f(2) = 1$ ⁠. In fact $f$ is exactly two-to-one: $f(2k-1) = f(2k) = k$ ⁠. (Textbook answer: "No".)

Play this problem

Balloon Pop, in the chapter’s Games tab. Machine 2 is this function: find the double hit, and see that every balloon can be hit. Play Balloon Pop ↗

Check it with numbers

Pick an output, say $m = 37$ ⁠. Step 4 says $n = 74$ should give it: $74$ is even, so $f(74) = 74/2 = 37$ ⁠. ✓ The other preimage is $73$ ⁠: it is odd, so $f(73) = (73+1)/2 = 37$ ⁠. ✓ Two inputs, one output, exactly as the analysis predicts.

Common mistakes

Using the wrong piece. $f(3)$ uses $\frac{n+1}{2}$ because 3 is odd; it is $2$ ⁠, not $1.5$ ⁠.
"Each piece is one-one, so $f$ is one-one." Each formula on its own never repeats a value, but the two pieces can collide with each other, and here they always do.
Stopping at "not one-one" without saying why onto holds. The question asks you to justify; a complete answer reports both properties.
Forgetting to check the preimage is in the domain. If the codomain included 0, there would be no natural $n$ with $f(n)=0$ ⁠, and onto would fail.

What to take away

With a piecewise function, test one-one across the pieces, not just within each piece.
One-one fails with one counterexample. Onto is proved by constructing a preimage for an arbitrary output, then checking it.
On infinite sets, onto and one-one are independent. Finite sets mapped to themselves are the special case where they coincide.

Every fact used, and where it comes from

Fact	Used in	Source
Odd numbers are $2k-1$ ⁠, even numbers are $2k$ ⁠, $k\in\N$	Steps 1, 2	Definition of odd and even
$f(2k-1) = f(2k) = k$	Steps 2–4	Direct substitution into the two formulas
Definitions of one-one, onto, bijective	Steps 3–5	Definitions 5–7, Section 1.3 (Lesson: types of functions)
One counterexample disproves a "for all" statement	Step 3	Logic of quantifiers
Finite sets: one-one ⇔ onto	Step 5 remark	Examples 13 and 14

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 →

Exercise 1.2 · Q9: Is the halving-and-rounding-up function bijective?

Basics you need

Solution

Check that fff really maps N\NN into N\NN

Tabulate values and spot the pattern

One-one? No: one counterexample settles it

Onto? Yes: build an input for any output

Conclude

Every fact used, and where it comes from

Check that $f$ really maps $\N$ into $\N$