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

-
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

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

-
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

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:

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

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

-
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