On 12 Dec 2012, at 23:39, meekerdb wrote:

On 12/12/2012 7:27 AM, Richard Ruquist wrote:
On Tue, Dec 11, 2012 at 10:08 AM, Bruno Marchal<marc...@ulb.ac.be> wrote:
Gödel used Principia Mathematica, and then a theory like PA can be shown essentially undecidable: adding axioms does not change incompleteness. That is why it applies to us, as far as we are correct. It does not apply to everyday reasoning, as this use a non monotonical theory, with a notion of
updating our beliefs.

Not all undecidable theory are essentially undecidable. Group theory is
undecidable, but abelian group theory is decidable.

Bruno, is there an general, meta-mathematical theory about what axioms will produce a decidable theory and which will not?

I have never heard about a simple recipe. The decidability of the theory of abelian group has been shown by Wanda Szmielew ("Arithmetical properties of Abelian Groups". Doctoral dissertation, University of California, 1950), see also "Decision problem in group theory", Proceedings of the tenth International Congress of Philosophy, Amsterdam 1948).

The undecidability of the elementary theory of group is proved by Tarski, and you can find it in the book (now Dover) Undecidable Theories, 2010.

Tarski has also proved the decidability of the elementary (first order) theory of the reals (with the consequence that you cannot define the natural numbers from the reals with the real + and * laws).

Natural numbers are logically more complex than the real numbers.

Same with polynomial equations: undecidable with integers coefficients and unknown, but decidable on the reals. In the real, adding the trigonometric functions makes possible to define the natural numbers (by sinPIx = 0), and so the trigonometric functions reintroduce the undecidability.



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