Fw: Theorem about logical systems

[Phil Bigelow <bigelowp@juno.com>]

Allen wanted me to forward this to the list.

<pb>
--
Stigmata free since 1972.
Oh wait....maybe it was only a Ketchup stain.


--------- Forwarded message ----------
From: "A.P. Hazen" <a.hazen@philosophy.unimelb.edu.au>

Hi!
   I'm a lurker  on the Dinosaur Mailing  List: a philosopher 
(specialty: logic) by trade, but with an avocational interest in 
vertebrate paleontology.  (Actually more interested in early mammals 
than in dinosaurs, but  fortunately you DML-ers aren't TOO strict 
about topic!)
    Since you have all  posted  something about MY specialty to DML, 
I'm taking the liberty of writing to you with references and  one 
paragraph  story.
---
References:
    The theorem Don Ohmes  was remembering is, in the trade, known as 
Gödel's SECOND Incompleteness  Theorem.  Published in German in 1931, 
English translations in (among other  places) Gödel's "Collected 
Works" v. 1 and in J. van Heijenoort, ed.,  "From Frege to Gödel: a 
sourcebook in mathematical logic."  Technical enough that I wouldn't 
recomment it to non-specialists.
    I haven't read the Wikipedia article  Tom referred to on DML.
    It's a famous and important enough theorem that lots of textbooks 
(typically for seniors or grad students in math or philosophy) 
contain expositions: these typically presuppose about two semesters 
of symbolic  logic.  If you have a basic acquaintance with symbolic 
logic and want to put some time into it, Raymond Smullyan's "Gödel's 
Incompleteness Theorems" is maybe the most user-friendly of 
expositions that go into technical details.
    There are LOTS and LOTS of informal expositions of varying 
quality.  E.  Nagel and ? Newman, "Gödel's Theorem," isn't bad (and 
the new  edition with a preface and emendations by Hofstadter is 
better than the original): 100+ small-format pages.  (Mathematician & 
science-fiction writer) Rudy Rucker  has a comprehensible short 
exposition  in an appendix to his "Infinity and the Mind".
---
Story:
    Gödel's Incompleteness Theorems have been the topic of  an 
extraordinary amount of b.s. and philosophical turf-war.  Saying they 
imply that  mathematics requires "faith" is, I suspect, right if 
properly understood, but saying it in the presence of logicians will 
get a fight started.
    Briefly.
    Starting about 1900, a lot of effort went into systematizing all 
of mathematics  in systems of axiomatic set theory, with axioms 
which, for precision, could be expressed in  the  notation of 
symbolic logic.  Alas, many of the systems suggested were 
INCONSISTENT: "Russell's Paradox" is the key word here.  An 
inconsistent system of axioms is useless,  because it can  "prove" 
EVERY sentence in the language  of its axioms.  So there  was also 
interest in how you could establish that  a system was consistent.
    Gödel showed (First Theorem) that any such axiomatic system
        [technical detail: any such system of at least a
        certain minimum  strength: able to express statements
        about the natural numbers and prove some basic ones]
is either INCOMPLETE or INCONSISTENT: that is, for a consistent one 
there are sentences  (expressed in the  same notation as the axioms) 
that can't be proved or disproved from  its axioms.  Roughly: no 
formalized axiomatic system is the FULL story, 'cause (unless it is 
inconsistent, but we aren't interested in inconsistent theories!) 
there's always a stronger one that can prove more.
    Gödel then showed (Second Theorem, a fairly quick corollary to the 
first given the way the proof goes) that...
                                        Well, the statement THAT a 
system of axiomatic set theory is consistent can (with proper 
encoding) be expressed AS a statement about sets (or about numbers).
        [Encoding: this mystifies many people, but is actually
        a basically simple  idea.  Using Morse Code, you can
        think of any sentence of a particular language as a
        string of dots and  dashes.  Thinking of them as 1's
        and 0's, you can think of the statement as a binary
        numeral: a name for a number.  So you can paraphrase
        statements ABOUT sentences as statements about numbers.
        ... and Gödel showed that, when the axioms and sentences
        of a formalized theory were treated as numbers in this way,
                statements like "this sentence is not formally derivable
        from those axioms" can be expressed as fairly simple
        mathematical relations between the numbers.]
What Gödel proved as his second theorem was that ONE of the sentences 
that couldn't be proven from the axioms of a consistent system was... 
the very statement that the system was consistent!
        So...
        Suppose you want to PROVE that an axiomatic system of set 
theory is righ, or is at least consistent.  What principles and facts 
do you appeal to in proving  this?  Well, [unless you are out of luck 
and the thing is really inconsistent] you can't make do with 
principles expressed in the axioms themselves: you need some 
"ASSUMPTION" from outside.
        ...
        Archimedes said he could move the earth, GIVEN a long enough 
lever and somewhere to stand.  One way of phrasing Gödel's theorem is 
that, in order to "move" anything in the foundations of mathematics, 
you always have to be GIVEN something.

Be well,
    Allen Hazen

PS: DML is one of my favorite WWWeb sources.