On a Question of Hamkins’

Albert Visser · 2025

Read On a Question of Hamkins’ by Albert Visser (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09109.txt.

Introduction

Albert Visser, writing alone in two thousand twenty-five, took up a logic question posed by Joel Hamkins. The question asks whether a special kind of formula can stay unproven in a system, in a way that treats equal statements the same. Visser works within Peano arithmetic, a standard system for number logic.

He shows that no such formula can meet the full demand, at any level of complexity. He then gives a positive answer for a weaker demand, which he calls conditional extensionality, with an even stronger result. One case stays open: what happens under consistent extensionality, a demand between the two.

Catalog record

CREATORAlbert Visser
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09109

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On a Question of Hamkins’ Albert Visser Abstract . Joel Hamkins asks whether there is a Π 1 0 \Pi^{0}_{1} -formula ρ ⁡ ( x ) \rho(x) such that ρ ⁡ ( ⌜ ​ φ ​ ⌝ ) \rho({\ulcorner\varphi\urcorner}) is independent over 𝖯𝖠 + φ {\sf PA}+\varphi , if this theory is consistent, where this construction is extensional in φ \varphi with respect to PA -provable equivalence. We show that there can be no such extensional Rosser formula of any complexity. We give a positive answer to Hamkins’ question for the case where we replace Extensionality by a weaker demand that we call Conditional Extensionality . For this case, we prove an even stronger result, to wit, there is a Π 1 0 \Pi^{0}_{1} -formula ρ ⁡ ( x ) \rho(x) that is extensional and Π 1 0 \Pi^{0}_{1} -flexible. We leave one important question open: what happens when we weaken Extensionality to Consistent Extensionality, i.e., Extensionality for consistent extensions? Consistent Extensionality is between full Extensionality and Conditional Extensionality. 2020 Mathematics Subject Classification 03F30, 03F40 This preprint is superseded by preprint ArXiv:2506.13524, Extensional Independence , by Taishi Kurahashi and Albert Visser 1. Introduction In his paper [ Ham22 ] , Joel Hamkins asks the following question (Question 28). 1 1 1 For notational consistency with the rest of this notes we changed the variable-names in the formulation of the question. Is there a \Pi^{0}_{1} -formula \rho(x) with the following properties? Independence: If {\sf PA}+\varphi is consistent, then so are {\sf PA}+\varphi+\rho({\ulcorner\varphi\urcorner}) and {\sf PA}+\varphi+\neg\,\rho({\ulcorner\varphi\urcorner}) . Extensionality: If {\sf PA}\vdash\varphi\leftrightarrow\psi , then {\sf PA}\vdash\rho({\ulcorner\varphi\urcorner})\leftrightarrow\rho({\ulcorner\psi\urcorner}) . We call a formula that satisfies both Independence and Extensionality an extensional Rosser formula . We allow an extensional Rosser formula to be of any complexity. We answer Hamkins’ question negatively. There simply is no extensional Rosser formula, not just over PA , but over a wide range of theories. We will show that, if we weaken Extensionality to Conditional Extensionality, Hamkins’ question gets a positive answer. What is more, in this case, we can strengthen independence to \Pi^{0}_{1} -flexibility . Specifically, we prove that there is a \Pi^{0}_{1} -formula \rho(x) over PA with the following properties. \Pi^{0}_{1} -Flexibility: If {\sf PA}+\varphi is consistent, then, for all \Pi^{0}_{1} -sentences \pi , the theory {\sf PA}+\varphi+(\rho({\ulcorner\varphi\urcorner})\leftrightarrow\pi) is consistent. Conditional Extensionality: If {\sf PA}\vdash\varphi\leftrightarrow\psi , then {\sf PA}+\varphi\vdash\rho({\ulcorner\varphi\urcorner})\leftrightarrow\rho({\ulcorner\psi\urcorner}) . The proof of our result is an adaptation of the methods of [ Vis21 ] . The notion of flexibility was introduced by Saul Kripke in [ Kri62 ] . We will call our formula \rho(x) an extensional \Pi^{0}_{1} -reflexive formula . Remark 1.1 . Kripke also studies flexibility not just for sentences but also for formulas. This introduces an ambiguity. Our \rho(x) is \Pi^{0}_{1} -flexible in the sense that certain sentential instances are \Pi^{0}_{1} -flexible sentences. Thus, parametrised sentence would perhaps be the better terminological choice for our notion over formula . To avoid clumsy wording we will persist in using flexible formula . The reader will have to keep the context of the paper in mind to get the right reading. ❍ Our result leaves the following question open. Open Question 1.2 . Is there a Rosser formula that satisfies the following weakened form of Extensionality. Consistent Extensionality: Suppose {\sf PA}\nvdash\neg\,\varphi and {\sf PA}\vdash\varphi\leftrightarrow\psi . Then, we have {\sf PA}\vdash\rho({\ulcorner\varphi\urcorner})\leftrightarrow\rho({\ulcorner\psi\urcorner}) . See also Remark 2.2 . ❍ We feel that Hamkins’ problem is only partially solved as long as Question 1.2 remains open. 2. There are no Extensional Rosser Formulas In this section, we prove that there is no formula that is both independent and extensional, thus answering Hamkins’ original question in the negative. Theorem 2.1 . Let U be any consistent theory that extends the Tarski-Mostowski-Robinson theory R . Then, there are no extensional Rosser formulas over base theory U . Note that we do not need any constraint on the complexity of the axiom set of U . Proof. Suppose \rho(x) is an extensional Rosser formula over U . We form the fixed points \vdash\varphi_{0}\leftrightarrow\rho({\ulcorner\varphi_{0}\urcorner}) and \vdash\varphi_{1}\leftrightarrow\neg\,\rho({\ulcorner\varphi_{1}\urcorner}) . By Independence, we find (a) \vdash\neg\,\varphi_{0} and \vdash\neg\,\varphi_{1} . So, \vdash\varphi_{0}\leftrightarrow\bot and \vdash\varphi_{1}\leftrightarrow\bot . Thus, by Extensionality, (b) \vdash\rho({\ulcorner\varphi_{0}\urcorner})\leftrightarrow\rho({\ulcorner\bot\urcorner}) and \vdash\rho({\ulcorner\varphi_{1}\urcorner})\leftrightarrow\rho({\ulcorner\bot\urcorner}) . By the Fixed Point Equations in combination with (b), we find (c) \vdash\varphi_{0}\leftrightarrow\rho({\ulcorner\bot\urcorner}) and \vdash\varphi_{1}\leftrightarrow\neg\,\rho({\ulcorner\bot\urcorner}) . By (a) and (c), we find \vdash\neg\,\rho({\ulcorner\bot\urcorner}) and \vdash\rho({\ulcorner\bot\urcorner}) , contradicting the consistency of U . ❑ By minor adaptations of the formulation and the proof, we find a similar result for theories that interpret R . Remark 2.2 . The above argument only uses the special case of Extensionality for inconsistent formulas. So, one may wonder what happens if we simply ban this case. This is our Question 1.2 . We note that Consistent Extensionality implies Conditional Extensionality, for which we have our positive result. Thus, Consistent Extensionality is in the gap between our negative answer and our positive result. ❍ 3. Gödel’s Incompleteness Theorems and Flexibility We briefly revisit Gödel’s Incompleteness Theorems and discuss their connection with \Pi^{0}_{1} -flexibility. 3.1. A Salient Consequence We formulate the for our paper salient consequence of (the proofs of) Gödel’s Incompleteness Theorems. Let U be a c.e. extension of EA . 2 2 2 We can work with a much weaker theory then EA . However, in the present paper, we do not strive for greatest generality. We can find a \Pi^{0}_{1} -formula \gamma such that: Independence: Suppose U+\varphi has property \mathcal{X} . Then, both U+\varphi+\gamma({\ulcorner\varphi\urcorner}) and U+\varphi+\neg\,\gamma({\ulcorner\varphi\urcorner}) are consistent. Monotonicity: Suppose U\vdash\varphi\to\psi . Then, U\vdash\gamma({\ulcorner\varphi\urcorner})\to\gamma({\ulcorner\psi\urcorner}) . What can \mathcal{X} be? It cannot be consistency by Theorem 2.1 . Here are some possibilities. I. U+\varphi is a true arithmetical theory. II. U+\varphi is \omega -consistent. III. U+\varphi is 1-consistent, in other words, U+\varphi satisfies \Sigma^{0}_{1} -reflection. IV. U+\varphi\nvdash\neg\,\gamma({\ulcorner\varphi\urcorner}) . We briefly discuss the ins and outs of these choices in Appendix A . Joel Hamkins in [ Ham22 ] shows that that Independence and Monotonicity cannot be combined under very general conditions. His result also covers a conditional version of Monotonicity. See also Appendix B . 3.2. Flexibility Saul Kripke in his paper [ Kri62 ] proves the existence of flexible predicates for a wide variety of formal theories. Let U be a consistent c.e. extension of EA . We define: \bullet \chi is a \varGamma -flexible sentence (over U ) iff, for all \varGamma -sentences \chi^{\prime} , we have \chi\leftrightarrow\chi^{\prime} is consistent with U . We see that independence is simply \{\top,\bot\} -flexibility. So, we can view \Pi^{0}_{1} -flexibility as a generalisation of the Rosser property. Interestingly, in his paper, Kripke does not discuss the flexibility of the consistency statement. The reason is undoubtedly that he was interested in a Kleene-style proof of a far more general theorem. We work over Elementary Arithmetic EA aka \mathrm{I}\Delta_{0}+{\sf Exp} . Let us first fix some concepts. Let {\sf proof}(x,y) be some standard elementary arithmetisation of ‘ x is a proof from assumptions of y ’. Let the elementary formula {\sf ass}(x,y) stand for ‘ y is an assumption that occurs in y ’. As usual, we assume that {\sf ass}(x,y) implies y<x over EA . We define: \bullet {\sf proof}_{{\langle\alpha\rangle}}(x,y):\leftrightarrow{\sf proof}(x,y)\wedge\forall z<x\,({\sf ass}(x,z)\to\alpha(z)) . \bullet \necessary_{{\langle\alpha\rangle}}\varphi:\leftrightarrow\exists x\,{\sf proof}_{{\langle\alpha\rangle}}(x,{\ulcorner\varphi\urcorner}) . \bullet As usual

Read the complete text