
Re: Can addition be defined in terms of multiplication?
Posted:
Aug 20, 2013 5:11 AM


On Tuesday, August 20, 2013 1:53:15 AM UTC7, 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 secondorder, and raises > > >>>> the question of why one would not simply define + directly that way too. > > >>>> > > >>>> Broadly speaking, you can either have a secondorder theory in which + > > >>>> and * and so on are not in the signature of the language (but are > > >>>> defined recursively) or you can have a firstorder 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 firstorder 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/howisexponentiationdefinedinpeanoarithmetic > > > > Which led me to > > http://math.stackexchange.com/questions/449146/whyareadditionandmultiplicationincludedinthesignatureoffirstorderpea?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

