Is there a proof of Gödel's Incompleteness Theorem without self-referential statements?

Question

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?

Answer 1

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).

Answer 2

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 ($*$).

Answer 3

There is this one, that I have heard of but not perused myself:

Link

Answer 4

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.

Answer 5

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.