Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements.

My question is, what if one argues that Gödel's Incompleteness Theorem only matters when a formula makes self-reference possible?

Is there any proof of Incompleteness Theorem that does not rely on self-referential statements?

share|improve this question
1  
There are statements that have no hint of self-reference that have been proved to be independent of this or that axiom system, so that very important consequence of the Incompleteness Theorem doesn't rely on self-referential statements. –  Gerry Myerson Jul 17 '12 at 9:20
add comment

5 Answers 5

Roughly speaking, the real theorem is that the ability to express the theory of integer arithmetic implies the ability to express formal logic.

Gödel's incompleteness theorem is really just a corollary of this: once you've proven the technical result, it's a simple matter to use it to construct variations of the Liar's paradox and see what they imply.

Strictly speaking, you still cannot create self-referential statements: the (internal) self-referential statement can only be interpreted as such by invoking the correspondence between external logic (the language in which you are expressing your theory) and internal logic (the language which your theory expresses).

share|improve this answer
7  
The last paragraph here is quite important: The Gödel sentence doesn't know it is speaking about itself; we have to conclude that looking at the formal system from the outside. –  Henning Makholm Jul 17 '12 at 10:56
add comment

There is a rather pretty proof of a standard version of Gödel's First Theorem by Kleene, that extracts it as a corollary of his (Kleene's) Normal Form Theorem. The proof involves diagonalization, but not self-reference. There's a two-page exposition here: http://www.logicmatters.net/resources/pdfs/KleeneProof.pdf

There are two further elementary proofs which don't involve self-reference, whose conclusions are something-a-bit-less-than the full Gödelian result, in Chs 6 and 7 of the second edition of my Gödel book.

Again, both those arguments involve diagonalization. It is diagonalization rather than self-reference which might reasonably be said to be characteristic of typical (though not all) incompleteness proofs.

share|improve this answer
    
Your email address on your site is quite ambiguous. What does "me" mean there? –  Asaf Karagila Apr 25 '13 at 17:32
    
me.com means me.com :-) [you obviously aren't an Apple fanboy, Asaf ...] –  Peter Smith Apr 25 '13 at 17:35
    
I rue the day I got an iPhone and became enslaved to the loathed iTunes! –  Asaf Karagila Apr 25 '13 at 17:41
    
Anyway, prepare to be emailed! (Insert dramatic chord here) –  Asaf Karagila Apr 25 '13 at 18:14
add comment

There is a weaker version of the first incompleteness theorem that is an almost trivial consequence of an insight from computability theory, namely of the result that

  there exists a computably enumerable set that is not computable   (*).  

Consequence: the set of true first-order sentences (i.e. true about the 'real' natural number sequence) is not axiomatizable by a c.e. axiom set.

Unfortunately, most proofs of ($*$) have themselves a scent of self-referentiality hanging around them. However, you may want to check out 'simple sets'. Simple sets are c.e. and not recursive, and the standard textbook-proof of their existence is, to the best of my knowledge, the argument that comes closest to a non-selfreferential argument for ($*$).

share|improve this answer
    
Editing one's own posts does not require any reputation, but since you're unregistered the system doesn't remember that you're you. If you register your account, you'll be able to edit your own posts, and to keep the reputation you earn. –  Henning Makholm Jul 17 '12 at 11:42
add comment

A low-level answer.
Gödel's own undecidable statement (it is now known from Julia Robinson etc.) can be of the form: "Here is a polynomial equation in many variables with integer coefficients. Does it have a solution in positive integers?" There is nothing self-referential about that. But we GOT that equation by coding something that Sarah considers to be self-referential into the polynomial.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.