Can you define an addition for natural numbers with the associativity property?

251 Views Asked by At

Using the Peano axioms for defining the natural numbers with the successor function $x \mapsto (x)'$, the usual way of defining an addition goes as follows

(1) For all $n \in N$, $n + 1 = (n)'$.

(2) For all $n, m \in N$, $n + (m)' = (n + m)'$

Could you instead of (2) also say (2)'?

(2)' For all $n, m, p \in N$, $(n + m) + p = n + (m + p)$

For example, using only (1) one can find that $2+2 = (1 + 1) + (1+1)$. With (2)', we can then say that $2+2 = ((1 + 1) + 1)+1$. Using only (1) again, we find that $2+2 = 1''' = 4$.

1

There are 1 best solutions below

3
On

You can certainly take axiom (2)' as an alternative to (2). However, if you wanted to construct a model of the Peano axioms (e.g., in the theory of sets), proving the consistency of axiom (2)' would involve more work than axiom (2). (In fact, you'd probably end up proving that axiom (2) was consistent and then deriving the consistency of axiom (2)' from that.)

[Aside: with over a century of hindsight, the Peano axioms should perhaps be refactored. To me, what they say is that $\Bbb{N}$ under addition is the free abelian monoid on one generator $1$ (which a computer scientist might think of as the initial algebra for the signature $(\Bbb{N}, 0, (\cdot)')$ and represent as finite lists of $0$ ore more $1$s). However. "free" and "initial algebra" are not first-order properties, we need to the abelian monoid axioms not only the first-order axioms: $$ 1 \neq 0 \\ \forall x(a + x = b + x \Rightarrow a = b)\\ $$ but also the first-order axiom schemata: $$ P(0) \land (\forall x \cdot P(x) \Rightarrow P(x + 1)) \Rightarrow (\forall x\cdot P(x)) $$ where $P$ stands for an arbitrary formula.]