On 2/28/2011 1:42 AM, Bruno Marchal wrote:

This is a very technical point. It can be shown that classical firstorder logic+addition gives a theory too much weak to be able todefined multiplication or even the idea of repeating an operation acertain arbitrary finite number of time. Likewise it is possible tomake a theory of multiplication, and then addition is not definable init. The pure addition theory is known as Pressburger arithmetic, andhas 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 andmultiplication, you get already (Turing) universality, and thusincompleteness, insolubility.## Advertising

Bruno http://iridia.ulb.ac.be/~marchal/

`Hmmm. Does that mean an arithmetic based on first order logic,`

`addition, and a logarithm operation might be complete and yet include a`

`kind of multiplication?`

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