Origin of self-reference in math I'm wondering about how self-reference enters in the math used in Godel's incompleteness theorem (GIT), for example.
From what I've read so far about GIT, self-reference enters the conversation by saying words like, "It's possible to construct" or "It allows or permits one to construct" statements that refer to themselves using numbers, etc. But this does not say that such construction are a necessary implication of the axioms of math. So the question is whether these self-referential statements are a necessary implication or not.
As it is, the language of "allows one to construct" or "it's possible to construct" seems to be something a free will agent can arbitrarily choose to employ at his convenience. It seems to be an imposition from outside the axiomatic system that is expected to be considered true though not provable from within that system. This language, in and of itself, seems to be the source of the incompleteness that is then proven by using it. 
Further thoughts:
I've tried reading through GIT. I get some of it, but I don't work with this kind of mathematics everyday. So I have questions of course. Now the concept of "provable" concerns me. That some statement is provable in the system, as I understand it, mean that the statement is implied by the axioms of the system. OK. So for every valid statement, there is a sequence of implications from the axioms to that statement. But I wonder whether it is possible to start with the statement in question and work backwards to the  axiom. For just because there is an implication from A to B does not mean there is an implication from B to A. Whether an arbitrary statement in question can be implied by its axioms seems to require a view of things from outside the system. It seems in order to prove that an arbitrary statement is implied (and thus provable) would require every possibly implied statement to be generated by the system to see if one of them is the statement in questions. Is that even doable?
 A: This is just a quirk of exposition. So let's be precise. The self-reference claim being made is:

For any formula $\sigma(x)$ there is a sentence $\varphi_\sigma$ such that $T$ proves the sentence $$\varphi_\sigma\leftrightarrow\sigma(\underline{\ulcorner\varphi_\sigma\urcorner}),$$ 

where


*

*$T$ is our theory in question (e.g. first-order Peano arithmetic), 

*"$\ulcorner \cdot\urcorner$" is the Godel numbering function, and 

*for $n\in\mathbb{N}$, $\underline{n}$ is the numeral $S(...(S(0))...)$ corresponding to $n$.
There's no "free agent" aspect here: the sentence $\varphi_\sigma$ exists, whether we happen to care about it (or even know about it) or not. Moreover, everything is fully "internal to $T$" - $T$ itself proves the equivalence between $\varphi_\sigma$ and $\sigma(\underline{\ulcorner\varphi_\sigma\urcorner}$).
Indeed, this internality is the crucial part for Godel's argument. Roughly speaking, Godel shows that there is a formula $\hat{\sigma}(x)$ such that for every sentence $\theta$, $T$ proves $\hat{\sigma}(\underline{\ulcorner\theta\urcorner})$ iff $T$ proves $\theta$. Now apply the diagonal lemma to the formula $\neg\hat{\sigma}$; the sentence $\varphi_{\neg\hat{\sigma}}$ then "asserts its own unprovability." 


*

*Incidentally, this argument actually requires more hypotheses on $T$ than strictly necessary: we need to assume that $T$ is $\Sigma_1$-sound, a technical property roughly saying that $T$ doesn't prove any false existence claims (Godel originally used the stronger property of $\omega$-consistency, but that was obvious overkill). A more subtle argument using optimal hypotheses - namely, mere consistency in the usual sense (together with recursive axiomatizability and sufficient strength) - was later cooked up by Rosser. But it's still the right starting point.


So yes, self-reference is a necessary feature of the system(s) in question. (You'll ultimately need to read the proof of the diagonal lemma to understand why, though.)
(It may help de-mystify things to remember that we use the same "agent-flavored" language elsewhere in math - e.g. "we may find a positive $\epsilon$ which is sufficiently small that ..." or "it's possible to construct a function which is continuous but nowhere differentiable.")

Incidentally, a reasonable reaction at this point - if you don't like incompleteness, that is - is to ask, "Why can't we restrict our attention to the non-self-referential part of mathematics?"
However, this turns out to be a non-starter: the question of whether (fixing a formula $\sigma$ of interest) a sentence $\varphi$ "asserts its own $\sigma$-ness" is in general undecidable. So you'll never be completely confident that a sentence you're interested in is non-self-referential with respect to $\sigma$.
It's also worth remembering that incompleteness exists even in the context of very concrete problems: the MRDP theorem (or rather, the proof of the MRDP theorem) shows that for any "appropriate" theory $T$ there is a Diophantine equation $\mathcal{E}_T$ which has no solution but which $T$ cannot prove has no solution. 
So self-reference, and more generally incompleteness, are just things we'll all have to live with.
A: Here is a puzzle by Raymond Smullyan that really illuminates the idea.
Suppose we have a machine that prints the symbol N,P,A, and - and only those symbols.  If X is any string of symbols, then the string X-X is called the associate of X.  For example, the associate of P is P-P.
The machine only prints strings of symbols called "sentences". A sentence has one of the following forms, whose meaning is indicated in parentheses. 


*

*P-X ("X is printable.")

*NP-X ("X is not printable.")

*PA-X ("The associate of X is printable.")

*NPA-X ("The associate of X is not printable.")
The machine prints only true sentences, and is so constructed that any sentence it can print will eventually be printed.  "Printable" in the above descriptions means that this particular machine will eventually print the string X.  
Prove: There is a true sentence that the machine cannot print.
Here are some examples, in case the meaning is not clear.
P-P is false, because P is not a sentence, and the machine cannot print it.
NP-P is true, as we have just seen.
P-NP-P may be true or false, depending on the particular machine.  We know that NP-P is true, but whether or it's printable depends on the machine.
The problem is to show that for any machine of this type, there is a true sentence that it cannot print. 
Hint: Look for a sentence that means, "This sentence is not printable." 
ANSWER

 NPA-NPA  

