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 machine

and multiplication requiring a turing machine.

if it could multiply arbitrary length inputs it

could do other calculations with unbounded possible

outcomes and the halting problem would arise.

Herc