Thursday, January 13, 2005

Godel's Incompleteness Theorem

by Asim Jalis

Here is an excellent discussion of Godel's Incompleteness Theorem by George Green: Link to George Green writes: > For any [consistent, recursive] axiom-set S, of sufficient > strength (to have a godel sentence), there is a sentence G(S) > that is true in some models M(S) and false in some other > models M(S) (this [along with the completeness theorem] is why > G(S) is not provable from S). In Godel's original proof, S is > PA, M(S) is N, and G(S) is "PA is consistent". > [Godel's theorem] means that if you have an intended model > (like N) in mind, then you can't always get what you want (a > proof, from your preferred recursive axiom-set, of Any old > truth in this model). It also means that some of the true (in > N) sentences that you CAN prove are going to have proofs that > are RIDICULOUSLY longer than the length of those true > sentences. > From the viewpoint of PA, it may well be that both Fermat's > Last Theorem and Goldbach's conjecture are "like G". [G is the > Godel sentence.] At any given stage of the process, things that > are "like G" (in the sense that they are Pi_1 sentences that > are true in your intended model but that you can't prove from > your axioms) may be abundant. All this means is that if your > intended/standard model really is that much more important to > you than all the other models, then you need more axioms to > approximate it. But it also means that approximation is what > you will have to settle for (no amount of axioms will get you > all the way there, if your axioms are simple enough that you > can recognize one in recursive time). Godel showed that the statement G is true in N (the numbers) but not derivable from PA.