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

We are asked to show that the function $f$ is a bijection. To prove this, we need to show that $f$ is both injective (one-to-one) and surjective (onto). - Injectivity: A function is injective if $f(a) = f(b)$ implies $a = b$. Suppose $f(a) = f(b)$. There are two cases to consider: 1. If $a$ and $b$ are both even, then $f(a) = a - 1$ and $f(b) = b - 1$. Thus, $a - 1 = b - 1$, which implies $a = b$. 2. If $a$ and $b$ are both odd, then $f(a) = a + 1$ and $f(b) = b + 1$. Thus, $a + 1 = b + 1$, which implies $a = b$. Therefore, $f$ is injective. - Surjectivity: A function is surjective if for every element $y$ in the target set, there is an $x$ in the domain such that $f(x) = y$. Consider any $y \in \mathbb{N}$. If $y$ is even, then $f(y+1) = y$. If $y$ is odd, then $f(y-1) = y$. Hence, every element of the target set has a preimage in the domain, so $f$ is surjective. Since $f$ is both injective and surjective, it is a bijection.