The Goedel Incompleteness Theorem and Decidability over a Ring

Goedel showed in 1931 that given any reasonable (consistent and effective) theory of arithmetic, there are true assertions about the natural numbers that are not theorems in that theory. This "incompleteness theorem" ended Hilbert's program of formalizing mathematics and is rightfully regarded as the most important result in the foundations of mathematics in this century. Now the concept of undecidability of a set plays an important role in understanding Goedel's work. On the other hand, the question of the undecidability of the Mandelbrot set has been raised by Roger Penrose. Penrose acknowledges the difficulty of formulating his question because "decidability" has customarily only dealt with countable sets, not sets of real or complex numbers.Here we give an exposition of Goedel's result in an algebraic setting and also a formulation (and essentially an answer) to Penrose's problem. The notions of computability and decidability over a ring R underly our point of view. Goedel's Theorem follow from the Main Theorem: There is a definable undecidable set over Z. By way of contrast, Tarski's Theorem asserts that every definable set over the reals or any real closed field R is decidable over R. We show a converse to this result, namely: any sufficiently infinite ordered field with this property is necessarily real closed.

ICSI Technical Report TR-90-036

Technical Report