A recursive function on $\mathbb{N}$ can be defined as follows:
Given an element $a \in \mathbb{N}$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we can define a function $g:\mathbb{N}\rightarrow\mathbb{N}$ as follows:
- $g(0) = a$
- $g(n+1) = f(g(n))$
The fact that $g$ exists and is unique can be proved using the Recursion Theorem in set theory.
My understanding is that in Peano Arithmetic, it is possible prove the existence of exponentiation using just addition and multiplication, but is it true for any recursively defined function?
In other words, is the existence of addition and multiplication strong enough to prove the existence of any recursive function? i.e can the Recursion Theorem be proved using the Peano Axioms (including addition and multiplication)?
Update: Since the answers below indicate that this is true, I am looking for an outline of a proof or a reference that shows that addition and multiplication are powerful enough to define any recursive function.
$PA$ can indeed prove the recursion theorem, although it's a bit of work to formalize it properly since $PA$ doesn't talk directly about functions. It's much better to work in the theory $ACA_0$, a conservative two-sorted extension of $PA$ which does talk directly about functions.
However, this isn't really the end of the story. It's not that $ACA_0$ proves the existence of exponentiation, but rather that PA proves the totality of exponentiation. And, in fact, $ACA_0$ does not prove the totality of every recursive function! This is a somewhat different issue, and I suspect that this is what you are really interested in.