Exercise
3
[1YP] Show that every \(nββ\) with \(nβ 0\) is successor of another \(kββ\), proving by induction on \(n\) this proposition
\[ P(n) \, {\stackrel{.}{=}}\, (n=0) β¨ (β k ββ, S(k)=n) \quad . \]
This shows that the successor function
\[ S:β β β⧡\{ 0\} \]
is bijective.
If \(n\neq 0\), we will call \(S^{-1}(n)\) the predecessor of \(n\).
Solution
1
(Part of this result applies more generally, see [1Z1])