Surjection, Recursion and Induction

Question

Let $S$ be the set inductively defined by:

1) $* \in S$

2) If $a \in S$ and $b \in S$ then $\langle a,b \rangle \in S$.

For each natural number $n \in \mathbf{N}$, let $d(n)=\text{max}\{k \quad|\quad5^{k} \quad \text{divides} \quad n\}$ and $e(n)=\text{max}\{k \quad | \quad 2^{k} \quad \text{divides} \quad n\}$. Let $f:\mathbf{N} \to S$ be defined recursively by:

$$f(0)=*$$ $$f(n)=\langle f(d(n)),f(e(n))\rangle$$

Show that $f$ is surjective.

Answer 1

• $f(0)=\star$ is in $\operatorname{im}f$.
• If $a=f(n), b=f(m)$ are in $\operatorname{im}f$, then $\langle a,b\rangle = f(2^m5^n)$ is in $\operatorname{im}f$.