Q.Show that $f: \mathbb{N} \to \mathbb{N}$, given by $f(x) = \begin{cases} x + 1, & \text{if } x \text{ is odd} \\ x - 1, & \text{if } x \text{ is even} \end{cases}$ is both one-one and onto.

Concept: Bijection Proof — Show the function is both injective (one-one) and surjective (onto).

Step 1: One-one.

Take any $x, y \in \mathbb{N}$ with $f(x) = f(y)$.

• If $x$ is odd, $f(x) = x+1$ (even). If $y$ is odd, $x+1 = y+1 \Rightarrow x = y$.
• If $x$ is even, $f(x) = x-1$ (odd). If $y$ is even, $x-1 = y-1 \Rightarrow x = y$.
• If one is odd and the other even, their images have opposite parity (odd vs even), so they cannot be equal. Thus $f$ is one-one.

Step 2: Onto.

Take any $y \in \mathbb{N}$. …

Why a Bijection Proof Works

The key insight is that $f$ simply exchanges each odd number with the even number immediately after it.

• If $x$ is odd, $f(x) = x+1$ (the next even number).
• If $x$ is even, $f(x) = x-1$ (the previous odd number).

So the function pairs up numbers like $(1,2)$, $(3,4)$, $(5,6)$, … and within each pair, the two numbers swap places. This is a perfect matching — every natural number belongs to exactly one such pair, and the function just swaps the two members.

A function that is a bijection must be both one-one (injective) and onto (surjective). We’ll prove each separately.

Step-by-Step Proof

1. Proving $f$ is one-one (injective)

We need to show: if $f(a) = f(b)$, then $a = b$.

Consider two natural numbers $a$ and $b$. Each is either odd or even. There are four cases to check.

Case 1: Both $a$ and $b$ are odd.

Then $f(a) = a+1$ and $f(b) = b+1$.

If $a+1 = b+1$, then $a = b$.

Case 2: Both $a$ and $b$ are even.

Then $f(a) = a-1$ and $f(b) = b-1$.

If $a-1 = b-1$, then $a = b$.

Case 3: $a$ is odd, $b$ is even.

Then $f(a) = a+1$ (which is even) and $f(b) = b-1$ (which is odd).

An even number can never equal an odd number, so $f(a) \neq f(b)$. This case cannot happen if $f(a) = f(b)$.

Case 4: $a$ is even, $b$ is odd.

Symmetric to Case 3 — $f(a)$ is odd, $f(b)$ is even, so they cannot be equal.

Thus the only way $f(a) = f(b)$ is when both inputs have the same parity, and then equality forces $a = b$. Hence $f$ is injective.

2. Proving $f$ is onto (surjective)

We need to show: for every $y \in \mathbb{N}$, there exists some $x \in \mathbb{N}$ such that $f(x) = y$.

Take any natural number $y$. We consider two cases based on whether $y$ is odd or even.

Case 1: $y$ is odd.

Since $y$ is odd, $y+1$ is even. Let $x = y+1$. …

Method: Proving a bijection by parity/cases

Use this when a function is defined by cases on parity (odd/even) and you must show it is one-one and onto.

Steps

Step 1: One-one via case analysis on parity

Suppose $f(a)=f(b)$. Split by the parity of $a$ and $b$. Within the same parity, equality of outputs forces $a=b$. Across opposite parities, the outputs have different parity (one odd, one even) and so cannot be equal — that case cannot occur.

Step 2: Onto by constructing a preimage for each target …

Common Mistakes

Mistake 1: Forgetting the cross-parity case when proving one-one

Why it's wrong: students check same-parity inputs but ignore that an odd input gives an even output and an even input gives an odd output, so they can never collide. Correct approach: include the mixed case and note the outputs have different parity, so $f(a)=f(b)$ is impossible there.

Mistake 2: Not constructing an explicit preimage for onto …