[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Subject Index][Author Index]
Fw: Theorem about logical systems
Allen wanted me to forward this to the list.
Stigmata free since 1972.
Oh wait....maybe it was only a Ketchup stain.
--------- Forwarded message ----------
From: "A.P. Hazen" <email@example.com>
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
Since you have all posted something about MY specialty to DML,
I'm taking the liberty of writing to you with references and one
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".
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.
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!
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.
PS: DML is one of my favorite WWWeb sources.