Set of Even Integers is Countably Infinite

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\Bbb E$ be the set of even integers.


Then $\Bbb E$ is countably infinite.


Proof

Let $f: \Bbb E \to \Z$ be the mapping defined as:

$\forall x \in \Bbb E: \map f x = \dfrac x 2$

$f$ is well-defined as $x$ is even and so $\dfrac x 2 \in \Z$.

Let $x, y \in \Bbb E$ such that $\map f x = \map f y$.

Then:

\(\ds \map f x\) \(=\) \(\ds \map f y\)
\(\ds \leadsto \ \ \) \(\ds \dfrac x 2\) \(=\) \(\ds \dfrac y 2\) Definition of $f$
\(\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$

$f^{-1}$ is well-defined, and $2 x$ is even.

Thus $f^{-1}$ is a mapping from $\Z$ to $\Bbb E$.

Then:

\(\ds \map {f^{-1} } x\) \(=\) \(\ds \map {f^{-1} } y\)
\(\ds \leadsto \ \ \) \(\ds 2 x\) \(=\) \(\ds 2 y\) Definition of $f^{-1}$
\(\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 E$.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Set_of_Even_Integers_is_Countably_Infinite&oldid=483313"