Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 Graham Cooper Posts: 4,417 Registered: 5/20/10
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 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
>
>
> 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 Peter Percival
8/16/13 William Elliot
8/16/13 Peter Percival
8/16/13 David C. Ullrich
8/16/13 namducnguyen
8/17/13 Peter Percival
8/17/13 namducnguyen
8/17/13 fom
8/23/13 tommy1729_
8/16/13 Peter Percival
8/16/13 Robin Chapman
8/16/13 Helmut Richter
8/16/13 Rotwang
8/16/13 Virgil
8/22/13 Rock Brentwood
8/16/13 Shmuel (Seymour J.) Metz
8/17/13 Helmut Richter
8/16/13 Jim Burns
8/16/13 fom
8/17/13 Robin Chapman
8/17/13 fom
8/17/13 Peter Percival
8/17/13 fom
8/17/13 Peter Percival
8/17/13 Peter Percival
8/18/13 William Elliot
8/18/13 Peter Percival
8/18/13 William Elliot
8/18/13 Peter Percival
8/18/13 Graham Cooper
8/18/13 David C. Ullrich
8/18/13 David C. Ullrich
8/17/13 Graham Cooper
8/18/13 David Bernier
8/18/13 Ben Bacarisse
8/18/13 Peter Percival
8/18/13 Jim Burns
8/18/13 fom
8/18/13 Ben Bacarisse
8/18/13 Graham Cooper
8/18/13 Graham Cooper
8/18/13 Graham Cooper
8/18/13 Graham Cooper
8/19/13 Graham Cooper
8/19/13 Alan Smaill
8/19/13 fom
8/19/13 Alan Smaill
8/20/13 Alan Smaill
8/20/13 Peter Percival
8/20/13 Graham Cooper
8/20/13 Graham Cooper
8/22/13 David Libert
8/22/13 Peter Percival
8/20/13 fom