Is there a formal definition of a number theoretical statement which is self-referential?

Question

Let our structure be $(\mathbb{N};+,\times,0,1,<)$. From that structure, Kurt Godel constructed a sentence which has two meanings, a straight-forward number-theoretical meaning, and a higher-level self-referential meaning which basically says, "I am not provable in Peano Arithmetic". But, is there a rigorous definition somewhere of a number-theoretical statement which is self-referential? For example, we can all agree that "$5$ is a prime number" is not self-referential. So, has anyone proposed a formal definition of the intuitive concept of self-referential statement? Or, is this another of those things which is "you know it when you see it"?

Answer 1

I think this is a great question! My personal take would be that there is no fully satisfying formalization yet known, but there also is no convincing argument yet that no such formalization can exist. Incidentally, I strongly recommend the books Diagonalization and self-reference (Smullyan) and Self-reference and modal logic (Smorynski) if you can get your hands on them (they're hard to find).

(For a variety of reasons I'm going to work over a theory - namely first-order Peano arithmetic $\mathsf{PA}$, although the details won't matter - rather than a structure; basically, this is Godelian rather than Tarskian, and is ultimately in my opinion the right way to set things up.)

---

Let's start with the following naive notion:

Given a formula $\varphi(x)$, a sentence $\theta$ asserts its own $\varphi$-ness iff $$\mathsf{PA}\vdash \theta\leftrightarrow\varphi(\underline{\ulcorner\theta\urcorner}).$$ A sentence $\theta$ is naively self-referential iff there is some formula $\varphi$ such that $\theta$ asserts its own $\varphi$-ness.

(Note that I'm choosing a specific Godel numbering here. We could also vary the numbering, and the question of what a "Godel numbering" really is is a great one, but to me that's a separate question so I'm punting for now.)

Now naive self-referentiality has the nice property of being perfectly formal. However, it's also pretty boring: just take as our choice of $\varphi$ the formula $\tau_n(x)=$ "$x$ is the Godel number of a true $\Sigma_n$ sentence" for some sufficiently large $n$. (This doesn't contradict Tarski, since a different $\tau_n$ is needed for different $n$s. Tarski just rules out a single $\tau$ doing the job for all $n$.) $\mathsf{PA}$ proves the "deflation scheme" $\eta\leftrightarrow\tau_n(\underline{\ulcorner\eta\urcorner})$ whenever $\eta$ is $\Sigma_n$, so this works.

So naive self-referentiality joins the long list of natural-at-first-but-actually-SUPER-BORING ideas in logic. But beating dead horses is great exercise, so let's not stop there. I think that naive self-referentiality is actually unsatisfying for an even deeper reason!

Specifically, I would argue the informal interpretation of $\theta$ as being (rather than merely behaving as) the natural-language sentence "I am $(\Sigma_n$-)true" is not justified by the mere fact that $$(*)\quad\mathsf{PA}\vdash\theta\leftrightarrow\tau_n(\underline{\ulcorner\theta\urcorner}).$$ This is because lots of other sentences also satisfy $(*)$ in place of $\theta$ - namely, any other sentence of the same (or lesser) syntactic complexity. So it seems that information is lost when we choose to construe $\theta$ as self-referential on the basis of $\tau_n$ (for sufficiently large $n$) alone.

Interestingly, a "dual" of this objection can be levied against the Godel sentence itself! This is because it turns out to be $\mathsf{PA}$-provably-equivalent to $\mathsf{Con(PA)}$, and $\mathsf{Con(PA)}$ (I would argue) doesn't have any compelling self-referential character. These two objections together motivate (in my opinion) a strengthening of naive self-reference: informally, say that $\theta$ is irreducibly self-referential iff for some $\varphi$ there is no $\mathsf{PA}$-meaningful difference between being $\theta$ and being a $\varphi$-fixed-point. The precise definition can be found at this old question of mine, asking whether the notion is in fact nontrivial. Sadly, that question is open, and the initial optimism I had has long since faded: I now suspect that either every sentence is irreducibly self-referential, or only the $\mathsf{PA}$-decidable sentences are irreducibly self-referential, and neither of these options is interesting.

Going back to naive self-reference, we could shift attention to the set of ways that a given sentence is naively self-referential instead of the simple yes/no question "is there naive self-reference at all." Specifically, for $\theta$ a sentence let $$\mathsf{NSR}(\theta)=\{\varphi: \theta\mbox{ asserts its own $\varphi$-ness}\}.$$ Maybe some $\theta$s have "larger" $\mathsf{NSR}$s than others; conversely, we could try to "weight" elements of $\mathsf{NSR}(\theta)$ based on how uniquely they pin down $\theta$ (e.g. $\tau_n\in\mathsf{NSR}(\theta)$ whenever $\theta\in\Sigma_n$, so $\tau_n$ should carry little weight in this sense). At the very least, we could look for interesting structural comparisons here. As far as I know, this is largely unexplored. But even if there's something interesting here, note that we would be unlikely to get a clean divide between "self-referential" and "non-self-referential" - rather, we'd more likely see a spectrum of possibilities. I've asked a question which can be thought of as a naive first step in this direction at MathOverflow.