On 28 Feb 2011, at 18:36, Brent Meeker wrote:

## Advertising

On 2/28/2011 1:42 AM, Bruno Marchal wrote:This is a very technical point. It can be shown that classicalfirst order logic+addition gives a theory too much weak to be ableto defined multiplication or even the idea of repeating anoperation a certain arbitrary finite number of time. Likewise it ispossible to make a theory of multiplication, and then addition isnot definable in it. The pure addition theory is known asPressburger arithmetic, and has been shown complete (it proves allthe true sentences *expressible* in its language, thus withoutmultiplication symbols); and decidable, unlike the usual Robinsonor Peano Arithmetic, with + and *, which are incomplete andundecidable.Once you have the naturals numbers and both addition andmultiplication, you get already (Turing) universality, and thusincompleteness, 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 everything-list@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.