[FOM] Goedel's First Incompleteness Theorem

[joeshipman@aol.com]

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