[FOM] Goedel's First Incompleteness Theorem
joeshipman@aol.com
joeshipman at aol.com
Sun Oct 25 19:02:38 EDT 2009
There is something common to all proofs of Godel's incompleteness
theorem. The most "different" proof I have seen is Chaitin's, which
develops algorithmic information theory and then concludes the
Incompleteness Theorem as a trvial corollary.
If you just care about specific systems, you can often avoid
diagonalization or other characteristic techniques. For example, you
could develop forcing and conclude that if ZF is consistent then it has
models with CH being true and other models with CH being false,
therefore ZF is either incomplete or inconsistent -- but that kind of
proof is specific to the ZF system. (There is a technical difficulty
because most treatments of forcing assume the existence of a transitive
model of ZF, but this can be avoided in various ways.)
-- JS
-----Original Message-----
From: praatika at mappi.helsinki.fi
To: Foundations of Mathematics <fom at cs.nyu.edu>
Sent: Sun, Oct 25, 2009 11:37 am
Subject: Re: [FOM] Goedel's First Incompleteness Theorem
"David F. Isles" <david.isles at tufts.edu>:
> I would appreciate it if someone could mention a survey or listing of
> different proofs of Goedel's First Incompleteness Theorem.
The following might be helpful:
Kotlarski, Henryk "The incompleteness theorems after 70 years." Ann.
Pure Appl. Logic 126 (2004), no. 1-3, 125-138.
A general warning: often the "different proofs" establish something
much more local and weaker than Gödel's theorem, e.g. just the
incompleteness of PA, and not the incompleteness of *any* consistent
formal system which contains elementary arithmetic, as Gödel's theorem
does.
And to prove that, the (more-or-less) original Gödel-Rosser proof may
still be - if not the only - at least the simplest way. (There are
obviously some variations around)
All the Best,
Panu
Panu Raatikainen
Ph.D., Academy Research Fellow,
Docent in Theoretical Philosophy
Department of Philosophy
University of Helsinki
Finland
E-mail: panu.raatikainen at helsinki.fi
http://www.mv.helsinki.fi/home/praatika/
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list