Equivalence of Definitions of Countably Infinite Set

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set.


The following definitions of the concept of Countably Infinite Set are equivalent:

Definition 1

$S$ is countably infinite if and only if there exists a bijection:

$f: S \to \N$

where $\N$ is the set of natural numbers.

Definition 2

$S$ is countably infinite if and only if there exists a bijection:

$f: S \to \Z$

where $\Z$ is the set of integers.


Proof

From Integers are Countably Infinite there is a bijection between $\Z$, the set of integers, and $\N$, the set of natural numbers.

Let $h: \N \to \Z$ be such a bijection.


Let $f: S \to \N$ be a bijection.

From Composite of Bijections is Bijection:

$h \circ f: S \to \Z$ is a bijection.


Similarly, let $g: S \to \Z$ be a bijection.

By Inverse of Bijection is Bijection, $h^{-1}: \Z \to \N$ is a bijection.

Again from Composite of Bijections is Bijection:

$h^{-1} \circ g: S \to \N$ is a bijection.

Hence the result.

$\blacksquare$