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