Is addition a sufficient operation?

For instance, multiplication can be viewed as 'repeated' addition, and powers repeated multiplication (at least for rational powers), hence powers can also be viewed as a more complicated repeated addition.

Similarly, subtraction is really addition of negative numbers, and with a bit of work, division can be viewed as a more complicated version of subtraction, and hence of addition.

How far can we take this?

Are there operations so intrinsically complicated/different from addition that an argument similar to the above wouldn't hold? No matter how sophisticated and complex we make addition?

That is, such operation cannot in principle be simplified down to a form of addition.

  • How would you simplify the composition of two isometries in $\mathbb{R}^3$ down to a form of addition? – Dietrich Burde Jun 3 '17 at 18:45
  • By performing arithmetics with the rules of the transformations defining them I'd say. e.g. if $f(x,y,z)=(x+a,y+b,z+c)$ and $g(x,y,z)=(x+d,y+e,z+f)$ you could compose a translation $h(x,y,z)=f(g(x,y,z))$ by adding the constants in these rules and get $h(x,y,z)=(x+a+d,y+b+e,z+c+f)$. – Stephen Jun 3 '17 at 19:00
up vote 3 down vote accepted

There is in fact an important sense in which addition is "sufficient" - namely, from the perspective of computability theory.

First, note that addition itself isn't the beginning of the road: addition is repeated successor $S(x)=x+1$. And in fact from the successor function and a few basic operations, we can build every computable function!

The computable functions account for all the functions that we can actually, well, compute; so in a very good sense addition lets us build every function (from naturals to naturals) that we'll ever use.


In fact, we can refine the above approach: by restricting the operations we use to build new functions from old, we can isolate interesting subclasses of the computable functions. For instance, replacing minimization (the $\mu$-operator) with a specific recursion scheme gives the primitive recursive functions. Primitive recursion is enough to build from successor all the way to exponentiation, and much further besides. However, it does not exhaust the computable functions. The Ackermann function is a particular computable function, generalizing the iterative process of going from successor to addition to multiplication to exponentiation to ..., which is not primitive recursive.

So in the sense of primitive recursion, addition is not sufficient to build everything. In fact, no single computable function is: given any computable $f$, there is some computable $g$ which is not primitive recursive relative to $f$. And indeed given any computable collection $\{f_i: i\in\mathbb{N}\}$ of computable functions, there is a computable function $g$ which is not primitive recursive relative to that whole collection. This can be proved via a diagonalization argument; and in fact, thinking about this argument in the context of the whole class of computable functions led Kleene to prove his recursion theorem.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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