NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/lang/c/16238

Internet Message Format | 1992-11-09 | 3.4 KB

Xref: sparky comp.lang.c:16238 comp.lang.c++:15988 comp.lang.pascal:6442 comp.lang.misc:3556
Newsgroups: comp.lang.c,comp.lang.c++,comp.lang.pascal,comp.lang.misc
Path: sparky!uunet!ferkel.ucsb.edu!taco!gatech!darwin.sura.net!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!sunova!sunova.ssc.gov!loegel
From: [e-mail] (George J. Loegel)
Subject: Godel's Proof (was Re: Software design =/= Programming)
In-Reply-To: [e-mail]'s message of Mon, 9 Nov 92 14:45:50 GMT
Message-ID: <[e-mail]>
Sender: [e-mail] (News Admin)
Nntp-Posting-Host: fegatello.ssc.gov
Reply-To: [e-mail]
Organization: Superconducting Super Collider Lab, Dallas, TX
References: <josef.720690811@uranium>
    <[e-mail]>
    <[e-mail]> <[e-mail]>
    <[e-mail]>
Date: Mon, 9 Nov 1992 19:45:31 GMT
Lines: 51

From the McGraw-Hill Dictionary of Science and Technology:
Godel's Proof: Any formal arithmetical system is incomplete in the
sense that, given any consistent set of arithmetical axioms, there are
true statements in the resulting arithmetical system that cannot be
derived from these axioms.
--- end of def ---
The trick here is that you use the arithmetical system to encode
information (i.e.  Godel numbering) about proofs and then show (a) no
proof leads to a false statement and (b) you can construct a statement
which says "I have no proof". By (a), (b) must be true, so (b) has no
proof. This leaves us with a true statement we cannot prove.

|>     The proof is truly wondrous to work through.

The full proof *is* wonderful -- we took six weeks going through it in
class. Also, Raymond Smullyan has just published a book (Oxford Press)
where he gives *three* different proofs of the Incompleteness Theorem.
Smullyan is a wonderful author (e.g. "Forever Undecided : a puzzle
guide to Godel" and "To Mock a Mockingbird") and I recommend any of
the books.

As for Charles Reindorf's question:
   OK, riddle me this. If I get you right, then if a statement A is
   provably undecidable, you assume that it is true. But if A is provably
   undecidable then so is ~A. This means that *both* A and ~A are assumed
   "true" which is a contradiction. Therefore how can you argue that A
   was "true"? (e.g. you might assume that the axiom of choice were true,
   but you might perversely also assume it were false, I guess).
---- end of quote ---

I believe this is a question about "independent axioms". The best
example of this is Euclid's 5th Postulate (Given a line and a point
outside the line there is exactly one line parallel to the given
line). This postulate gave many mathematicians trouble so they tried
to "prove" it from the remaining axioms. Euclid's 5th Postulate is
"independent" of the other axioms so we can make geometrical systems
where this postulate is *either* true or false but *not* (as you point
out) both.  If we replace the 5th Postulate with "There are *no* lines
parallel to the given line" we get spherical geometry, and if we use
"There are more than one parallel line" we get Lobashevski (or
hyperbolic) geometry.

Another example of an "independent axiom" is the Continuum Hypothesis
with respect to (ZF?) set theory.
--
George J. Loegel
Superconducting Super Collider Laboratory
Accelerator Systems Division
Controls Department -- Software Group
Dallas, TX.
[e-mail]