13
$\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.

$\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$ Dec 6, 2022 at 22:46
  • $\begingroup$ @JoelDavidHamkins Yes, that's right. I've edited for clarity. $\endgroup$ Dec 6, 2022 at 22:47

1 Answer 1

8
$\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)$.

$\endgroup$
9
  • 3
    $\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$ Dec 7, 2022 at 0:58
  • 2
    $\begingroup$ This has been SR on SR (self-reference). $\endgroup$ 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$ 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$ 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$ Dec 7, 2022 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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