On 28 Feb 2011, at 18:36, Brent Meeker wrote:
On 2/28/2011 1:42 AM, Bruno Marchal wrote:
This is a very technical point. It can be shown that classical
first order logic+addition gives a theory too much weak to be able
to defined multiplication or even the idea of repeating an
operation a certain arbitrary finite number of time. Likewise it is
possible to make a theory of multiplication, and then addition is
not definable in it. The pure addition theory is known as
Pressburger arithmetic, and has been shown complete (it proves all
the true sentences *expressible* in its language, thus without
multiplication symbols); and decidable, unlike the usual Robinson
or Peano Arithmetic, with + and *, which are incomplete and
undecidable.
Once you have the naturals numbers and both addition and
multiplication, you get already (Turing) universality, and thus
incompleteness, insolubility.
Bruno
http://iridia.ulb.ac.be/~marchal/
Hmmm.
That's just "known" results in the field.
Does that mean an arithmetic based on first order logic, addition,
and a logarithm operation
I guess you mean some digital truncation of it, by ceilings or bottom,
with logarithm(n) = the least natural number bigger than logarithm(n),
or the biggest natural number smaller than logarithm(n) ?
might be complete
Quite possible, but I really don't know that. Interesting, but not
necessarily an easy exercise.
and yet include a kind of multiplication?
If addition + natural number logarithm is Turing complete (universal),
then multiplication, like any Turing computable functions will be
capable of being defined in the theory.
Note this: diophantine (means that the variables refer to integers)
polynomial of degree 4 equations are Turing universal. In particular
there is a degree four universal polynomial which, equated to 0, is
universal.
But on the real numbers, you can use Sturm Liouville technic to solves
such polynomial equation. The first order theory of the real numbers
is complete and decidable. Thus you cannot defined the natural numbers
in such a theory! But the theory of the trigonometric polynomials on
the reals is again Turing complete. Now you can use the sin function
to define the natural numbers, and you get the addition and
multiplication on them by the usual real addition and multiplication.
Bruno
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
