Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 120 / 4

The structural induction principle says that a property $P(f)$ holds for every primitive recursive function if it holds for every initial function of recursion theory and is preserved by function composition in recursion theory and primitive recursion. This is justified because primitive recursive functions are, by definition, the smallest class closed under those constructors; equivalently, every such function has a finite construction tree, and ordinary induction on its height proves $P$.

Take $P(f)$ to mean that $f$ is total. The zero, successor, and projection functions are total. A composition of total functions is total. Finally, suppose $g$ and $h$ are total and $f$ is defined from them by primitive recursion. For fixed $\mathbf{x}$, induction on $n$ proves that $f(\mathbf{x},n)$ exists: the value at zero is $g(\mathbf{x})$, and from the existing value at $n$, totality of $h$ gives the value at $n+1$. Therefore every primitive recursive function is total.

Define a natural number to be a Finite von Neumann ordinal: an ordinal $n$ such that every nonempty subset of $n$ has a greatest member. This avoids the usual impredicative description of $\mathbb{N}$ as the intersection of all inductive sets.

Every usual von Neumann natural numberhas this property. The proof is by induction: a nonempty subset of $n+1$ either contains $n$, which is then greatest, or is a nonempty subset of $n$.

Conversely, let $\alpha$ be an ordinal with the stated property. If $\alpha$ were not one of the finite von Neumann ordinals, it would contain every finite ordinal. Indeed, if $n$ were the least finite ordinal not in $\alpha$, ordinal comparability and the presence of all $m<n$ would force $\alpha =n$ or $\alpha =m$ for some $m<n$. The subsetwould then be nonempty and have no greatest element, a contradiction. Thus this definition picks out exactly the natural numbers given by the usual least-inductive-set definition.

Let $T$ have a semidecidable axiomatization. If $T$ is inconsistent, the singleton axiom set $\{\perp \}$ is decidable and independent. If $T$ has no nonlogical axioms, the empty set already works. In the remaining case assume $T$ is consistent, choose a total computable enumeration $A_1,A_2,\dots$ of its axioms, allowing repetitions, and conservatively enlarge the language by fresh nullary predicates $P_1,P_2,\dots$.

For each $i\ge 1$, let $B_i$ be the conjunction of $i$ copies of $P_i\wedge A_i$. The range $\{B_i:i\ge 1\}$ is decidable by the Craig trick. Given a candidate formula of length $m$, only indices $i\le m$ are possible; compute $A_1,\dots ,A_m$, form the corresponding $B_i$, and compare the finite list syntactically.

The new theory has exactly the same consequences in the original language. Every model of $T$ expands to a model of all $B_i$ by interpreting every $P_i$ as true, while the reduct of any model of all $B_i$ satisfies every $A_i$. The axioms are independent: after deleting $B_i$, take any model of $T$, interpret $P_j$ as true for $j\ne i$, and interpret $P_i$ as false. This expansion satisfies every remaining $B_j$ but not $B_i$. Hence the $B_i$ form an independent tagged axiomatization that is decidable. Here equivalence means a conservative extension, or equivalently equality of all consequences in the original language.