> -----Original Message----- > [EMAIL PROTECTED] On Behalf Of John Randall > > Raul Miller wrote: > On 7/5/07, Terrence Brannon <[EMAIL PROTECTED]> wrote: > >> But then again, math is limited by Goedel's Incompleteness > >> theorem whereas computers can do more? > > > > That does not match my understanding, of Goedel's > > Incompleteness theorem, nor of the character of computers. > > > > As I understand the incompleteness theorem: a mathematical > > system of sufficient complexity will allow an infinite number > > of statements which are not resolvable simply by recourse to > > previous axioms (definitions). > > > I largely agree with Raul, and differ from Terrence. > > Completeness and consistency are not mutually exclusive. > > The only mathematical systems that are considered are consistent ones: > they may or may not be complete. > > Boolean algebra is complete: ordinary arithmetic on the natural > numbers is not. However this does not mean that every statement on > the natural numbers is undecidable (for example, x<:x^2 is decidable > and true), only that there are some which are not.
Yet, as far as I understand, a consequence of Godel's Incompleteness Theorem (found by himself) states that the consistency of the ordinary arithmetic cannot be proven (at least, an effective proof cannot exist). In other words, believing in the consistency of the arithmetic is, ultimately, an act of faith. (Then again, what is not?) To complicate matters, at least for me, there is a result by Tarski implying that (an axiomatic version of) the field of real numbers is complete. I am not familiar with its proof and I do not know how to reconcile it with the former statement. Can you, or anybody else, provide some enlightenment? (My only guess is that the above mentioned axiomatic description of the field of real numbers is insufficient to imply the axioms of the ordinary arithmetic of the natural numbers presumed to be embedded.) > > Completeness does not have a huge impact on most of mathematics except > in areas which directly depend on it, such as the word problem and the > halting problem. Computable functions are much smaller than functions > from the natural numbers to the natural numbers: there are only > countable many of the former, and uncountably many of the latter. A related problem to halting is finding (using a proper definition of) the shortest version of an arbitrary self-contained algorithm (which it is not an unusual pastime of some members of this forum, myself included). This problem prompted Chaitin's work (according to himself). > > As to learning mathematics, I believe that proofs are a post hoc > formalization, and that almost all mathematics proceeds from > examples. Indeed, theorems without concrete examples are dismissed as > "general nonsense". > > Best wishes, > > John > > > > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
