A uniformly, extremely nonextensional formula of arithmetic with many undecidable fixed points in many theories

Abstract:

It is proved that there is a single unary formula $F$ of Peano arithmetic PA and a fixed infinite set $\mathcal {E}$ of fixed points $\phi$ of $F$ in PA with the following property. Let $T$ be any recursively enumerable, $\Sigma _1^0$-sound extension of PA. Then (i) almost all $\phi$ in $\mathcal {E}$ are undecidable in $T$, and (ii) for all such $\phi$ and all equivalence relations $E$ satisfying reasonable conditions and refining provable equivalence in $T$ (but not depending on $\phi$ or $T$) there is a sentence $\psi$ equivalent to $\phi$ via $E$ which is not a fixed point of $F$ in $T$. The theorem furnishes an extreme instance of the difficulties encountered in trying to introduce quantification theory into the diagonalizable algebras of Magari, and yet preserve a central theorem about these structures, the De Jongh-Sambin fixed point theorem. The construction is designed for further applications.