virus: Godel's theorem

Eric Boyd (6ceb3@qlink.queensu.ca)
Sun, 05 Jul 1998 05:54:05 -0400


virions,

I've studied Godel's theorem -- not all *that* complicated, but certainly
not, say, easy to follow. The basic concept is, as people have pointed
out, *self-reference*:

`This well-formed formula is unprovable-in-Peano-Arithmetic.'
-- http://users.ox.ac.uk/~jrlucas/implgoed.html

The crux of the proof is the formation of the above statement in the formal
system in question, and, by meta-mathematical techniques, the realization
that it *has* to be true... In his words "We are therefore confronted with
a proposition which asserts its own unprovability."

Godel himself wrote a brilliant summary of his proof at the beginning of
his paper:

http://www.ddc.net/ygg/etext/godel/godel3.htm

I recommend it.

As to how profoundly important this result is, I sort of waver... the fact
that it applies to formal systems so simple as even the natural numbers
with addition and multiplication is rather scary (to think that it's
possible to give a simple math statement which is UNDECIDABLE under the
axioms of the system IS scary.) What comes to mind immediately, of course,
is the proof of independence of Euclid's "parallel postulate" -- for 2000
years, people were convinced that it MUST be a consequence of the other,
simpler, axioms of geometry -- but they were wrong. It stands outside that
system -- meaning it is literally undecidable from within that formal
framework.

On the other hand, Godel's proof DOES NOT ESTABLISH the existence of
statements such as Euclid's parallel postulate -- what it establishes is
the existence of self-reflective statements which ensure their own
unprovability. Yes, this means that ultimately the formal systems in
question are incomplete, but perhaps they are ONLY incomplete with respect
to this one category of statements -- which are not particularly USEFUL
ones anyway. Interesting, perhaps -- but in terms of model building, those
types of statements have no relevance.

On a more profound note, some of the other results that Godel established
in the same paper -- for instance, the unprovability of the consistency of
a system from inside itself -- have deeper consequences.

"Even more interesting, the reality of Platonic 'forms' - ideals
contemplated by the human intellect - is questioned by some simple
corollaries to Gödel's Theorem[1]. His Proposition XI states that the
consistency of any formal deductive system (if it is consistent)
is neither provable nor disprovable within the system. A quick leap
of logic interprets this corollary as such: 'Any sufficiently
complex, consistent logical framework cannot be self-dependent'
- i.e., it must rely on intuition, or some external confirmation
of certain propositions (specifically, one that proves internal
consistency)."
-- Siegfried, Introduction to Godel's Theorem,
http://www.ddc.net/ygg/etext/godel/

>From a model building view point, what this means is that while we can
build a model which will "map" the phenomena in question (with some
incompleteness, although, as I said, the statements which Godel *proved*
are unprovable do not necessarily relate to the modeled, but exist as
self-referential statements inside the model), there is the problem that
the *model* itself now stands in the position that the *modeled* used to --
that is, in need to explanation, justification, etc. We cannot prove the
consistency of the model from within itself -- we must go OUTSIDE, either
to the real world (which brings us back where we started), or to another
model (infinite recursion results; how many meta's would you like?).

So, again, we see that a justificationist stance runs into problems:

"Every branch of knowledge, if traced up to its source and final
principles, vanishes into mystery." -- Arthur Machen

And, despite my own misgivings about the dangers of (provisionally)
accepting things merely because they can't be shown wrong, I recommend
PanCritical Rationalism: a falsificationist stance.

http://www.primenet.com/~maxmore/pcr.htm

ERiC

[1] Since the platonic realm is the home of god, is it a mere coincidence
that my spell checker wants to replace "Godel" with "godless"??? Serious
replies only please :-)