Arithmetic functions This may be a slightly vague question but if one defines a function (of some arity) recursively on the natural numbers, the "simplest" examples are things like addition, multiplication, or factorial. 
How do these functions fit into a general sense of defining recursively functions on the natural numbers? Starting only from the successor operator. 
What indeed exactly is an "arithmetic function"? 
 A: You need to be a bit more specific about what counts as defining a function recursively. You probably mean what is called, more carefully, a definition by primitive recursion, where e.g. we stipulate the value of $f(0)$ and then define $f(n + 1)$ in terms of the value of $f(n)$ using only already-defined functions. 
A techie aside: On some nice ways of defining what it is to define an $n + 1$ function (primitive)-recursively in its final argument, you'll need more that the successor function in your "starter pack" of functions if you are even to get addition -- you'll need the "projection functions" $I_k^n$ which take an $n$-tuple of arguments and return the $k$-th argument as value, and the zero function $Z(n)$ which always takes the value zero.
But these fine details apart, the functions that can be defined by a sequence of primitive recursive definitions starting from the successor function (and other trivia) are the primitive recursive functions -- i.e. the numerical functions that can be computed using just "for" loops without any open-ended searches.
For more, see e.g. the opening section of http://plato.stanford.edu/entries/recursive-functions/ or of course http://en.wikipedia.org/wiki/Primitive_recursive_function
A: An arithmetic function on $N$ can be seen as a subset of $N^3$. For a function $f$ of two variables on $N$ (like addition or multiplication), 
$\forall a,b,c ((a,b,c)\in f\rightarrow (a,b,c)\in N^3)$
$\forall a,b\in N\exists c\in N ((a,b,c)\in f)$
$\forall a,b,c,d\in N ((a,b,c)\in f\wedge (a,b,d)\in f\rightarrow c=d)$
If you want to construct the add function on $N$ using only the successor function $s$, you start by selecting a subset $S$ from $\mathcal P(N^3)$ such that:
$\forall a(a\in S \leftrightarrow a\in \mathcal P(N^3) \wedge \forall b\in N((b,1,s(b))\in a)\wedge\forall b,c,d\in N ((b,c,d)\in a\rightarrow(b,s(c),s(d))\in a))$  
Then the required add function (a subset of $N^3$) is just the intersection $\bigcap S$.
UPDATE
Alternatively, we can construct the set of ordered triples $add$ as follows:
$\forall x,y,z:[(x,y,z)\in add \iff (x,y,z)\in N^3$
$\land \forall a\subset \mathcal P(N^3):[\forall b\in N:[(b,0,b)\in a]\land \forall b,c,d:[(b,c,d)\in a \implies (b,s(c),s(d))\in a]$
$\implies (x,y,z)\in a]] $ 
Then you can prove that $add$ is a function such that:


*

*$\forall x\in N: add(x,0)=x$

*$\forall x,y \in N: add(x,s(y))=s(add(x,y))$
