Skip to main content
5 of 5
added 131 characters in body
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

Which sentences are "irreducibly" self-referential over $\mathsf{PA}$?

Previously asked at MSE. Below, all sentences/formulas are in the language of arithmetic, and for simplicity we conflate numbers with numerals and sentences with Godel numbers.


Say that a sentence $\varphi$ is irreducibly self-referential iff there is a formula $\chi(x)$ such that the following are equivalent for all sentences $\psi$:

  1. $\mathsf{PA}\vdash\varphi\leftrightarrow\psi$.

  2. $\mathsf{PA}\vdash\psi\leftrightarrow\chi({\psi})$.

  3. $\mathsf{PA}\vdash \chi({\psi})\leftrightarrow\varphi$.

(Note that the 1/2 equivalence implies that $\mathsf{PA}\vdash \varphi\leftrightarrow\chi(\varphi)$. Also, this isn't a typo: I really do want to require an "equivalence of provable equivalences" here.)

Intuitively, the 1/2-equivalence asserts that when we interpret $\varphi$ as saying "I have property $\chi$," we don't lose any information about $\varphi$: any two ways of whipping up such a sentence result in the same meaning. The 2/3-equivalence is a bit weirder. It says that we can't remove the self-referential aspect of $\varphi$ by shifting the referent to $\psi$: if $\varphi$ could be rephrased as "$\psi$ has property $\chi$," then $\psi$ already involves the same type of self-reference as $\varphi$.

Basically, if $\varphi$ is irreducibly self-referential via $\chi$, then (modulo a special consideration for the role of $\mathsf{PA}$) reading $\varphi$ as "I have property $\chi$" is completely justified: not only is there no information lost (corresponding to inequivalent fixed points), but there is also no unnecessary self-reference added.

My question is simply:

Is there a snappy description of the irreducibly self-referential sentences? (Also, what if anything changes if we look instead at $\mathsf{PA}$-provably i.s.r. sentences?)

It's consistent with my understanding so far that every sentence is irreducibly self-referential, or that only the decidable sentences are irreducibly self-referential. Obviously each of these outcomes would be a bit boring; my hope is that i.s.r. actually provides a nontrivial dividing line amongst the independent sentences, but I have no evidence for that at the moment. (And in fact, the way these things tend to go I do suspect that one or the other of the "boring" outcomes holds for simple reasons, I just don't see the argument yet.)


Here are a couple easy observations:

  • Non-example: Let $\chi=\neg\mathsf{Prov}_{\mathsf{PA}}$ be the usual unprovability predicate for $\mathsf{PA}$, and let $\varphi$ be a fixed point for that predicate. It is known that any two fixed points of $\neg\mathsf{Prov}_\mathsf{PA}$ are $\mathsf{PA}$-provably equivalent, so $\varphi$ satisfies the 1/2-equivalence. However, taking $\psi=\perp$ we see that $\varphi$ fails to satisfy the 1/3-equivalence: $\mathsf{PA}\vdash\neg\mathsf{Prov_{PA}}(\perp)\leftrightarrow\varphi$ is true (indeed this is how we establish the 1/2 equivalence for $\varphi$) but $\mathsf{PA}\vdash\perp\leftrightarrow\varphi$ is (hopefully!) not. So the usual Godel sentence is not irreducibly self-referential via $\neg\mathsf{Prov}_{\mathsf{PA}}$ ... although in principle it could be irreducibly self-referential via some other formula.

  • Silly examples: On the other hand, the unmodified provability formula $\mathsf{Prov_{PA}}(-)$ does show that every $\mathsf{PA}$-theorem is irreducibly self-referential. Suppose $\mathsf{PA}\vdash\varphi$ and $\psi$ is some other sentence. By Lob's Theorem, condition (2) is equivalent to $\mathsf{PA}\vdash\psi$, which in turn is equivalent to condition $(1)$ since $\mathsf{PA}\vdash\varphi$, and we clearly have condition $(1)$ implying condition $(3)$. Meanwhile, soundness of $\mathsf{PA}$ + $\mathsf{PA}\vdash\varphi$ also shows that $(3)$ implies $\mathsf{PA}\vdash\psi$, which gives us $(1)$. A related argument via non-disprovability gives the i.s.r.-ness of every $\mathsf{PA}$-disprovable sentence. (Thanks to Fedor Pakhomov and Sridhar Ramesh for fixing very silly errors in this part!)

Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331