# Set of Odd Integers is Countably Infinite

## 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$