Question

Show that the function $f: \mathbb{N} \to \mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers, given by \[ f(n) = \begin{cases} n - 1, & \text{if } n \text{ is even} \\ n + 1, & \text{if } n \text{ is odd} \end{cases} \] is a bijection.

Hint:

To prove a function is a bijection, verify that it is both injective (one-to-one) and surjective (onto).

Answer 1

The objective is to demonstrate that the function $f$ is a bijection. This requires proving that $f$ is both injective and surjective. - Injectivity: A function $f$ is injective if $f(a) = f(b)$ implies $a = b$. Assume $f(a) = f(b)$. Case 1: If $a$ and $b$ are both even, then $f(a) = a - 1$ and $f(b) = b - 1$. Setting $a - 1 = b - 1$ yields $a = b$. Case 2: If $a$ and $b$ are both odd, then $f(a) = a + 1$ and $f(b) = b + 1$. Setting $a + 1 = b + 1$ yields $a = b$. Thus, $f$ is injective. - Surjectivity: A function $f$ is surjective if for every $y$ in the target set, there exists an $x$ in the domain such that $f(x) = y$. Let $y \in \mathbb{N}$. If $y$ is even, then $f(y+1) = y$. If $y$ is odd, then $f(y-1) = y$. Consequently, every element in the target set has a preimage in the domain, establishing that $f$ is surjective. Since $f$ is both injective and surjective, it is a bijection.