Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"?

share|improve this question
Perhaps you're thinking of primitive recursive functions. –  Zhen Lin Dec 13 '12 at 15:00
Yes, perhaps now a button to "restate" the question might be nice, given that I know or recall a bit more now. Obviously if I edit it loads, it will make the ensuing answers that were helpful, look silly. –  John Smith Dec 13 '12 at 19:01
add comment

2 Answers

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

share|improve this answer
I'm aware of the proof that recursion is well defined for example: given f(0) and that f(n)=gf(n-1), prove by induction that for any natural number n, the first n "initial segments" that belong to your countably infinite sequence you are about to prove exists, and than take the set theoretic union over the natural numbers to obtain this sequence. –  John Smith Dec 13 '12 at 18:49
But yeah, that primitive recursive thing does sound like something I've heard before (but forgot). You start with constant functions, projections and the successor function. What simple functions on the naturals are arrived at in this way, and how do the standard "arithmetic functions" like addition, multiplication and so forth fit into it? –  John Smith Dec 13 '12 at 18:53
add comment

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$.

share|improve this answer
Yes that's the definition of addition I've seen before. I suppose my question Dan is how do addition and multiplication (and exponentiation and tetration etc.) fit into some general scheme of defining functions on the natural numbers in this way? Whatever "this way" is, of course. Perhaps it could be defined as primitive recursion on the natural numbers starting from successor, zero, and projections. –  John Smith Dec 13 '12 at 18:58
The construction I give for addition here implements the recursive definition given informally as: $x+1=s(x)$ and $x+s(y)=s(x+y)$. For multiplication, that would be: $x\times 1 = x$ and $x\times (y+1)=x\times y+x$ –  Dan Christensen Dec 15 '12 at 17:07
Having constructed the '+' function, for multiplication we would have: $\forall a(a\in S \leftrightarrow a\in \mathcal P(N^3) \wedge \forall b\in N((b,1,b)\in a)\wedge\forall b,c,d\in N ((b,c,d)\in a\rightarrow(b,c+1,d+b)\in a))$ –  Dan Christensen Dec 16 '12 at 4:23
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.