1
$\begingroup$

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

  • 0
    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.2012-12-13

2 Answers 2

3

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

  • 0
    But ye$a$h, 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?2012-12-13
3

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

  • 0
    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))$2012-12-16