# Equivalence of Definitions of Countably Infinite Set

## Contents

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