I am interested in different contexts in which Gödel's incompleteness theorems arise. Besides traditional Gödelian proof via arithmetization and formalization of liar paradox it may also be obtained from undecidability results of Turing and Church. In the context of complexity theory, it is not hard to see that Gödel's theorem (as well as Turing's result) follows from the following Chaitin's result: there exists some natural number N such that for any program P of size more than N it is impossible to prove (say, in ZFC) that it is the smallest (in the sense of size, i. e. number of bits) of those programs which have the same inputs-outputs as P has. The number N depends on particular axiomatic system (say, ZFC) and is not very large so that it actually can be calculated.
If You know other ways towards Gödel's incompleteness theorems, please, present them. Particularly, can Goedel's theorem be obtained without use of self-referential ideas?
Best Answer
Apart from usual proofs with diagonalization, have a look at model-theoretic proofs (Kotlarski's proof, Kreisel's left-branch proof, etc..), then there are some other proofs that formalize paradoxes (Kikuchi's, Boolos's, etc... there are about a dozen, most of them mentioned in Kotlarski's book).
If you don't want full generality ("for every rec. ax. theory T") then of course almost every proof in modern Unprovability Theory does not use any self-reference (you build a model of your theory by hands, using some unprovable combinatorial principle). Have a look at some easy recent accessible model-theoretic proofs of the Paris-Harrington Principle.
At the low end of the consistency strength spectrum (ISigma_n, PA, ATR_0), for theories that already have good classifications of their provably recursive functions, PH and other unprovable statements can also be proved unprovable using ordinal analysis (e.g. Ketonen-Solovay style), without using diagonalization tricks.
For higher ends of the strength spectrum (SMAH, SRP, etc), H. Friedman's highly technical results also don't use any diagonalization. This is a huge powerful machinery, and much new research is happening there.
MDRP theory gives interesting examples: have a look at the Jones polynomial expression: you can indeed substitute numbers into it and hit every consistency statement by its instances. There are similar ones for n-consistency for each n.
There is much more to say: this is a big subject, with huge bibliography. And, yes, much of the body of results in the subject is unpublished. I can give more pointers if necessary.