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.




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.



You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to