> Now I know of the standard way that addition can be *defined* in terms of
> multiplication and successor, but I’m not sure that this has too much to do
> with the oft-suggested implication that "arithmetic with multiplication only
> is decidable".
> Is that last statement ever made, explicitly? I don’t recall it being so.
> And just what would it BE – arithmetic with multiplication and successor,
> but not addition. What sensible axioms could it be given?
See Boolos and Jeffrey, Computability and Logic, 3rd ed, p 219: "Like arithmetic
without multiplication, arithmetic without addition is a decidable theory, as
Skolem showed." As for axiomatisation: I don’t know, the presentations all involve
discarding the sentences of arithmetic which contain successor and addition (it
has to be both, otherwise, as you say, the theory becomes essentially equivalent
to arithmetic as we can define addition in terms of successor and multiplication).
Hope this helps. Antony.
Accounts of Pressburger Arithmetic, and the proof that arithmetic with
addition (and successor) but NOT multiplication are decidable, are often
preceded by a comment or so about arithmetic with "only one of" multiplication
or addition.
Now I know of the standard way that addition can be *defined* in terms of
multiplication and successor, but I’m not sure that this has too much to do
with the oft-suggested implication that "arithmetic with multiplication only
is decidable".
Is that last statement ever made, explicitly? I don’t recall it being so.
And just what would it BE – arithmetic with multiplication and successor,
but not addition. What sensible axioms could it be given?
Help please.
——————————————————————————-
Bill Taylor W.Tay…@math.canterbury.ac.nz
——————————————————————————-
Godel’s humility theorem:-
Providing you are capable of doing sufficient math,
you are intelligent if and only if you cannot prove you are.
——————————————————————————-
- Hide quoted text — Show quoted text -
Bill Taylor wrote:
> Accounts of Pressburger Arithmetic, and the proof that arithmetic with
> addition (and successor) but NOT multiplication are decidable, are often
> preceded by a comment or so about arithmetic with "only one of" multiplication
> or addition.
> Now I know of the standard way that addition can be *defined* in terms of
> multiplication and successor, but I’m not sure that this has too much to do
> with the oft-suggested implication that "arithmetic with multiplication only
> is decidable".
> Is that last statement ever made, explicitly? I don’t recall it being so.
> And just what would it BE – arithmetic with multiplication and successor,
> but not addition. What sensible axioms could it be given?
Consider–add to suitable* axioms for first order logic these:
1. if (x = y) then (if (x = z) then (y = z))
2. if (x = y) then (sx = sy)
3. 0 <> sx
4. if (sx = sy) then x = y
5. x + 0 = x
6. x + sy = s(x + y)
9A. for any wff A, if A0 then (if (all x)(if Ax then Asx) then (all
x)Ax)
Then you have Presburger’s 1929 axioms.
Now replace those with:
1. if (x = y) then (if (x = z) then (y = z)
2. if (x = y) then (sx = sy)
3. 0 <> sx
4. if (sx = sy) then x = y
7. x.0 = 0
8n. for each natural number n, N0.(sy) = N(N0.y), where "N" is n ‘s’s.
9A. for any wff A, if A0 then (if (all x)(if Ax then Asx) then (all
x)Ax)
and you have _my_ candidate for arithmetic without +.
8n is just an axiom schema to replace
8. x.(sy) = (x.y) + x
by replacing "+ x" with x-many successor function applications.
Could be rubbish–no guarantee of fitness for purpose!
*Note, 1. is needed because the "suitable" fol has no axioms for "=", it
is introduced as a binary predicate.
All of these "s"s remind me to remind you that "Presburger" only has
one.
Regards, PP
- Hide quoted text — Show quoted text -
> Help please.
> ——————————————————————————-
> Bill Taylor W.Tay…@math.canterbury.ac.nz
> ——————————————————————————-
> Godel’s humility theorem:-
> Providing you are capable of doing sufficient math,
> you are intelligent if and only if you cannot prove you are.
> ——————————————————————————-
- Hide quoted text — Show quoted text -
Bill Taylor wrote:
> Accounts of Pressburger Arithmetic, and the proof that arithmetic with
> addition (and successor) but NOT multiplication are decidable, are often
> preceded by a comment or so about arithmetic with "only one of" multiplication
> or addition.
> Now I know of the standard way that addition can be *defined* in terms of
> multiplication and successor, but I’m not sure that this has too much to do
> with the oft-suggested implication that "arithmetic with multiplication only
> is decidable".
> Is that last statement ever made, explicitly? I don’t recall it being so.
> And just what would it BE – arithmetic with multiplication and successor,
> but not addition. What sensible axioms could it be given?
> Help please.
> ——————————————————————————-
> Bill Taylor W.Tay…@math.canterbury.ac.nz
> ——————————————————————————-
> Godel’s humility theorem:-
> Providing you are capable of doing sufficient math,
> you are intelligent if and only if you cannot prove you are.
> ——————————————————————————-
Goedel’s complementary humility theorem:
Providing you are capable doing sufficient physics,
you are intelligent if and only if you can prove you
are ignorant of Goedel’s theorem.
Bill Taylor <math…@math.canterbury.ac.nz> a écrit dans le message :
89n3uc$34…@cantuc.canterbury.ac.nz…
- Hide quoted text — Show quoted text -
> Accounts of Pressburger Arithmetic, and the proof that arithmetic with
> addition (and successor) but NOT multiplication are decidable, are often
> preceded by a comment or so about arithmetic with "only one of"
multiplication
> or addition.
> Now I know of the standard way that addition can be *defined* in terms of
> multiplication and successor, but I’m not sure that this has too much to
do
> with the oft-suggested implication that "arithmetic with multiplication
only
> is decidable".
> Is that last statement ever made, explicitly? I don’t recall it being so.
> And just what would it BE – arithmetic with multiplication and successor,
> but not addition. What sensible axioms could it be given?
> Help please.
A good reference for decidability of Th(N;=,x) (the elementary theory of
integer multiplication – sometimes called "Skolem Arithmetic") is :
C.Smorynski, "Logical Number Theory I", Springer-Verlag, 1991.
It presents Cegielski’s proof (1981) by quantifier elimination.
Alternative proofs were given by Mostowski ("On directs products of
theories",J.Symb.Log. 17, 1-31, 1952) and later Hodgson ("On direct products
of automaton decidable theories", Theor.Comp.Sci. 19,331-335, 1982) — both
use Presburger’s decidability result for Th(N;=,+).
Alexis Bes