Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Can addition be defined in terms of multiplication?
Replies: 58   Last Post: Aug 23, 2013 3:56 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Graham Cooper

Posts: 4,275
Registered: 5/20/10
Re: Can addition be defined in terms of multiplication?
Posted: Aug 20, 2013 5:11 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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


Date Subject Author
8/16/13
Read Can addition be defined in terms of multiplication?
Peter Percival
8/16/13
Read Re: Can addition be defined in terms of multiplication?
William Elliot
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/16/13
Read Re: Can addition be defined in terms of multiplication?
David C. Ullrich
8/16/13
Read Re: Can addition be defined in terms of multiplication?
namducnguyen
8/17/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/17/13
Read Re: Can addition be defined in terms of multiplication?
namducnguyen
8/17/13
Read Re: Can addition be defined in terms of multiplication?
fom
8/23/13
Read Re: Can addition be defined in terms of multiplication?
tommy1729_
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Robin Chapman
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Helmut Richter
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Rotwang
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Virgil
8/22/13
Read Re: Can addition be defined in terms of multiplication?
Rock Brentwood
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Shmuel (Seymour J.) Metz
8/17/13
Read Re: Can addition be defined in terms of multiplication?
Helmut Richter
8/16/13
Read Re: Can addition be defined in terms of multiplication?
Jim Burns
8/16/13
Read Re: Can addition be defined in terms of multiplication?
fom
8/17/13
Read Re: Can addition be defined in terms of multiplication?
Robin Chapman
8/17/13
Read Re: Can addition be defined in terms of multiplication?
fom
8/17/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/17/13
Read Re: Can addition be defined in terms of multiplication?
fom
8/17/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/17/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/18/13
Read Re: Can addition be defined in terms of multiplication?
William Elliot
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/18/13
Read Re: Can addition be defined in terms of multiplication?
William Elliot
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/18/13
Read Re: Can addition be defined in terms of multiplication?
David C. Ullrich
8/18/13
Read Re: Can addition be defined in terms of multiplication?
David C. Ullrich
8/17/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/18/13
Read Re: Can addition be defined in terms of multiplication?
David Bernier
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Ben Bacarisse
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Jim Burns
8/18/13
Read Re: Can addition be defined in terms of multiplication?
fom
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Ben Bacarisse
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/18/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/19/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/19/13
Read Re: Can addition be defined in terms of multiplication?
Alan Smaill
8/19/13
Read Re: Can addition be defined in terms of multiplication?
fom
8/19/13
Read Re: Can addition be defined in terms of multiplication?
Alan Smaill
8/20/13
Read Re: Can addition be defined in terms of multiplication?
Alan Smaill
8/20/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/20/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/20/13
Read Re: Can addition be defined in terms of multiplication?
Graham Cooper
8/22/13
Read Re: Can addition be defined in terms of multiplication?
David Libert
8/22/13
Read Re: Can addition be defined in terms of multiplication?
Peter Percival
8/20/13
Read Re: Can addition be defined in terms of multiplication?
fom

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.