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