Is there a proof of Gödel's Incompleteness Theorem without self-referential statements? 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?
 A: 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.
A: 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).
A: 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 ($*$).
A: There is this one, that I have heard of but not perused myself:
Link
A: 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.
A: Here's a direct computability-theoretic argument. Suppose $T$ is an "appropriate" theory. Let $A,B$ be two disjoint c.e. sets, and let $A_T=\{x: T\vdash x\in A\}$ and $B_T=\{x:T\vdash x\not\in A\}$. Each $A_T$ and $B_T$ is c.e. by definition; since $T$ is complete we have $A_T\sqcup B_T=\mathbb{N}$, and hence they're each computable; and since $T$ is "appropriate" we have $A\subseteq A_T$ and $B\subseteq B_T$. But this gives us a contradiction: just take $A,B$ to be a pair of computably inseparable c.e. sets.
Of course, how do we know that computably inseperable c.e. sets exist? Well, this in turn is a straightforward trick with a universal Turing machine: we set $$A=\{e:\varphi_e(e)\downarrow =0\}\quad\mbox{and}\quad B=\{e:\varphi_e(e)\downarrow=1\}.$$ By definition, $A$ and $B$ are disjoint c.e. sets (and note that if $\varphi_e(e)\uparrow$ then $e$ is not in $A$ or $B$).
Now suppose $C$ were a computable separator for $A$ and $B$; that is, $C$ is computable, $A\subseteq C$ and $B\cap C=\emptyset$. Let $\varphi_c$ be the total computable characteristic function of $C$ - that is, $$C=\{x:\varphi_c(x)\downarrow=1\}.$$ We now have two cases:


*

*If $c\in C$, then $\varphi_c(c)=1$. But then we have $c\in B$, contradicting the assumption that $C\cap B=\emptyset$.

*If $c\not\in C$, then $\varphi_c(c)=0$. But then we have $c\in A$, contradicting the assumption that $A\subseteq C$.
Note that crucially "$\varphi_c(c)\uparrow$" is not an option - since $\varphi_c$ is total.

There's no self-reference at all there: the closest we come is in the verification step of our construction of computably inseparable c.e. sets, but that's not actually self-reference (feeding an existing object its own "name" is different from building an object which somehow "knows its own name ahead of time"). This is exactly the diagonalization versus self-reference point.
