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

Reply via email to