2

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?

Majik Won
  • 21
  • 1
    I recommend “Godel, Escher, Bach” by Douglas Hoffstadter and “Godel’s Proof” by Negel and Newman. – Andrew Estrella Jul 27 '19 at 16:16
  • Natural language is by itself a source of self-reference. The discovery of Godel was that the formal language of arithmetic was sufficiently "strong" to have this feature of natural language. – Mauro ALLEGRANZA Jul 27 '19 at 17:46

2 Answers2

5

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.

Noah Schweber
  • 245,398
  • It's very kind of you to respond. Please see "Further thoughts" at the bottom of the original post. Thank you. – Majik Won Jul 27 '19 at 18:59
  • @MajikWon I don't understand what you say there. What exactly is the problem? Given any set of sentences $T$ and any sentence $\varphi$, either there is a proof of $\varphi$ from $T$ or there isn't a proof of $\varphi$ from $T$; and there is a formula in the language of $T$ expressing appropriately the existence of such a proof (as long as $T$ is "reasonable"). Can you make your concern more specific? Is there a particular statement or definition you take issue with? – Noah Schweber Jul 27 '19 at 19:06
  • Maybe I'm thinking more logically than mathematically. Yes, either the statement is or is not provable in the system. My concern is there may be no means of proving that a statement can be implied from the axioms. There is no calculation possible. No sequence of implications exist from an arbitrary statement to the axioms. For axioms implying statements is not equivalent to statements implying axioms. The function from arbitrary statement to axioms does not exist because implication (proof?) is a one way street, from axiom to statements. – Majik Won Jul 27 '19 at 19:19
  • @MajikWon I'm still not really sure what you're getting at, honestly. Axioms are sentences, and proofs are very concrete objects with a precise definition. In particular, we can just brute-force-search through proofs! Now this doesn't work for negative results - if $T$ doesn't prove $\varphi$, we might never know since there are infinitely many possible proofs - and in fact as a consequence of Godel's argument the set of consequences of $T$ (for $T$ "appropriate") is not in fact computable. But none of that impacts what's going on here. – Noah Schweber Jul 27 '19 at 19:35
  • And indeed, provability itself is appropriately definable inside arithmetic via Godel numbering (this is the other part of Godel's argument). Incidentally, the precise notion of proof we use in this context does have a semantic justification - it corresponds to "semantic entailment" in a precise sense. (And don't let the name confuse you: there's no tension between the completeness of a logical framework and the incompleteness of a specific theory in that framework.) – Noah Schweber Jul 27 '19 at 19:38
  • "In particular, we can just brute-force-search through proofs! Now this doesn't work for negative results - if T doesn't prove φ, we might never know since there are infinitely many possible proofs"... I think that's my point. If it's not provable, we'll never know it. Isn't this the same as saying that the general function from arbitrary statement to axioms cannot exist. – Majik Won Jul 27 '19 at 19:54
  • @MajikWon No, if it's not provable we might never know it. But that doesn't mean that some axiom systems can't prove that some sentences aren't provable in some other axioms. In particular, our theory $T$ proves "If $T$ is consistent, then $T$ doesn't prove $G_T$" (where $G_T$ is the Godel sentence for $T$); put another way, the theory $T$ + "$T$ is consistent" proves that $T$ doesn't prove $G_T$. And this is basically Godel's incompleteness theorem: if an appropriate theory is consistent, then it doesn't prove its own Godel sentence. – Noah Schweber Jul 27 '19 at 19:56
  • You're mistaking a generally negative result for an entirely negative result. And re: "the general function from arbitrary statement to axioms cannot exist," it sounds like you're conflating truth and provability (or a related conflation, like existence and computability). If you want an entirely internal-to-$T$ version of GIT, here it is: $T$ proves the (appropriately-formulated) sentence "If $T$ is consistent, then $T$ does not prove $G_T$." – Noah Schweber Jul 27 '19 at 19:59
  • Let us continue this discussion in chat. – Majik Won Jul 27 '19 at 19:59
  • So to cap up, correct me if I'm wrong, the self reference occurs by specifying a function, T, that specify its own provability, right? Is this function unique? And do you need an infinite numbering system to prove GIT? Thanks. – Majik Won Jul 27 '19 at 20:37
  • @MajikWon I'm not sure what "function" you're talking about - I don't see a function here. Functions aren't provable, sentences are. (But maybe you're talking about the function sending a formula $\sigma$ to a corresponding $\varphi_\sigma$?) Moreover, $T$ is the theory we're looking at (e.g. Peano arithmetic), not a function. Regardless, nothing here is unique. As to your last question, I'm not sure what you're asking - but you need a Godel numbering which is applicable to all formulas/finite sequences of formulas in order to talk about provability inside the theory, so tentatively "yes." – Noah Schweber Jul 27 '19 at 20:41
4

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

saulspatz
  • 53,131