Theorem. There's a bijection from the set of natural numbers to an alternative set of the natural numbers $\mathbb{N}'$ that obey the Peano axioms.

Proof. According to the recursion theorem there is a (unique) function $$ f:\mathbb{N} \rightarrow \mathbb{N}' \: with \: f(0) = 0' \wedge (\forall n \in \mathbb{N}) \: f(n++) = f(n)++' $$ such that f(n) = n' iff f(n++) = n'++'. Due to the Peano axioms all successors in $\mathbb{N}'$ are pairwise different such that for all $n \in \mathbb{N}$ there's exactly one element in $\mathbb{N}'$ which means that $f$ is 1-1. Now assume $f$ is not surjective. Then there is an element in $\mathbb{N}'$ which cannot be reached by an infinite application of the successor operator to $0'$. A contradiction. Hence, we have that $f$ is onto and 1-1, equivalent to saying that $f$ is a bijection.

• Back to menu