14
$\begingroup$

Below, all sentences/formulas are first-order and in the language of arithmetic. For simplicity, we conflate numbers and numerals, and conflate sentences/formulas and their Godel numbers.

Given a formula $\varphi(x)$ and a sentence $\theta$, say that $\theta$ asserts its own $\varphi$-ness iff $\mathsf{PA}\vdash\theta\leftrightarrow\varphi(\theta).$ Let $\mathsf{SR}(\theta)$ be the set of $\varphi$ such that $\theta$ asserts its own $\varphi$-ness. Bounded truth predicates show that $\mathsf{SR}(\theta)$ is never empty. I'm curious how much $\mathsf{SR}(\theta)$ could actually depend on $\theta$; in particular, if there's a lot of potential variety here, this might give a meaningful notion of "degree of self-referentiality" of a sentence.

Here's one way to make this precise:

Are there sentences $\theta,\theta'$ such that $\mathsf{SR}(\theta)\not\cong\mathsf{SR}(\theta')$ as partial orders?

The partial ordering I have in mind is provability: $\sigma\le\rho$ iff $\mathsf{PA}\vdash\forall x[\sigma(x)\rightarrow\rho(x)]$. By considering bounded truth predicates, $\mathsf{SR}(\theta)$ always contains a copy of $\mathbb{Z}$: briefly, look at $\tau_n^+(x)=$ "$x$ is a true $\Sigma_n$ sentence" and $\tau_n^-(x)=$ "$x$ is not a false $\Sigma_n$-sentence" for $n$ sufficiently large. Another "canonical" element is the formula $\varphi(x)\equiv\theta$ (basically, "ignore input, output $\theta$"). Finally, $\mathsf{SR}(\theta)$ is always a distributive lattice. Beyond this, however, I don't see anything useful.

Improve this question
$\endgroup$
2
  • $\begingroup$ Since the formulas $\varphi$ in SR($\theta$) have a free variable, when you say the order is provability, I guess you mean that PA proves $\varphi(x)\to\psi(x)$, i.e., $\forall x\ \varphi\to\psi$. Right? $\endgroup$
    – Joel David Hamkins
    Commented Dec 6, 2022 at 22:46
  • $\begingroup$ @JoelDavidHamkins Yes, that's right. I've edited for clarity. $\endgroup$
    – Noah Schweber
    Commented Dec 6, 2022 at 22:47

1 Answer 1

Reset to default
9
$\begingroup$

If $\varphi$ is not required to behave the same way on Gödel codes of equivalent sentences or any such thing, then $\mathsf{SR}(\theta)$ is always equivalent to the preorder on all arbitrary formulas, by defining in PA a bijection $f$ between $\mathbb{N} - \{\theta\}$ and $\mathbb{N}$, and noting that any formula $\varphi$ gives rise to a formula $\varphi' \in \mathsf{SR}(\theta)$ via $\varphi'(\theta) = \theta$ and $\varphi'(n) = \varphi(f(n))$ for $n \neq \theta$.

We have that $\varphi \leq \psi$ iff $\varphi' \leq \psi'$, and that every formula $\varphi \in \mathsf{SR}(\theta)$ is equivalent to some $\psi'$ (specifically, take $\psi(n) = \varphi(f^{-1}(n))$). Thus, the map $\varphi \mapsto \varphi'$ is an equivalence from the preorder of arbitrary formulas to the preorder $\mathsf{SR}(\theta)$.

Improve this answer
$\endgroup$
9
  • 4
    $\begingroup$ Very nice. In particular, SR($\theta$) is a Boolean algebra under provable equivalence---for negation, you just negate all the other coordinates except the fixed-point coordinate, so it is still a fixed-point, but the conjunction is minimal amongst fixed-points. $\endgroup$
    – Joel David Hamkins
    Commented Dec 7, 2022 at 0:58
  • 2
    $\begingroup$ This has been SR on SR (self-reference). $\endgroup$
    – Sridhar Ramesh
    Commented Dec 7, 2022 at 1:02
  • 1
    $\begingroup$ Can we hope to use the same idea, but just change the formula on the coordinates of the provably equivalent to $\theta$ coordinates? PA proves this is an equivalence relation on the codes, even if it doesn't prove all the facts about that relation. $\endgroup$
    – Joel David Hamkins
    Commented Dec 7, 2022 at 1:55
  • 1
    $\begingroup$ Yes, I believe we could just do that (where "provably equivalent to $\theta$ coordinates" means coordinates which satisfy a predicate in the language of PA asserting there is a proof that they are equivalent to $\theta$; thus, we would get different behavior at all coordinates $\psi$ for which PA proves $\Box (\theta \leftrightarrow \psi)$ and not just those coordinates for which PA proves $\theta \leftrightarrow \psi$). But I think that'd be enough to show a basically similar result that all $\mathsf{SR}(\theta)$ are the same, in that context, depending on how exactly we formalize things.). $\endgroup$
    – Sridhar Ramesh
    Commented Dec 7, 2022 at 1:59
  • 1
    $\begingroup$ Well, some formalities turn on exactly what level of externality vs internality we choose to define the equivalence-respecting condition at, so I'll leave it at that until the revised question is more formalized. $\endgroup$
    – Sridhar Ramesh
    Commented Dec 7, 2022 at 2:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.