Past exam of the logic and set theory course of the University of Oxford / 2011 / B / 4 / a

An approximation is a function $s:n+1\to X$ with $s(0)=x_0$ and $s(k+1)=g(s(k))$ for $k<n$. By induction on $n$, there is such a function: start with $\{(0,x_0)\}$ and append the uniquely specified value $g(s(n))$.

Any two approximations agree on their common domain, by induction from their common initial value and the same transition function $g$. The collection $\mathcal{S}$ of all approximations is a set, being a definable subset of $\mathcal{P}(\omega \times X)$. Therefore $f=\bigcup \mathcal{S}$ is a function. Existence of approximations of every finite length gives $\mathrm{dom}(f)=\omega$. Each defining equation appears in a sufficiently long approximation, soThis proves the natural-number recursion theorem without the axiom of choice; no arbitrary sequence of choices was made.

Suppose $h:\omega \hookrightarrow X$ is an injection. Shift its image by definingThe two pieces have disjoint images, so $g$ is injective, but $h(0)$ is omitted. Thus $g$ is not surjective.

Conversely, let $g:X\to X$ be an injection which omits some $a\in X$. The natural-number recursion theorem defines $h(0)=a$, $h(n+1)=g(h(n))$. If $h(m)=h(n)$ with $m<n$, repeated injectivity cancels $m$ iterations and gives $a=g^{n-m}(a)$, putting $a$ in the image of $g$, a contradiction. Hence $h$ is injective. ThereforeChoosing one witness $a$ from a single known nonempty set uses no axiom of choice. This is the Dedekind-infinite characterization.