Set of Odd Integers is Countably Infinite
Jump to navigation
Jump to search
Theorem
Let $\Bbb O$ be the set of odd integers.
Then $\Bbb O$ is countably infinite.
Proof
Let $f: \Bbb O \to \Z$ be the mapping defined as:
- $\forall x \in \Bbb O: \map f x = \dfrac {x + 1} 2$
$f$ is well-defined as $x + 1$ is even and so $\dfrac {x + 1} 2 \in \Z$.
Let $x, y \in \Bbb O$ such that $\map f x = \map f y$.
Then:
\(\ds \map f x\) | \(=\) | \(\ds \map f y\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \dfrac {x + 1} 2\) | \(=\) | \(\ds \dfrac {y + 1} 2\) | Definition of $f$ | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds x + 1\) | \(=\) | \(\ds y + 1\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds x\) | \(=\) | \(\ds y\) |
Thus $f$ is injective by definition.
Consider the inverse $f^{-1}$.
By inspection:
- $\forall x \in \Z: \map {f^{-1} } x = 2 x - 1$
$f^{-1}$ is well-defined, and $2 x - 1$ is odd.
Thus $f^{-1}$ is a mapping from $\Z$ to $\Bbb O$.
Then:
\(\ds \map {f^{-1} } x\) | \(=\) | \(\ds \map {f^{-1} } y\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds 2 x - 1\) | \(=\) | \(\ds 2 y - 1\) | Definition of $f^{-1}$ | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds 2 x\) | \(=\) | \(\ds 2 y\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds x\) | \(=\) | \(\ds y\) |
Thus $f^{-1}$ is injective by definition.
It follows by the Cantor-Bernstein-Schröder Theorem that there exists a bijection between $\Z$ and $\Bbb O$.
$\blacksquare$
Sources
- 2008: David Joyner: Adventures in Group Theory (2nd ed.) ... (previous) ... (next): Chapter $2$: 'And you do addition?': $\S 2.1$: Functions: Example $2.1.6$