Subjects set theory

Bijection Natural Odd

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Bijection Natural Odd


1. The problem asks us to construct a bijection (a one-to-one and onto function) from the set of natural numbers $\mathbb{N}$ to the set of odd natural numbers $\mathbb{O}$. This bijection will show both sets have the same cardinality. 2. Recall that $\mathbb{N} = \{1, 2, 3, 4, 5, \ldots\}$ and $\mathbb{O} = \{1, 3, 5, 7, 9, \ldots\}$. Each natural number maps to an odd number. 3. Define the function $f: \mathbb{N} \to \mathbb{O}$ by the rule $$ f(n) = 2n - 1 $$ This function takes any natural number $n$ and maps it to the $n$-th odd number. 4. To prove $f$ is a bijection, we show it is injective and surjective. 5. Injective: Suppose $f(n_1) = f(n_2)$. Then $2n_1 - 1 = 2n_2 - 1$ implies $2n_1 = 2n_2$ and hence $n_1 = n_2$. So $f$ is injective. 6. Surjective: For any odd number $m \in \mathbb{O}$, $m$ can be expressed as $m = 2k - 1$ where $k$ is a natural number. Since $f(k) = m$, every element in $\mathbb{O}$ has a preimage in $\mathbb{N}$. So $f$ is surjective. 7. Therefore, $f$ is a bijection and this proves that $\mathbb{N}$ and $\mathbb{O}$ have the same number of elements. Final answer: $$f(n) = 2n - 1$$