[proofplan] We prove that the class $\mathcal{R}$ of partial recursive functions coincides with the class $\mathcal{T}$ of partial functions of the form $f_{T,\ell}$ for some recursion tree $(T, \ell)$, and that the primitive recursive functions coincide with those $f_{T,\ell}$ whose labelling uses no minimisation. The proof is two inclusions. For $\mathcal{T} \subseteq \mathcal{R}$ we induct on the height of $(T, \ell)$: leaves are labelled by basic functions (identity, zero, successor, projection), which are recursive by definition, and each internal node applies one of the closure operations (composition, primitive recursion, minimisation) to the recursive functions provided by its immediate subtrees; recursion tree semantics is then, by inspection, the same as the inductive definition of $\mathcal{R}$. For $\mathcal{R} \subseteq \mathcal{T}$ we induct on the derivation of $f \in \mathcal{R}$: a basic function is realised by a single-node tree; a function obtained by composition, primitive recursion, or minimisation from functions with trees $(T_i, \ell_i)$ is realised by the tree whose root has the appropriate label and whose immediate subtrees are the $(T_i, \ell_i)$. The primitive recursive case is the restriction of both arguments to tree labellings that avoid the minimisation operation. At each step we verify that the tree-semantics operation matches the closure operation, so the induced partial function is precisely the function constructed by the closure rule. [/proofplan] [step:Fix notation for recursive functions and recursion trees] Write $\mathbb{W} := \Sigma^*$ for the set of words over a fixed finite alphabet $\Sigma$. A *partial function* is a map $f : \mathbb{W}^k \rightharpoonup \mathbb{W}$ for some arity $k \ge 0$, where $\rightharpoonup$ indicates $f$ may be undefined on some inputs (we write $f(w) \uparrow$ for "undefined" and $f(w) \downarrow$ for "defined"). The class $\mathcal{R}$ of *partial recursive functions* is the smallest class of partial functions over $\mathbb{W}$ that contains the basic functions (zero, successors $s_a : v \mapsto va$ for each $a \in \Sigma$, and projections $\pi_i^k : (w_1, \ldots, w_k) \mapsto w_i$) and is closed under \begin{align*} \text{composition: } & (g, f_1, \ldots, f_m) \;\mapsto\; g \circ (f_1, \ldots, f_m), \\ \text{primitive recursion: } & (f, g) \;\mapsto\; h \text{ where } h(w, \varepsilon) = f(w) \text{ and } h(w, s_a(v)) = g_a(w, v, h(w, v)), \\ \text{minimisation: } & f \;\mapsto\; \mu f \text{ where } (\mu f)(w) = \min\{v : f(w, v) = \varepsilon \text{ and } f(w, v') \downarrow \text{ for all } v' < v\}. \end{align*} The subclass $\mathcal{PR} \subseteq \mathcal{R}$ of *primitive recursive* functions is the smallest class containing the basic functions and closed under composition and primitive recursion (but not minimisation); all primitive recursive functions are total. A *recursion tree* over $\mathbb{W}$ is a finite rooted ordered tree $T$ together with a labelling $\ell$ that assigns to each node a label drawn from a fixed finite set of tags: \begin{align*} \ell(v) \in \{&\text{basic}_{\pi_i^k}, \text{basic}_{s_a}, \text{basic}_0\} \\ & \cup \{\text{comp}\} \cup \{\text{rec}\} \cup \{\text{min}\}, \end{align*} subject to the arity constraint that each node's label determines the number of children it must have. A *leaf* must be labelled with a basic function. An internal node labelled $\text{comp}$ has one "outer" child $v_g$ and $m$ "inner" children $v_{f_1}, \ldots, v_{f_m}$ for some $m$. An internal node labelled $\text{rec}$ has two children $v_f$ and $v_g$ (and records which letter $a \in \Sigma$ each recursion branch corresponds to, yielding one child per letter if the alphabet has more than one letter; we absorb this into the $\text{rec}$ label without loss of generality by treating $\text{rec}$ as collecting $|\Sigma|$-many $g_a$'s along with $f$). An internal node labelled $\text{min}$ has one child $v_f$. To each recursion tree we associate a partial function $f_{T, \ell}$ by induction on the height of $T$: \begin{align*} \text{leaf with } \ell = \text{basic}_\phi: \quad & f_{T, \ell} = \phi \; (\phi \text{ a basic function}); \\ \text{node labelled } \text{comp}: \quad & f_{T, \ell} = f_{T_g, \ell_g} \circ (f_{T_{f_1}, \ell_{f_1}}, \ldots, f_{T_{f_m}, \ell_{f_m}}); \\ \text{node labelled } \text{rec}: \quad & f_{T, \ell} \text{ is the function } h \text{ defined by primitive recursion from } f_{T_f, \ell_f} \text{ and } f_{T_{g_a}, \ell_{g_a}}; \\ \text{node labelled } \text{min}: \quad & f_{T, \ell} = \mu(f_{T_f, \ell_f}). \end{align*} A recursion tree is *primitive-recursive* if no node carries a $\text{min}$ label. Write $\mathcal{T} := \{f_{T, \ell} : (T, \ell) \text{ a recursion tree}\}$ and $\mathcal{T}_{\text{pr}} := \{f_{T, \ell} : (T, \ell) \text{ a primitive-recursive recursion tree}\}$. The theorem asserts $\mathcal{R} = \mathcal{T}$ and $\mathcal{PR} = \mathcal{T}_{\text{pr}}$. [/step] [step:Show that every function realised by a recursion tree is partial recursive] We prove $\mathcal{T} \subseteq \mathcal{R}$ (and simultaneously $\mathcal{T}_{\text{pr}} \subseteq \mathcal{PR}$) by induction on the *height* of the recursion tree $(T, \ell)$. *Base case: height $0$.* The tree consists of a single leaf, which by definition carries a basic-function label $\text{basic}_\phi$. Then $f_{T, \ell} = \phi \in \mathcal{R}$ because the basic functions are explicitly among the generators of $\mathcal{R}$. The leaf is trivially a primitive-recursive tree, and $\phi \in \mathcal{PR}$ by the same reason. *Inductive step: height $\ge 1$.* Let $(T, \ell)$ have height $n \ge 1$ and let $r$ be its root. The immediate subtrees $(T_1, \ell_1), \ldots, (T_k, \ell_k)$ rooted at the children of $r$ all have height $\le n - 1$, so by the induction hypothesis $f_{T_i, \ell_i} \in \mathcal{R}$ for each $i$. We split on the label of the root. - $\ell(r) = \text{comp}$: the root has one outer child and $m$ inner children, giving $k = m + 1$ children. By the tree semantics, $f_{T, \ell} = f_{T_g, \ell_g} \circ (f_{T_{f_1}, \ell_{f_1}}, \ldots, f_{T_{f_m}, \ell_{f_m}})$, where $f_{T_g, \ell_g} \in \mathcal{R}$ and $f_{T_{f_i}, \ell_{f_i}} \in \mathcal{R}$ by the induction hypothesis. Since $\mathcal{R}$ is closed under composition, $f_{T, \ell} \in \mathcal{R}$. If $(T, \ell)$ is primitive-recursive, so are all immediate subtrees, and then $f_{T, \ell} \in \mathcal{PR}$ because $\mathcal{PR}$ is closed under composition. - $\ell(r) = \text{rec}$: the root's children yield a "base" function $f_{T_f, \ell_f}$ and step functions $f_{T_{g_a}, \ell_{g_a}}$ for each $a \in \Sigma$, all in $\mathcal{R}$ (resp. $\mathcal{PR}$) by the induction hypothesis. The tree semantics defines $f_{T, \ell}$ as the function $h$ obtained from them by primitive recursion. Since $\mathcal{R}$ (resp. $\mathcal{PR}$) is closed under primitive recursion, $f_{T, \ell} \in \mathcal{R}$ (resp. $\mathcal{PR}$). - $\ell(r) = \text{min}$: the root has one child with recursion tree $(T_f, \ell_f)$ and $f_{T_f, \ell_f} \in \mathcal{R}$ by the induction hypothesis. Then $f_{T, \ell} = \mu(f_{T_f, \ell_f}) \in \mathcal{R}$ by closure of $\mathcal{R}$ under minimisation. This case cannot occur if $(T, \ell)$ is primitive-recursive (by definition of that class of trees), so the primitive-recursive induction is not affected by this case. By induction on height, $f_{T, \ell} \in \mathcal{R}$ for every recursion tree, and $f_{T, \ell} \in \mathcal{PR}$ for every primitive-recursive recursion tree. [/step] [step:Show that every partial recursive function is realised by a recursion tree] We prove $\mathcal{R} \subseteq \mathcal{T}$ (and simultaneously $\mathcal{PR} \subseteq \mathcal{T}_{\text{pr}}$) by induction on the *construction* of a function $f \in \mathcal{R}$. The class $\mathcal{R}$ (resp. $\mathcal{PR}$) is defined as the smallest class closed under certain operations, which is equivalent to saying every member arises by finitely many applications of those operations to basic functions; we induct on the number of such applications (the *derivation depth*). *Base case: $f$ is a basic function.* Let $(T_f, \ell_f)$ be the recursion tree consisting of a single leaf labelled $\text{basic}_f$ (which is a valid label because $f$ is one of zero, $s_a$, or $\pi_i^k$). Then $f_{T_f, \ell_f} = f$ by the leaf rule of the tree semantics, so $f \in \mathcal{T}$. The single-leaf tree is primitive-recursive (no $\text{min}$ node), so the same witness also shows $f \in \mathcal{T}_{\text{pr}}$. *Inductive step: $f$ is obtained by a closure operation.* We split on which closure operation produced $f$. - *$f$ from composition.* Suppose $f = g \circ (f_1, \ldots, f_m)$ with $g, f_1, \ldots, f_m \in \mathcal{R}$ each having smaller derivation depth than $f$. By the induction hypothesis there exist recursion trees $(T_g, \ell_g)$ and $(T_{f_i}, \ell_{f_i})$ with $f_{T_g, \ell_g} = g$ and $f_{T_{f_i}, \ell_{f_i}} = f_i$. Construct $(T, \ell)$ with a new root $r$ labelled $\text{comp}$, whose outer child subtree is $(T_g, \ell_g)$ and whose $m$ inner children subtrees are $(T_{f_1}, \ell_{f_1}), \ldots, (T_{f_m}, \ell_{f_m})$. By the tree semantics, \begin{align*} f_{T, \ell} &= f_{T_g, \ell_g} \circ (f_{T_{f_1}, \ell_{f_1}}, \ldots, f_{T_{f_m}, \ell_{f_m}}) = g \circ (f_1, \ldots, f_m) = f, \end{align*} so $f \in \mathcal{T}$. If $g, f_1, \ldots, f_m \in \mathcal{PR}$, then by induction hypothesis each subtree is primitive-recursive, and $(T, \ell)$ is primitive-recursive because the new root carries $\text{comp}$ (not $\text{min}$); hence $f \in \mathcal{T}_{\text{pr}}$. - *$f$ from primitive recursion.* Suppose $f = h$, where $h$ is defined by primitive recursion from $g \in \mathcal{R}$ and a family $\{g_a : a \in \Sigma\} \subset \mathcal{R}$ of smaller derivation depth. By the induction hypothesis, these functions admit recursion trees $(T_g, \ell_g), (T_{g_a}, \ell_{g_a})$. Construct $(T, \ell)$ with a new root $r$ labelled $\text{rec}$, whose children subtrees are $(T_g, \ell_g)$ and $(T_{g_a}, \ell_{g_a})$ for each $a \in \Sigma$ in fixed order. By the tree semantics, $f_{T, \ell}$ is the function defined from $f_{T_g, \ell_g} = g$ and $f_{T_{g_a}, \ell_{g_a}} = g_a$ by primitive recursion, which is exactly $h = f$. So $f \in \mathcal{T}$. If all inputs are in $\mathcal{PR}$, the subtrees are primitive-recursive, and $(T, \ell)$ remains primitive-recursive because $\text{rec}$ is not $\text{min}$; hence $f \in \mathcal{T}_{\text{pr}}$. - *$f$ from minimisation.* Suppose $f = \mu g$ for some $g \in \mathcal{R}$ of smaller derivation depth. By the induction hypothesis, $(T_g, \ell_g)$ satisfies $f_{T_g, \ell_g} = g$. Construct $(T, \ell)$ with a new root $r$ labelled $\text{min}$ and single child subtree $(T_g, \ell_g)$. Then $f_{T, \ell} = \mu f_{T_g, \ell_g} = \mu g = f$, so $f \in \mathcal{T}$. This case is not available in the $\mathcal{PR} \to \mathcal{T}_{\text{pr}}$ induction because minimisation is not among the closure operations defining $\mathcal{PR}$; so no case is missing there. By induction on derivation depth, every $f \in \mathcal{R}$ satisfies $f \in \mathcal{T}$, and every $f \in \mathcal{PR}$ satisfies $f \in \mathcal{T}_{\text{pr}}$. [/step] [step:Combine the two inclusions] Step 2 establishes $\mathcal{T} \subseteq \mathcal{R}$ and $\mathcal{T}_{\text{pr}} \subseteq \mathcal{PR}$; Step 3 establishes $\mathcal{R} \subseteq \mathcal{T}$ and $\mathcal{PR} \subseteq \mathcal{T}_{\text{pr}}$. Combining: \begin{align*} \mathcal{R} &= \mathcal{T}, & \mathcal{PR} &= \mathcal{T}_{\text{pr}}. \end{align*} So a partial function $f$ is (partial) recursive iff there exists a recursion tree $(T, \ell)$ with $f = f_{T, \ell}$, and $f$ is primitive recursive iff such a tree exists with no $\text{min}$ labels. This is the theorem. [/step]