Can addition be defined in terms of multiplication?

[Peter Percival]

Can addition be defined in terms of multiplication? I.e., is there a
formula in the language of arithmetic

x + y = z <-> ...

such that in '...' any of the symbols of arithmetic except + may occur?
Or, alternatively, is there a formula in the language of arithmetic

x + y = ...

with the same requirement?

The symbols of arithmetic (for the purpose of this question) are either

individual variables, (classical) logical constants including =,
S, +, *, and punctuation marks;

or the above with < as an additional binary predicate symbol.

--
Sorrow in all lands, and grievous omens.
Great anger in the dragon of the hills,
And silent now the earth's green oracles
That will not speak again of innocence.
David Sutton -- Geomancies

[William Elliot]

On Fri, 16 Aug 2013, Peter Percival wrote:

> Can addition be defined in terms of multiplication? I.e., is there a formula
> in the language of arithmetic
>
> x + y = z <-> ...
>
> such that in '...' any of the symbols of arithmetic except + may occur? Or,
> alternatively, is there a formula in the language of arithmetic
>
> x + y = ...
>
> with the same requirement?

x + y = log(e^x * e^y)

[Peter Percival]

William Elliot wrote:
> On Fri, 16 Aug 2013, Peter Percival wrote:
>
>> Can addition be defined in terms of multiplication? I.e., is there a formula
>> in the language of arithmetic
>>
>> x + y = z <-> ...
>>
>> such that in '...' any of the symbols of arithmetic except + may occur? Or,
>> alternatively, is there a formula in the language of arithmetic
>>
>> x + y = ...
>>
>> with the same requirement?
>
> x + y = log(e^x * e^y)

Er... yes...

>> The symbols of arithmetic (for the purpose of this question) are either
>>
>> individual variables, (classical) logical constants including =,
>> S, +, *, and punctuation marks;
>>
>> or the above with < as an additional binary predicate symbol.
>>

[Peter Percival]

Peter Percival wrote:
> Can addition be defined in terms of multiplication? I.e., is there a
> formula in the language of arithmetic
>
> x + y = z <-> ...
>
> such that in '...' any of the symbols of arithmetic except + may occur?
> Or, alternatively, is there a formula in the language of arithmetic
>
> x + y = ...
>
> with the same requirement?
>
> The symbols of arithmetic (for the purpose of this question) are either
>
> individual variables, (classical) logical constants including =,
> S, +, *, and punctuation marks;

That might have been worded better. How about

individual variables; (classical) logical constants including =;
non-logical constants S, + and *; and punctuation marks.

? English is not my strong point... lists within lists... mutter mutter.

[Robin Chapman]

On 16/08/2013 09:54, Peter Percival wrote:
> Can addition be defined in terms of multiplication? I.e., is there a
> formula in the language of arithmetic
>
> x + y = z <-> ...
>
> such that in '...' any of the symbols of arithmetic except + may occur?
> Or, alternatively, is there a formula in the language of arithmetic
>
> x + y = ...
>
> with the same requirement?
>
> The symbols of arithmetic (for the purpose of this question) are either
>
> individual variables, (classical) logical constants including =,
> S, +, *, and punctuation marks;
>
> or the above with < as an additional binary predicate symbol.

IIRC "arithmetic without addition" is a decidable theory
(of course Presburger's famous theorem is that "arithmetic
without multiplication" is decidable). I think this means that
the theory of the language (0,1,*,=) in N is decidable. I'm not
sure if we can allow S and/or <.

Of course if we have a language like this with a decidable theory, then
we can't define addition, lest the full theory of Peano arithmetic
be decidable.

[dull...@sprynet.com]

On Fri, 16 Aug 2013 02:05:09 -0700, William Elliot <ma...@panix.com>
wrote:

>On Fri, 16 Aug 2013, Peter Percival wrote:
>
>> Can addition be defined in terms of multiplication? I.e., is there a formula
>> in the language of arithmetic
>>
>> x + y = z <-> ...
>>
>> such that in '...' any of the symbols of arithmetic except + may occur? Or,
>> alternatively, is there a formula in the language of arithmetic
>>
>> x + y = ...
>>
>> with the same requirement?
>
>x + y = log(e^x * e^y)

If you don't know what "in the language of arithmetic" means
it would be a good idea to refrain from answering questions
about the language of arithmetic, lest you look silly.

[Helmut Richter]

On Fri, 16 Aug 2013, Robin Chapman wrote:

> On 16/08/2013 09:54, Peter Percival wrote:
> > Can addition be defined in terms of multiplication? I.e., is there a
> > formula in the language of arithmetic
> >
> > x + y = z <-> ...
> >
> > such that in '...' any of the symbols of arithmetic except + may occur?
> > Or, alternatively, is there a formula in the language of arithmetic
> >
> > x + y = ...
> >
> > with the same requirement?

A similar problem I have asked some years ago is the following:

Given a multiplication on a set (e.g. defined as a commutative and
associative operation allowing cancellation (ab = ac implies b = c)),
is there an addition so that the set becomes a ring with both operations?
I have no clue how to tackle such questions.

An example: Let M = {x elem Z : x == 1 mod 3} with ordinary
multiplication. Could this be the multiplication in a ring, if addition is
suitably defined? I guess, no, but it is but a guess.

> IIRC "arithmetic without addition" is a decidable theory
> (of course Presburger's famous theorem is that "arithmetic
> without multiplication" is decidable). I think this means that
> the theory of the language (0,1,*,=) in N is decidable. I'm not
> sure if we can allow S and/or <.
>
> Of course if we have a language like this with a decidable theory, then
> we can't define addition, lest the full theory of Peano arithmetic
> be decidable.

I'll look into this argument a bit closer.

--
Helmut Richter

[Rotwang]

On 16/08/2013 17:14, Helmut Richter wrote:
> [...]

>
> A similar problem I have asked some years ago is the following:
>
> Given a multiplication on a set (e.g. defined as a commutative and
> associative operation allowing cancellation (ab = ac implies b = c)),
> is there an addition so that the set becomes a ring with both operations?
> I have no clue how to tackle such questions.
>
> An example: Let M = {x elem Z : x == 1 mod 3} with ordinary
> multiplication. Could this be the multiplication in a ring, if addition is
> suitably defined? I guess, no, but it is but a guess.

I think the answer is no. Note that in any ring,

x.0 = x.0 + (x.x - x.x)
= x.(0 + x) - x.x
= x.x - x.x = 0

So if M with ordinary multiplication could be extended to a ring, there
would be an element of M which multiplied by every other element to give
itself. No such element exists (since if e.g. x.4 = x then x = 0).

[Virgil]

On 16/08/2013 17:14, Helmut Richter wrote:
> [...]
>
> A similar problem I have asked some years ago is the following:
>
> Given a multiplication on a set (e.g. defined as a commutative and
> associative operation allowing cancellation (ab = ac implies b = c)),
> is there an addition so that the set becomes a ring with both operations?
> I have no clue how to tackle such questions.

In rings, ab = ac need not necessarily imply b = c.

It requires, in addition, at least that both ab and ac be nonzero.

Note that in the ring of integers modulo 16
one has
8*2 = 8*4 = 0
but not
2 = 4
--

[Jim Burns]

On 8/16/2013 4:54 AM, Peter Percival wrote:
> Can addition be defined in terms of multiplication? I.e.,
> is there a formula in the language of arithmetic
>
> x + y = z <-> ...
>
> such that in '...' any of the symbols of arithmetic
> except + may occur? Or, alternatively, is there a
> formula in the language of arithmetic
>
> x + y = ...
>
> with the same requirement?
>
> The symbols of arithmetic (for the purpose of this question) are either
>
> individual variables, (classical) logical constants including =,
> S, +, *, and punctuation marks;
>
> or the above with < as an additional binary predicate symbol.

How about

x + y = z <-> 2^x * 2^y = 2^z

where 2^x is just an abbreviation for the function 2pwr: N -> N,
defined by
2pwr(0) = 1

2pwr( Sx ) = 2 * 2pwr( x )

It's true that I use the successor S, which I hear implicitly
uses addition, but without S I don't see how to do much of
anything at all.

I wonder how Nam defines * without using either + or S.

Come to think of it, if I can use S, why can't I just
go ahead and define + in the usual (so far as I know) fashion
x + 0 = x

x + Sy = S(x + y)

It seems to me that, if one is going to do arithmetic
without addition, unique prime factorization becomes central.
It might be useful to represent numbers by their prime exponents,
so that
3 * 4 = 12
becomes
( 0, 1, ...) * ( 2, 0, ...) = ( 2, 1, ...)
with special rules for 0, of course. It looks like countably
many copies of N, with only finite many copies non-zero.
Each copy has its own successor function S2(x) = 2*x,
S3(x) = 3*x, ...

However, I am daunted by the prospect of defining * in
this system. We would need to give rules that explain why
3 + 4 = 7
or, rather, why
( 0, 1, 0, 0, ...) + ( 2, 0, 0, 0, ...) = ( 0, 0, 0, 1, ...)

[Shmuel Metz]

In <alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de>, on
08/16/2013

at 06:14 PM, Helmut Richter <hh...@web.de> said:

>Given a multiplication on a set (e.g. defined as a commutative
>and associative operation allowing cancellation (ab = ac implies
>b=c)),

That would be a strange definition in general, although it's
reasonable if you're only concerned with groups. Is the "*" operation
in Z a multiplication? Certainly 0b=0c doesn't imply b=c.

--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>

Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org

[fom]

I have not really developed my ideas in this area much. However,
while trying to consider certain alternative interpretations for
some sentences in which I had been interested, I came up with the
following:

--------------------------------

AxAy(xcy <-> (Az(ycz -> xcz) /\ Ez(xcz /\ -ycz)))

may be interpreted as "x is a proper divisor of y"
and

AxAy(xey <-> (Az(ycz -> xez) /\ Ez(xez /\ -ycz)))

may be interpreted as "x is a prime
divisor of y".

--------------------------------

The idea here, of course, is to begin with respect to aliquot
parts (a proper part relation is irreflexive and transitive).

Because of relatively simple analogous constructions discussed
in Ian Fleming's "Combinatorics of Finite Sets" the only model for
these sentences which I have considered are the natural numbers
with no squares (powers) in their prime decompositions.

The sentence which distinguishes interpretation of the predicates
is

AxAy((Az(ycz -> xez) /\ Ez(xez /\ -ycz)) -> Az((xez /\ -ycz) ->
(-(Ew(wey /\ -xew) <-> Aw(xcw <-> ycw)))))

or, more simply,

AxAy(xey -> Az((xez /\ -ycz) -> (-(Ew(wey /\ -xew) <-> Aw(xcw <-> ycw)))))


As I said, I have not really thought about this except with
respect to a very simple model for the purpose of alternative
interpretation.

The material in Fleming's book that influenced the restriction
on the model is the fact that the poset of subsets of an n-set
can be considered as the poset of divisors of square-free numbers
under division. So, from the point of view of set theory,
this would be the relevant case for comparison.

I have begun thinking about developing this for a theory of
arithmetic. But, I am not an arithmetician. Heck, I am not
even a mathematician. :-)

Beginning with divisors is a bit different from what you had
in mind. But, given your statement, I thought I would throw
this into the mix.

<snip>

[Nam Nguyen]

On 16/08/2013 9:49 AM, dull...@sprynet.com wrote:
> On Fri, 16 Aug 2013 02:05:09 -0700, William Elliot <ma...@panix.com>
> wrote:
>
>> On Fri, 16 Aug 2013, Peter Percival wrote:
>>
>>> Can addition be defined in terms of multiplication? I.e., is there a formula
>>> in the language of arithmetic
>>>
>>> x + y = z <-> ...
>>>
>>> such that in '...' any of the symbols of arithmetic except + may occur? Or,
>>> alternatively, is there a formula in the language of arithmetic
>>>
>>> x + y = ...
>>>
>>> with the same requirement?
>>
>> x + y = log(e^x * e^y)
>
> If you don't know what "in the language of arithmetic" means
> it would be a good idea to refrain from answering questions
> about the language of arithmetic, lest you look silly.

_That_ actually isn't silly. The language of arithmetic is either
L1(0,S,+,*,<) or L2(0,S,+,*), so "in the language of arithmetic"
technically just means "in L1" or "in L2".

What is really ... really silly is the fact whatever "in the language
of arithmetic" is _supposed to MEAN_ is basically negated, destroyed,
by the upward LST.

--
-----------------------------------------------------
There is no remainder in the mathematics of infinity.

NYOGEN SENZAKI

[Peter Percival]

Jim Burns wrote:

>
> I wonder how Nam defines * without using either + or S.

It is undefined in the theory that Shoenfield calls N, which is
Robinson's Q.

> Come to think of it, if I can use S, why can't I just
> go ahead and define + in the usual (so far as I know) fashion
> x + 0 = x
>
> x + Sy = S(x + y)
>
> It seems to me that, if one is going to do arithmetic
> without addition, unique prime factorization becomes central.
> It might be useful to represent numbers by their prime exponents,
> so that
> 3 * 4 = 12
> becomes
> ( 0, 1, ...) * ( 2, 0, ...) = ( 2, 1, ...)
> with special rules for 0, of course. It looks like countably
> many copies of N, with only finite many copies non-zero.
> Each copy has its own successor function S2(x) = 2*x,
> S3(x) = 3*x, ...
>
> However, I am daunted by the prospect of defining * in
> this system. We would need to give rules that explain why
> 3 + 4 = 7
> or, rather, why
> ( 0, 1, 0, 0, ...) + ( 2, 0, 0, 0, ...) = ( 0, 0, 0, 1, ...)
>
>
>

[Peter Percival]

Nam Nguyen wrote:
> On 16/08/2013 9:49 AM, dull...@sprynet.com wrote:
>> On Fri, 16 Aug 2013 02:05:09 -0700, William Elliot <ma...@panix.com>
>> wrote:

>>> x + y = log(e^x * e^y)
>>
>> If you don't know what "in the language of arithmetic" means
>> it would be a good idea to refrain from answering questions
>> about the language of arithmetic, lest you look silly.
>
> _That_ actually isn't silly. The language of arithmetic is either
> L1(0,S,+,*,<) or L2(0,S,+,*), so "in the language of arithmetic"
> technically just means "in L1" or "in L2".

So given the language of arithmetic is what you say, it isn't silly to
use log and exp? Note that my post spelled out your L1 and L2.

[Peter Percival]

Jim Burns wrote:
> On 8/16/2013 4:54 AM, Peter Percival wrote:
>> Can addition be defined in terms of multiplication? I.e.,
>> is there a formula in the language of arithmetic
>>
>> x + y = z <-> ...
>>
>> such that in '...' any of the symbols of arithmetic
>> except + may occur? Or, alternatively, is there a
>> formula in the language of arithmetic
>>
>> x + y = ...
>>
>> with the same requirement?
>>
>> The symbols of arithmetic (for the purpose of this question) are either
>>
>> individual variables, (classical) logical constants including =,
>> S, +, *, and punctuation marks;
>>
>> or the above with < as an additional binary predicate symbol.
>
> How about
>
> x + y = z <-> 2^x * 2^y = 2^z
>
> where 2^x is just an abbreviation for the function 2pwr: N -> N,
> defined by
> 2pwr(0) = 1
>
> 2pwr( Sx ) = 2 * 2pwr( x )

That goes beyond what I defined as the language of arithmetic.

[Nam Nguyen]

On 17/08/2013 1:06 AM, Peter Percival wrote:
> Nam Nguyen wrote:
>> On 16/08/2013 9:49 AM, dull...@sprynet.com wrote:
>>> On Fri, 16 Aug 2013 02:05:09 -0700, William Elliot <ma...@panix.com>
>>> wrote:
>
>>>> x + y = log(e^x * e^y)
>>>
>>> If you don't know what "in the language of arithmetic" means
>>> it would be a good idea to refrain from answering questions
>>> about the language of arithmetic, lest you look silly.
>>
>> _That_ actually isn't silly. The language of arithmetic is either
>> L1(0,S,+,*,<) or L2(0,S,+,*), so "in the language of arithmetic"
>> technically just means "in L1" or "in L2".
>
> So given the language of arithmetic is what you say, it isn't silly to
> use log and exp?

No. Take the "language of arithmetic" to be L1 (for example): you can
formalize a real number system for log and exp.

My point is it's silly to claim L1 to be the "language of arithmetic"
while it could also be the "the language of complete order field", or
many ... many other alternatives.

That's just shows how we've _unjustifiably biased_ our logical
reasoning, in favor of the concept of the natural numbers.

> Note that my post spelled out your L1 and L2.

(I only glanced through the conversation between Dave and William).

[fom]

On 8/17/2013 9:56 AM, Nam Nguyen wrote:
> On 17/08/2013 1:06 AM, Peter Percival wrote:
>> Nam Nguyen wrote:
>>> On 16/08/2013 9:49 AM, dull...@sprynet.com wrote:
>>>> On Fri, 16 Aug 2013 02:05:09 -0700, William Elliot <ma...@panix.com>
>>>> wrote:
>>
>>>>> x + y = log(e^x * e^y)
>>>>
>>>> If you don't know what "in the language of arithmetic" means
>>>> it would be a good idea to refrain from answering questions
>>>> about the language of arithmetic, lest you look silly.
>>>
>>> _That_ actually isn't silly. The language of arithmetic is either
>>> L1(0,S,+,*,<) or L2(0,S,+,*), so "in the language of arithmetic"
>>> technically just means "in L1" or "in L2".
>>
>> So given the language of arithmetic is what you say, it isn't silly to
>> use log and exp?
>
> No. Take the "language of arithmetic" to be L1 (for example): you can
> formalize a real number system for log and exp.
>
> My point is it's silly to claim L1 to be the "language of arithmetic"
> while it could also be the "the language of complete order field", or
> many ... many other alternatives.
>

That may be so. However, the notion arises from universal algebra.

What one actually has is

"The theory of arithmetic"

"The language of the theory of arithmetic"

"The model of the language of the theory of arithmetic"

Tarski's 1933 specifically excludes consideration of
scientific languages built up from definition.

Apparently, Hilbert and Bernays demonstrated the eliminability
of definite descriptions (the syntax associated with defined
individual constants). Presuming that Kleene has represented
the argument faithfully, the requirements for obtaining reducts
can be found in "Introduction to Metamathematics". There
is a provability requirement.

When a theory is given axiomatically, its language is the alphabet
of symbols which are neither punctuation nor logical constants.

It is merely a list of symbols.

It is typed according to a list of ordered pairs which associate
an arity with each of the symbols.

It is significant that Chang and Keisler describe model theory
as

(universal algebra) + (logic)

to express the idea that algebraic structures which focus
primarily on operations (functions) and constants are extended
to include relations.

[Helmut Richter]

On Fri, 16 Aug 2013, Shmuel (Seymour J.) Metz wrote:

> In <alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de>, on
> 08/16/2013
> at 06:14 PM, Helmut Richter <hh...@web.de> said:
>
> >Given a multiplication on a set (e.g. defined as a commutative
> >and associative operation allowing cancellation (ab = ac implies
> >b=c)),
>
> That would be a strange definition in general, although it's
> reasonable if you're only concerned with groups. Is the "*" operation
> in Z a multiplication? Certainly 0b=0c doesn't imply b=c.

I was imprecise in stating the problem. Of course, it was meant in a way so
that it *can* have solutions, e.g. the ordinary multiplication of integers is
indeed the multiplication in a ring. Let me try to do better:

Given a structure (M, 0, 1, ￜ) where

M is a set,
0 elem M is a constant,
1 elem M is a constant,
ￜ : MￜM -> M is an operation

with the following properties:

(1) ￜ is commutative and associative
(2) 0ï¿œx = 0 for all x
(3) 1ï¿œx = x for all x
(4) xￜz = yￜz and z ￜ= 0 ==> x = y for all x, y, z

where condition (4) comes from the first intended application of the problem;
the problem may be meaningful also without it. Condition (4) is not generally
fulfilled in rings.

Now we want to decide the question whether there is an operation + so that
(M, 0, 1, +, ￜ) is a ring.

Example 1: M = {0, 1, 2, 3, 4}
If x, y ￜ= 0, xￜy is the unique z in {1, 2, 3, 4} such that
x+y-1 == z (mod 4)

Then there is an addition which makes it a ring, even a field:
1+1=2; 1+3=0; 1+4=3; 2+2=3; 2+3=1; 2+4=0; 3+3=4; 3+4=2; 4+4=1;

because {1, 2, 3, 4} is a group under ￜ that is isomorphic to the
multiplicative group of F5, and the isomorphism consists of swapping 3 and 4.


Example 2: M = {0} u {x elem Z: x == 1 (mod 3)}
xï¿œy is defined as ordinary multiplication

Question: Is there an addition which makes that a ring? Or why not?

--
Helmut Richter

[William Elliot]

> Jim Burns wrote:
> > On 8/16/2013 4:54 AM, Peter Percival wrote:

> > > Can addition be defined in terms of multiplication? I.e.,
> > > is there a formula in the language of arithmetic
> > > x + y = z <-> ...
> > >
> > > such that in '...' any of the symbols of arithmetic
> > > except + may occur?
> > >

> > > The symbols of arithmetic (for the purpose of this question) are either
> > > individual variables, (classical) logical constants including =,
> > > S, +, *, and punctuation marks;
> > > or the above with < as an additional binary predicate symbol.
> >
> > How about
> > x + y = z <-> 2^x * 2^y = 2^z
> >
> > where 2^x is just an abbreviation for the function 2pwr: N -> N,
> > defined by
> > 2pwr(0) = 1
> > 2pwr( Sx ) = 2 * 2pwr( x )
> That goes beyond what I defined as the language of arithmetic.

It does not. It quite definable with Peano's axioms
which may be presumed to be what you intend because
of the inclusion of S in the symbols of arithematic.

If you want it for the reals, then 2^x, x in is
definable with <= and a whole lot of logical overhand.

[Peter Percival]

Then I think the onus is on you to produced definitions in one or both
of these forms:

x + y = ...

x + y = z <-> ...

where the only non-logical symbols (baring punctuation) in the ... are
from this set: {*,S,0} or this set: {*,S,0,<}. I wouldn't be surprised
if + can be defined (in the way requested) from {*,S,0} or {*,S,0,<} but
I would like either to see it spelt out, or to be given a reference.

>
> If you want it for the reals,

Which I don't.

> then 2^x, x in is
> definable with <= and a whole lot of logical overhand.
>

[William Elliot]

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.

[Peter Percival]

And the magic formulae

2^x = ...

2^x = y <-> ...

are what in the languages {*,S,0} or {*,S,0,<}?

>>> If you want it for the reals,
>>
>> Which I don't.
>>
>>> then 2^x, x in is
>>> definable with <= and a whole lot of logical overhand.
>

[Ben Bacarisse]

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.

<snip>
--
Ben.

[Peter Percival]

Yes, I am. Sorry for not mentioning it. The definitions that I seek
will be eliminable.

[Jim Burns]

Does "first order theory" mean no recursive definitions or
no recursion at all?

I have grown used to gliding past the logical implications of
definitions, assuming (possibly incorrectly) that there were
no *logical* implications, that they were solely a matter of
convenience for the writer and reader -- although a very
important matter of enormous convenience in practice,
making the otherwise incomprehensible comprehensible.
How wrong am I?

It seems to me that one is very limited in what one can do
without recursion. It might well be possible to prove that
Goldbach's Conjecture or the similar Nam's Conjecture is
unprovable in such a system (though one may have to use
recursion to prove that).

[dull...@sprynet.com]

On Sun, 18 Aug 2013 02:18:14 -0700, William Elliot <ma...@panix.com>
wrote:

>> Jim Burns wrote:
>> > On 8/16/2013 4:54 AM, Peter Percival wrote:
>
>> > > Can addition be defined in terms of multiplication? I.e.,
>> > > is there a formula in the language of arithmetic
>> > > x + y = z <-> ...
>> > >
>> > > such that in '...' any of the symbols of arithmetic
>> > > except + may occur?
>> > >
>> > > The symbols of arithmetic (for the purpose of this question) are either
>> > > individual variables, (classical) logical constants including =,
>> > > S, +, *, and punctuation marks;
>> > > or the above with < as an additional binary predicate symbol.
>> >
>> > How about
>> > x + y = z <-> 2^x * 2^y = 2^z
>> >
>> > where 2^x is just an abbreviation for the function 2pwr: N -> N,
>> > defined by
>> > 2pwr(0) = 1
>> > 2pwr( Sx ) = 2 * 2pwr( x )
>> That goes beyond what I defined as the language of arithmetic.
>
>It does not.

It does.

>It quite definable with Peano's axioms
>which may be presumed to be what you intend because
>of the inclusion of S in the symbols of arithematic.

You simply don't know what "a definition in the language
of arithmetic" means. But don't let that stop you.

[dull...@sprynet.com]

On Sun, 18 Aug 2013 03:09:00 -0700, William Elliot <ma...@panix.com>
wrote:

Yes. Now give a defintion of 2^n _in the language of arithmetic_.

[Ben Bacarisse]

No, but it means a weaker induction axiom than the one usually used in a
second-order theory. At this point you bump up hard against my
knowledge boundary and I can't really say much more about it.

I should pass on the rest. Someone Who Knows will come along clear it
up, I hope.

<snip>
--
Ben.

[fom]

You can find a discussion of defined symbol eliminability
in Kleene's "Introduction to Metamathematics". There are
certain provability requirements which must be met.

I suppose the question of "logical" implications would
depend on how you view "logic".

Obviously, definitions for the purpose of a particular
problem domain are stipulative and convenient. The question
of a logical foundation, however, will trace the hypothetical assertions
of theorems backward to minimal sets of common
premises. Similarly, the principal of non-circularity will
permits tracing defined symbols backward to language primitives
which cannot be eliminated through substitution.

Since the deductive calculus does not introduce symbols
other than variables (x=x is an instance of the axioms
of identity introducing a term into a proof -- as in
"Fix x" or "Let x be..."), the language of a theory are
the symbols different from the logical constants (and
punctuation) which appear in the sentences through which
the theory is expressed.

If one begins with a given theory and the language determined
by the alphabet of symbols in its given assertions, then
introducing a symbol with a definition is a *new* language.

Here is an explanatory excerpt from Hodges' "Model
Theory" concerning the extension of a language with
constant symbols:

"The conventions for interpreting variables are
one of the more irksome parts of model theory.
We can avoid them, at a price. Instead of interpreting
a variable as a name of the element b, we can add a
new constant for b to the signature. The price we pay
is that the language changes every time another element
is named. When constants are added to a signature,
the new constants and the elements they name are called
parameters."


Kleene gives more general remarks because he includes
the stipulated definitions of logical constants among
the symbols which may be eliminated. Section 74 begins
with:

"At various stages in the informal development of a
mathematical theory additions may be to the stock of
concepts and notations. If the development is formalized,
at the corresponding stages the new formation rules and
postulates are added to a given formal system S_1 to
obtain another S_2. Thus the formulas (provable formulas)
of S_1 become a subset of those of S_2. The new formation
rules introduce new formal symbols or notations, and the
new postulates provide for their use deductively. We
shall write "|-(1)" ("|-(2)") for the deducibility
relation in S_1 (in S_2).

"Under such circumstances, we say that the new notations
or symbols (with their postulates) are eliminable (from
S_2 in S_1), if there is an effective process by which,
given any formula E of S_2, a formula E' of S_1 can be
found, such that:

(I)

If E is a formula of S_1, then E' is E



(II)

|-(2) E <-> E'



(III)

If Gamma |-(2) E, then Gamma' |-(1) E'


Here Gamma' is D_1', ..., D_k', if Gamma is D_1, ..., D_k.
We call (1) - (3) the elimination relations."



This view of languages seems to come from mixed algebraic
and logical principles. However, I believe that Whitehead
published a book on universal algebra prior to "Principia
Mathematica". When Tarski wrote his 1933 paper on truth
in formalized languages, he specifically excluded languages
built from definitions. Since "Principia Mathematica" had
been the standard at that time, one may interpret the
situation with respect to the algebraic notion.

As I wrote elsewhere it is significant that Chang and

Keisler describe model theory as

(model theory) = (universal algebra) + (logic)

I wonder if some of the confusion over these matters
would be alleviated if curriculum committees placed
a course on universal algebra as a prerequisite for
courses on mathematical logic. The latter introduce
model theory without the algebraic analyses and thus
conflate the role of definitions in mathematics and
logic.

I hope these remarks provide some clarification
for your question. Depending on one's view of
logic, it might be more correct to say that
definitions have no "mathematical" implications.

[graham...@gmail.com]

On Friday, August 16, 2013 1:54:40 AM UTC-7, Peter Percival wrote:
> Can addition be defined in terms of multiplication? I.e., is there a
>
> formula in the language of arithmetic
>
>
>
> x + y = z <-> ...
>
>
>

Here's a solution in www.phpPROLOG.com

PREFIX FUNCTIONS

x - MULTIPLY
+ - ADD
n^ - n to the power of..



1 x [ n^ X ] [ n^ 0 ] [ n^ X ]



2 x [ n^ X ] [ n^ [ s Y ] ] [ n^ [ s Z ] ] :-

+ [ n^ X ] [ n^ Y ] [ n^ Z ]



3 + X Y Z :-

x [ n^ X ] [ n^ Y ] [ n^ Z ]








TRACE
+ [s 0] [s [s 0]] ANS ?


HEAD 1
+ X Y Z
TAIL 1
x n^ X n^ Y n^ Z
x n^ [ s 0 ] n^ [ s s 0 ] n^ Z
HEAD 1
x [ n^ X ] [ n^ [ s Y ] ] [ n^ [ s Z ] ]
TAIL 1
x n^ X n^ Y n^ Z
x n^ [ s 0 ] n^ [ s 0 ] n^ Z
HEAD 1
x [ n^ X ] [ n^ [ s Y ] ] [ n^ [ s Z ] ]
TAIL 1
x n^ X n^ Y n^ Z
x n^ [ s 0 ] n^ [ 0 ] n^ Z
HEAD 1
x [ n^ X ] [ n^ 0 ] [ n^ X ]
MATCH
TRUE 1
MATCH
TRUE 1
MATCH
TRUE 1
MATCH


+ [s 0] [s [s 0]] ANS ?

ANS = s s s 0

[graham...@gmail.com]

> 2 x [ n^ X ] [ n^ [ s Y ] ] [ n^ [ s Z ] ] :-
>
>
>
> + [ n^ X ] [ n^ Y ] [ n^ Z ]

TYPO:

x [ n^ X ] [ n^ [ s Y ] ] [ n^ [ s Z ] ] :-

x [ n^ X ] [ n^ Y ] [ n^ Z ]

this is:

2^x * 2^(y+1) = 2^(z+1)

<-
2^x * 2^y = 2^z

which is just an adaption of Peano Addition / same algorithm.

x + y+1 = z+1
<-

x + y = z

Herc

[Alan Smaill]

Ben Bacarisse <ben.u...@bsb.me.uk> writes:

> William Elliot <ma...@panix.com> writes:
>
>> On Sun, 18 Aug 2013, Peter Percival wrote:

...

>>> Then I think the onus is on you to produced definitions in one or both of
>>> these forms:
>>> x + y = ...
>>> x + y = z <-> ...
>>>
>>> where the only non-logical symbols (baring punctuation) in the ... are from
>>> this set: {*,S,0} or this set: {*,S,0,<}. I wouldn't be surprised if + can be
>>> defined (in the way requested) from {*,S,0} or {*,S,0,<} but I would like
>>> either to see it spelt out, or to be given a reference.
>>
>> 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.

--
Alan Smaill

[Alan Smaill]

I should add: while this shows exponentiation is definable (by
abbreviational definitions) in Peano Arithmetic, as indeed any primitive
recursive function is, it doesn't show that exponentiation can be so
defined purely in terms of multiplication.

--
Alan Smaill

[fom]

I have several volumes of the complete works.

Do you have any more specific information on
which paper?

[Alan Smaill]

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

--
Alan Smaill

[Peter Percival]

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.

[fom]

thanks

[David Libert]

Can addition be defined in terms of multiplication?

...................................................

Author: David Libert
Date: 2013-08-22 12:18:08 EDT


Table of Contents
.................
1 this article is dual posted to Usenet and Wikispaces
2 this is a reply to Peter Percival's Aug 20 article
3 Two stackexchange references from Alan Smaill and Peter
4 Summary of results from second stackexchange reference
5 Discussion of quoted results
5.1 Herbert Enderton A Mathematical Introduction to Logic
5.2 Successor cannot define addition or multiplication
5.3 Multiplication is not definable from successor and +
5.4 Addition IS definable from successor and multiplication
5.5 Decidability or not of arithmetic (sub)theories
5.5.1 Followup about theory of multiplication only
5.5.1.1 Further Handbook reference


1 this article is dual posted to Usenet and Wikispaces
........................................................
Dual posting in accordance with policy
http://davesscribbles.wikispaces.com/policyusenetincrwikispaces

http://davesscribbles.wikispaces.com/plusundeffrommult

2 this is a reply to Peter Percival's Aug 20 article
......................................................
[1]
Peter Percival
sci.logic sci.math

Can addition be defined in terms of multiplication?

Tue Aug 20, 2013
https://groups.google.com/d/msg/sci.logic/Oh0di6uEMSM/I0gwV8M8HhcJ

3 Two stackexchange references from Alan Smaill and Peter
...........................................................

> > 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

Above, Alan and Peter gave two stackexchange references:

[2]
http://math.stackexchange.com/questions/312891/how-is-exponentiation-defined-in-peano-arithmetic

[3]
http://math.stackexchange.com/questions/449146/why-are-addition-and-multiplication-included-in-the-signature-of-first-order-pea?rq=1

4 Summary of results from second stackexchange reference
..........................................................
Peter quotes results stated in [3]:

> 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.

5 Discussion of quoted results
................................

5.1 Herbert Enderton A Mathematical Introduction to Logic
...........................................................
[4]
Herbert Enderton
A Mathematical Introduction to Logic
Academic Press copyright 1972

5.2 Successor cannot define addition or multiplication
........................................................
In [4], section 3.1 pp 178-184, Enderton defines the theory of
successor only on the natural numbers and proves it admits elimination
of quantifiers.

In that section 3.1, exercise 4 on page 184 uses the elimination of
quantifiers above to conclude the sets definable in this theory are
each finite or compliment of finite (cofinite).

From + we can define the set of even numbers, which is neither finite
nor cofinite. From * we can define the set if squares, which is
neither finite nor cofinite.

So neither + nor * are definable.

5.3 Multiplication is not definable from successor and +
..........................................................
This is from Presberger's elimination of quantifiers argument on
successor and + from 1929. [4] states the decidability of this
theory on page 188 and gives the elimination of quantifiers proof
in the following pages. On page 192 [4] states the consequence of
this elimination of quantifiers above that the definable sets are
exactly the eventually periodic ones.

From * we can define the set if squares, which is not eventually
periodic, so * is undefinable from this theory.

5.4 Addition IS definable from successor and multiplication
.............................................................
The quote from [3] above says multiplication is NOT definable from
successor and multiplication, but this seems to be in error.

Herbert Enderton posted about this, noting a method from Julia
Robinson:

[5]
Herbert Enderton Tue Dec 10, 2002 sci.logic
"Re: The language of whatever (Was: Definable real numbers)"
https://groups.google.com/d/msg/sci.logic/A6l0yl6QzbA/76ELiiVDNBMJ
https://groups.google.com/forum/#!original/sci.logic/A6l0yl6QzbA/76ELiiVDNBMJ

5.5 Decidability or not of arithmetic (sub)theories
.....................................................
[3] noted +,* together are undecidable, but + and * are each
individually decidable.

For +,* code Turing machines into +,* and the undecidability of the
halting problem. Such coding can be done with Godel's methods to
code sequences as from [2].

[6]
http://en.wikipedia.org/wiki/Decidability_(logic)

attributes this:

> The first-order theory of the natural numbers with
> addition, multiplication, and equality, established
> by Tarski and Andrzej Mostowski in 1949.

(Above I edited to break a long line.)


The + decidability is Presberger's Theorem as above.

In this thread

[7]
Robin Chapman sci.logic sci.math Fri Aug 16, 2013
"Re: Can addition be defined in terms of multiplication?"
https://groups.google.com/d/msg/sci.logic/Oh0di6uEMSM/remJFZUASlcJ

noted the Presberger result about + above, and then noted this
should also apply to *.

This sounds right to me though I don't yet see it in detail. The
standard model of * is a finite support product of omega copies of
the standard + model, ie each coordinate copy corresponding to
powers of a distinct prime. Composite numbers appear as finite
support Cartesian products of those copies.

Either repeat Presberger's proof on this more complicated setup
directly. Or maybe some abstract nonsense does a reduction.

If that is correct about * being a decidable theory, that answers
the original question of this thread:

[8]
Peter Percival
sci.logic sci.math

Can addition be defined in terms of multiplication?

Fri Aug 16, 2013
https://groups.google.com/d/msg/sci.logic/Oh0di6uEMSM/ll6XE2ItRvAJ

namely answer that addition cannot be defined from multiplication.
Robin already pointed this out in [7].

5.5.1 Followup about theory of multiplication only
...................................................
Above is as far as I got on my own.

Since writing that I Googled and found some more. Not proofs I know
but literature references. So I am adding this as a separate
section about that and preserving my original comments above. Those
comments were from a less informed background so are still easier to
understand.

I Googled "theory of multiplication only decidable" and that led
me to the references I will give and discuss below.

[9]
On Direct Products of Theories
Andrzej Mostowski
Source: J. Symbolic Logic Volume 17, Issue 1 (1952), 1-31.
http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.jsl/1183731313

[10]
Research web page of Alexis Bès University of Paris
http://lacl.fr/bes/recherche.html

[11]
A.Bès
Definability and decidability results related
to the elementary theory of ordinal multiplication
Fund.Math.171, 197-211 (2002).
http://lacl.fr/bes/publi/ordimult.ps
http://lacl.fr/bes/publi/errataordimult.ps


[11] page 1 notes that the decidability of theory of multiplication
only on omega was announced by Skolem in 1930 and proved by
Mostowski in [9]. [11] notes that proof in [9] was a direct
consequence of Mostowski's results on direct products of structures
and Presberger's result on decidability of the theory of + on omega.
So it seems this was along the lines I was noting in the section

[10] links to [11].

[11] notes as above about Skolem and [9]. [11] also references two
other papers proving that decidability of the theory of
multiplication on omega.

[11] also states and proves its main new theorem: the elementary
theory of usual ordinal multiplication on an ordinal alpha
(ie von Neumann's definition: considering ordinal alpha to be the set
of all smaller ordinals, and hence the universe of a structure) is
decidable <-> a < omega^omega.

[11] includes further technical results about definability from
multiplication on an ordinal.

Those are the basic references I found. So this is further support
for the stackexchange [3] about theory of multiplication being
decidable. As Robin noted in [7] and I noted in the section above,
this is enough to answer the original [8] question: multiplication
can't define addition.

There is the Feferman Vaught theorem, along the lines of decidability
of theory of a product structure of factors having decidable
theories. Possibly related to the Mostowski [9].

Googling "feferman vaught" I found a reference on this sort of
thing, though scanning I didn't notice the names Feferman Vaught:

[12]
http://theory.stanford.edu/~tingz/talks/quals.pdf

[12] page 34 is specifically about decidability of multiplication on
natural numbers.

5.5.1.1 Further Handbook reference
...................................
Since writing the above I found an additional reference:

[13]
Handbook of Mathematical Logic
Edited by Jon Barwise
North-Holland Publishing Company
4th printing 1985

[14]
Decidable Theories
Michael O. Rabin
[13] pp 595-629


[15] in [14] section 2.5 Further results pp 611-612
page 612

[15] notes properties of product structures was initiated by
Mostowski and developed by Feferman and Vaught. Rabin notes
this applies to show the theory of multiplication on omega is
decidable, applying these product results to the decidability of
the theory of + on omega. Namely by this general theory getting
the decidability of the direct sum of omega many copies of + on
omega. This as I wrote earlier about finite support.

Rabin mentions this decidability of * as due to Skolem and Mostowski.

[Peter Percival]

David Libert wrote:
> Can addition be defined in terms of multiplication?
> ...................................................

Thank you. I rather fancied that my question had an affirmative answer.