11

Through recursion, inversion, extension and all kinds of simple shenanigans the successor function leads to definitions of $+, \cdot, /, x^k, \exp, \sin, \partial, \int$ and other special functions. It seems to have uncanny utility. In particular, this set of functions happens to permit concise description of physics.

I ask, is this merely the result of directions math took in our history, or is there really something profound about $+$? Is $\mathbb N$ hard coded somewhere in the ZF axioms, or in the logic used to describe them? Among the uncountably many other functions, could there be another one, which is not trivially derived form $+$ but could match its utility?

Karolis Juodelė
  • 9,702
  • 1
  • 25
  • 39
  • 1
    Now, I suspect that it might be, not $+$ but $\mathbb N$ that's special. But the question remains. Out of all groups, could there be a more useful one? – Karolis Juodelė Apr 02 '14 at 16:55
  • 1
    I think you meant "many other $\mathbb{N}^2\rightarrow \mathbb{N}$". – Marra Apr 02 '14 at 16:56
  • @Marra Unless he meant the unary $+$ which I doubt because of the context. – user2345215 Apr 02 '14 at 16:57
  • 1
    I guess because deep down, math is just about counting? And $+$ is the most fundamental counting operations(totalling two counts?) – Guy Apr 02 '14 at 16:58
  • 2
    Don't think about it as an operator on natural numbers. Think about it as the cardinality of the union of $2$ sets, which is a very basic notion. – user2345215 Apr 02 '14 at 16:59
  • 4
    I suppose really the successor function is at the bottom of the hierarchy as it is part of the definition of the natural numbers in the Peano framework (and addition is defined in terms of the successor function). As such, the foundation of arithmetic via the Peano axioms is probably the explanation you're looking for. – Dan Rust Apr 02 '14 at 17:07
  • I am with @DanielRust in this one. – Marra Apr 02 '14 at 17:16
  • As I posted my answer below, @DanielRust's spot-on comment appeared. I'll leave my long-winded version up for what it is worth. – Peter Smith Apr 02 '14 at 17:19
  • @PeterSmith Your answer explains the point well. Succession (and hence addition) is built into the natural numbers at a fundamentally basic level, and so as arithmetic is built up from the definition of the natural numbers, it stands to reason that subsequent definitions would be given in terms of these objects. – Dan Rust Apr 02 '14 at 17:33

2 Answers2

3

In what sense is multiplication defined in terms of addition? Note, for example, that multiplication can't be defined in the first-order theory of addition.

We only get such a definition of multiplication from addition if we go second-order. But then, if we do go second-order, addition too is definable, in terms of successor.

Now, you might ask in the same spirit as the OP: why does the successor function have such an "uncanny utility" among all the numerical functions, that so many functions (addition, multiplication, exponentiation, superexponentiation, factorial, etc. etc.) can be defined in terms of it, in a second-order framework?

But there is something very odd about that question, as if we can first grasp what is involved in talking of the natural numbers, and then wonder "why is successor special?". That makes no sense. To grasp a structure as a natural number structure just is to grasp it as structured by being generated a successor function from an initial number (there is a zero, a unique next number, a unique next number, etc., without repetitions). The unique role of the successor function together with the unique role of the initial number is what makes the natural numbers the natural numbers (up to isomorphism).

Peter Smith
  • 54,743
  • I do mean second order and I really should have formulated my question in terms of $x \mapsto x+1$ or $\mathbb{N}$ itself. The question remains though. Why is $\mathbb N$ more useful than an arbitrary algebraic structure? Would it be possible to describe the word with something completely different? – Karolis Juodelė Apr 02 '14 at 17:31
  • I've edited the question to clarify that I consider successor function, $+$, and $\mathbb N$ to be inseparable and to represent the same concept. – Karolis Juodelė Apr 19 '14 at 06:26
3

$\mathbb{N}$ is "hard-coded" into logic: logical expressions are strings of symbols, and strings have lengths.

The theories of Peano arithmetic and string processing are essentially the same: with string processing, you can do arithmetic with lookup-tables and pushing symbols around. With Peano arithmetic, you can encode strings as digits of numbers.

An example of how this enters the picture can be seen with recursion. If you have an element $a$ of some set, and a function $f$ on that set, then you can talk about repeatedly applying $f$ to $a$. All of the expressions you can get look like $a, fa, ffa, fffa, \ldots$.

The individual terms can be labelled with natural numbers, counting how many $f$'s appear in the arithmetic expression.

  • So you're saying that any model described in logic would have a special place for $\mathbb N$. Possibly because the set of true statements is $\mathsf {RE}$. Do you have ideas why this would matter to physical laws? – Karolis Juodelė Apr 19 '14 at 06:46