```Date: Aug 20, 2013 5:11 AM
Author: Graham Cooper
Subject: Re: Can addition be defined in terms of multiplication?

On Tuesday, August 20, 2013 1:53:15 AM UTC-7, Peter Percival wrote:> Alan Smaill wrote:> > > fom <fomJUNK@nyms.net> writes:> > >> > >> On 8/19/2013 6:23 AM, Alan Smaill wrote:> > >>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:> > >>>> > >>>> William Elliot <marsh@panix.com> writes:> > >>>>> > >>>>> As Jim Burns said> > >>>>> 	z = x + y iff 2^z = 2^x * 2^y> > >>>>>> > >>>>> where 2^n is defined by induction 2^0 = 1, 2^1 = 1 and 2^(n+1) = 2*2^n> > >>>>> all of which can be done with Peano's axioms.> > >>>>> > >>>> Stepping out of my comfort zone here, but I think the point is that> > >>>> allowing recursive definitions makes the theory second-order, and raises> > >>>> the question of why one would not simply define + directly that way too.> > >>>>> > >>>> Broadly speaking, you can either have a second-order theory in which +> > >>>> and * and so on are not in the signature of the language (but are> > >>>> defined recursively) or you can have a first-order theory where + and *> > >>>> and so on are added to the signature, with axioms used to induce the> > >>>> usual meaning.> > >>>>> > >>>> I suspect Peter is talking about a first-order theory where recursive> > >>>> definitions are not permitted.> > >>>> > >>> I do too; it can be done, but it is not easy.> > >>>> > >>> See Goedel on defining exponentiation from plus and times via the> > >>> Chinese remainder theorem.> > >>>> > >>> > >> I have several volumes of the complete works.> > >>> > >> Do you have any more specific information on> > >> which paper?> > >> > > There is a formulation in the incompleteness theorem article.> > > he needed it to know that goedel numbers using exponentiation could> > > be defined inside arithmetic with plus and times.> > >> > > Versions of this use just FOL;> > > overview here:> > >> > >   http://math.stackexchange.com/questions/312891/how-is-exponentiation-defined-in-peano-arithmetic> > > > Which led me to > > http://math.stackexchange.com/questions/449146/why-are-addition-and-multiplication-included-in-the-signature-of-first-order-pea?rq=1 > > near the foot of which it says:> > > > Actually, more is known. Neither addition nor multiplication is > > definable from successor alone; multiplication is not definable from > > successor and addition; and addition is not definable from successor and > > multiplication. The theory of the natural numbers with multiplication > > and addition is undecidable, but the restriction to just addition is > > decidable, and the restriction with just multiplication is decidable.> > Probably due to Addition being possible on a finite state machineand multiplication requiring a turing machine.if it could multiply arbitrary length inputs itcould do other calculations with unbounded possibleoutcomes and the halting problem would arise.Herc
```