Consistent recursively axiomatizable theory This is question 4 page 234 of Enderton's Mathematical Introduction to Logic, section 3.4 on the "Arithmetization of Syntax":

Let $T$ be a consistent recursively axiomatizable theory (in a recursively numbered language with $\mathbf{0}$ and $\mathbf{S}$). Show that any relation representable in $T$ must be recursive.

I think this is related to Theorem 34A p. 232:

A relation is recursive iff it is representable in the theory $\text{Cn}\ A_E$.

But I'm not sure how to use that information. Should I show that deductions in $T$ can be coded in $A_E$, or is there a better way to do it?
 A: Long comment
Basically, yes. See definition page 205 :

More generally, let $T$ be any theory in a language with $0$ and $S$. Then
  $\rho$ represents $R$ in $T$ iff for every $a_1,\ldots, a_m \in \mathbb N$ :

$\langle a_1, \ldots, a_m \rangle \in R \Rightarrow \rho(S^{a_1}0,\ldots, S^{a_m}0) \in T$,
$\langle a_1, \ldots, a_m \rangle \notin R \Rightarrow (\lnot \rho(S^{a_1}0,\ldots, S^{a_m}0)) \in T$.


Then, the exercise implicitly refers to the last comment before Th.34A, page 232 :

Since the converse to item 19 is immediate, we have [...].

The converse of item 19 is exactly :

Any relation that is representable in $\mathsf {Cn} A_E$ is  recursive.

The execise is aimed to prove that for recursiveness it is enough a theory $T$ that is :

consistent and recursively axiomatizable (in a recursively numbered language with $0$ and $S$).  

Note that [page 207] :

DEFINITION. A relation $R$ on the natural numbers is recursive iff it
  is representable in some consistent finitely axiomatizable theory (in a language with $0$ and $S$).

We have that $A_E$ [see page 203] consists of eleven axioms; thus $\mathsf {Cn} A_E$ is finitely axiomatizable.
Now, the issue is : is it possible to "relax" the requirement from finitely axiomatizable to recursively axiomatizable ?
The answer is yes, because being recursively axiomatizable is enough to ensure that we can manufacture a primitive recursive predicate $Ax_T(x)$ coding : "$x$ is an axiom of $T$". In this way, the provability predicate : $Prov_T(x,z)$, coding : "$x$ is a derivation of $z$ from the axioms of $T$", is still primitive recursive and all the "machinery" works.

Added
Let $T$ be a consistent, recursively axiomatized (i.e. axiomatized by a recursive set of axioms) theory containing $\overline 0$ and $S$.
Assume $R$ is representable in $T$; we want to prove that $R$ is recursive.
We consider the characteristic function $K_R$ of $R$ and we have a formula $\rho(x,y)$ such that :

if $K_R(a)=1$, then $T \vdash \rho(a,1)$

(for simplicity I'll consider a unary relation $R$ and I'll write $n$ both for the number and the corresponding numeral $S^n0$).
Then $a \in R$ if and only if $T \vdash \rho(a,1)$, since $T$ is consistent. 
By the machinery of arithmetization, we have a primitive recursive relation $Prv_T$ such that $Prv_T(l,m)$ holds iff $l$ "encode" a derivation $\phi_1,\ldots, \phi_k$ from $T$ such that $m=\ulcorner \phi_k \urcorner$.
Thus [see page 234] :

$K_R(a) =$ the "second component" of the least $s$ such that :

(i) $(s)_0$ encodes the input $a$; [...].


Then, $a \in R$ iff $K_R(a)=(\mu s)(Prv_T((s)_0, \ulcorner \rho(n,(s)_1) \urcorner))_1$.
The function id recursive beacuse $Prv_T$ is p.r. and the function $K_R$ uses minimization and $Subst$.
