I�ve just begun to study these things [*], so maybe I can say something about this subject
Dan Minette wrote: > > The reason this is important is that it is tied into > the proof of true statements in a formal system. > My understanding of what Godel proved is > "every formal system at least as complicated as arithmetic > will have true statements that cannot be proven within > the system." These statements are > (usually always?) self-referential statements. > The math that studies "proof" is called Model Theory, and it goes something like this: in math, we have a structure [for example, a group with one "special" element and a binary operation] and a set of axioms that this structure must satisfy [again, in a group we have the neutral element, the inverse, and associativity]. In Model Theory, we have a "language" [that can even have an infinite number of symbols, that generates sentences], and the set of axioms [again, it can be infinite], and proof of truth or falsity comes from rules that are clearly defined for manipulating sentences. Truth or Falsehood of a sentence are defined if for all structures that satisfy the axioms the sentence is valid in that structure. It�s possible to say that some sentences are "false" or that some statements are "true" [examples of both: "exists x such that x != x" and "for all x, x = x"], while some other sentences may or may not be valid ["exists x, exists y, such that x != y" is valid in any structure with 2 or more elements, false otherwise]. One curious outcome of Model Theory is that there is _no_ system of axioms that can prove that the structure has a finite number of elements without fixing this number of elements [an axiom that says that the structure has at least 3 elements is "exists x, exists y, exists z, such that x != y and x != z and y != z", while and axiom that says that the structure has at most 3 elements is "for all x, for all y, for all z, for all t, x = y or x = z or x = t or y = z or y = t or z = t"; take both axioms together and we have a new theorem equivalent to saying that there are 3 and only 3 distinct elements] BTW, these two axioms that define a set with 3 elements are "complete", because they define _uniquely_ [up to isomorphism] a set of three elements. Godel�s theorem is that any system of axioms [this includes an _enumerable_ system of axioms, but I don�t know if more than that are allowed] that is complex enough to include set theory is not "complete", in other words, there are structures that satisfy them and that are _not_ isomorphic. For example, if we take ZFC [the Zermelo-Frankel Axioms of Set Theory with the Continuum Hypothesis] it�s even possible to _construct_ an _enumerable model_ of it. Namely, it�s possible to build a set U and a binary relation @ [damn keyboard without math symbols] such that (U,@) satisfy _all_ ZFC axioms, with @ playing the role of the "belongs to" relation!!! [and it�s even intuitive how to build this model: just take as 0-th step the empty set, and as n-th step all the sets that can be build from the previous set using (once) all axioms; each step is enumerable, so its union is enumerable too] > Humans have means of handling these statements. > Humans can find ways to prove these statements > outside of the formal system. This is one of the main > arguments against considering human thinking as > algorithmic: we can handle these self-referential > statements. > But humans _can�t_ handle these statements, heck, there are even statements that are defined in a _finite_ set that humans can�t handle. What is the most significant digit of 2^(10^googol) ? No matter how smart you think a human brain might be, we are _limited_ in time to run an algorithm. > Its not that humans can make such predictions; they can't. > Its that the ability to handle what humans do > algorithmically involves the completeness > of algorithms. That's why the question of a universal > Turing machine is important. > Is it really important? We know that there are _finite_ problems that can�t be solved by machine or human brain. So why should we be so scared that there are _infinite_ problems that can�t be solved? Alberto Monteiro
