On a Question of Hamkins'

This paper resolves Joel Hamkins' question by proving that no extensional Rosser formula of any complexity exists, while demonstrating that a positive answer holds under the weaker condition of "Conditional Extensionality," which allows for a $\Pi^0_1$-formula that is both extensional and $\Pi^0_1$-flexible.

The Gist

Here is an explanation of Albert Visser's paper, "On a Question of Hamkins'," translated into everyday language using analogies.

The Big Picture: The "Truth-Teller" Game

Imagine you are playing a game with a very strict, logical referee named PA (Peano Arithmetic). PA is a rulebook for math that is incredibly smart but has a known flaw: it cannot prove everything that is true (thanks to Gödel's famous Incompleteness Theorems).

A mathematician named Joel Hamkins asked a tricky question:

"Can we design a special 'Truth Detector' (a formula $\rho$) that looks at any math statement ($\phi$) and tells us if it's true or false, in such a way that:

1. Independence: If the rulebook plus the statement is consistent, the detector can say 'True' OR 'False' without breaking the rules.
2. Extensionality (The Golden Rule): If two statements mean the exact same thing logically, the detector must give them the exact same answer."

Visser's paper is the answer to this game.

---

Part 1: The Impossible Dream (The "No" Answer)

The Goal: Hamkins wanted a detector that is Extensional.
The Analogy: Imagine a judge who must treat two people exactly the same if they are wearing the exact same outfit (logically equivalent). If Person A and Person B are wearing identical suits, the judge must give them the same verdict.

The Result: Visser proves this is impossible.
No matter how clever you are, you cannot build a Truth Detector that satisfies both conditions at once.

Why? (The Paradox Trap)
Visser uses a classic logic trap (similar to the "Liar Paradox").

1. Imagine the detector looks at a statement that says, "I am not detected as True."
2. If the detector says "True," the statement is false.
3. If the detector says "False," the statement is true.
4. Because the detector must be "Extensional," it treats this tricky statement the same way it treats a known contradiction (like $2+2=5$).
5. This forces the detector to contradict itself, breaking the consistency of the whole system.

The Takeaway: You cannot have a perfect, logical "Truth Detector" that treats equivalent statements identically and remains independent. The rules of logic forbid it.

---

Part 2: The Compromise (The "Yes, But..." Answer)

Since the perfect version is impossible, Visser asks: "What if we relax the rules?"

He introduces a weaker version of the Golden Rule called Conditional Extensionality.

• Old Rule (Extensionality): If $A$ and $B$ are equivalent, the detector says the same thing about them always.
• New Rule (Conditional Extensionality): If $A$ and $B$ are equivalent, the detector says the same thing about them only if we are currently assuming A is true.

The Analogy:
Imagine a detective who is investigating a crime.

• Old Rule: The detective must treat two suspects identically even if one of them is innocent and the other is guilty, just because they look alike. (This leads to chaos).
• New Rule: The detective says, "If I assume Suspect A is the culprit, then I will treat Suspect B (who looks like A) exactly the same way."
  This is a much more flexible and realistic rule.

The Result:
Visser proves that YES, you can build a detector that works under this weaker rule!
Furthermore, this detector is "Flexible."

• Flexibility Analogy: Imagine a chameleon. If you tell the chameleon, "Assume the background is red," it can turn red. If you say, "Assume the background is blue," it can turn blue. It can adapt to any consistent scenario without breaking.
  Visser shows that this new detector can adapt to any $\Pi^0_1$ statement (a specific type of math claim) without causing a contradiction.

---

Part 3: How the New Detector Works (The "Slow Cooker")

How did Visser build this flexible detector? He didn't use a standard "proof" method. He used something called "Slow Provability."

The Analogy:

• Standard Proof: Like a race car. It checks if a statement is true as fast as possible. If it can't prove it quickly, it gives up.
• Slow Proof: Like a slow cooker. It checks if a statement is true, but it only uses "ingredients" (axioms) that are "small" or "safe" according to a specific, slow-growing scale.

Visser's detector looks at a statement and asks: "Can this be proven using only the 'small' axioms?"
Because the definition of "small" changes depending on the context (the statement $\phi$), the detector can be "flexible." It can say "True" in one context and "False" in another, even if the statements look similar, because the "smallness" scale shifted.

This allows the detector to avoid the paradox trap that broke the "perfect" detector. It essentially says, "I will only judge you based on the rules of the specific room you are currently in."

---

The Open Question: The "Middle Ground"

Visser leaves one door slightly ajar.
He solved the "Perfect" version (Impossible) and the "Weak" version (Possible).
But there is a middle ground called Consistent Extensionality.

• The Question: What if the detector only has to treat equivalent statements the same if those statements don't lead to a contradiction?
• The Status: We don't know yet. Visser says this is the next big mystery to solve. It's like asking, "Can we have a chameleon that changes color based on the room, but only if the room isn't on fire?"

Summary in One Sentence

Joel Hamkins asked if we can have a perfect, unchanging logic detector; Albert Visser proved that's impossible, but showed we can build a flexible, context-aware detector that works almost as well, leaving just one small mystery unsolved.

Technical Summary

Here is a detailed technical summary of the paper "On a Question of Hamkins'" by Albert Visser.

1. Problem Statement

The paper addresses a specific question posed by Joel Hamkins (Question 28 in [Ham22]) regarding the existence of a specific type of formula in Peano Arithmetic (PA).

The Question: Does there exist a $\Pi^0_1$-formula $\rho(x)$ satisfying two specific properties?

1. Independence: If the theory $PA + \varphi$ is consistent, then both $PA + \varphi + \rho(\ulcorner\varphi\urcorner)$ and $PA + \varphi + \neg\rho(\ulcorner\varphi\urcorner)$ are consistent.
2. Extensionality: If $PA \vdash \varphi \leftrightarrow \psi$, then $PA \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$.

A formula satisfying both is termed an extensional Rosser formula. Hamkins asked if such a formula exists with complexity restricted to $\Pi^0_1$. Visser investigates whether this is possible, and if not, what happens if the Extensionality condition is weakened.

2. Methodology

Visser employs techniques from provability logic, fixed-point theory, and the study of "slow provability" and "uniform provability." The methodology is divided into two main parts: a negative proof for full extensionality and a positive construction for conditional extensionality.

A. Negative Result (Non-existence of Extensional Rosser Formulas)

Visser proves that no extensional Rosser formula exists, regardless of complexity, for any consistent theory $U$ extending the Tarski-Mostowski-Robinson theory $R$.

• Proof Strategy: The proof uses a diagonalization argument involving fixed points.
  1. Assume such a $\rho(x)$ exists.
  2. Construct fixed points: $\varphi_0 \leftrightarrow \rho(\ulcorner\varphi_0\urcorner)$ and $\varphi_1 \leftrightarrow \neg\rho(\ulcorner\varphi_1\urcorner)$.
  3. By the Independence property, $U \vdash \neg \varphi_0$ and $U \vdash \neg \varphi_1$.
  4. By Extensionality, since $\varphi_0$ and $\varphi_1$ are both provably equivalent to $\bot$ (false), $\rho(\ulcorner\varphi_0\urcorner)$ and $\rho(\ulcorner\varphi_1\urcorner)$ must be provably equivalent to $\rho(\ulcorner\bot\urcorner)$.
  5. This leads to a contradiction: $U \vdash \rho(\ulcorner\bot\urcorner)$ and $U \vdash \neg\rho(\ulcorner\bot\urcorner)$, violating the consistency of $U$.
• Conclusion: The combination of Independence and full Extensionality is impossible.

B. Positive Result (Conditional Extensionality and Flexibility)

Visser then weakens the Extensionality requirement to Conditional Extensionality:

• Definition: If $PA \vdash \varphi \leftrightarrow \psi$, then $PA + \varphi \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$.

Under this weaker condition, Visser constructs a $\Pi^0_1$-formula that satisfies Independence and a stronger property called $\Pi^0_1$-Flexibility.

• $\Pi^0_1$-Flexibility: If $PA + \varphi$ is consistent, then for any $\Pi^0_1$-sentence $\pi$, the theory $PA + \varphi + (\rho(\ulcorner\varphi\urcorner) \leftrightarrow \pi)$ is consistent.
• Construction Technique:
  1. Uniform Provability: The paper defines a notion of "uniform provability" where proofs are bounded by a parameter $x$.
  2. Smallness: A number $x$ is defined as "$\varphi$-small" if all $\Sigma^0_1$ sentences provable from $\varphi$ with proofs of size $\leq x$ are true. This relies on the principle that while the "outer world" (standard model) may contain large numbers, the "inner world" (within a consistent extension) sees them as small.
  3. Slow Provability: The formula $\triangle_\varphi \psi$ is defined as "$\psi$ is provable from $\varphi$ using only $\varphi$-small axioms."
  4. The Formula: The target formula is $\rho(x) := \triangle_x \top$ (specifically, the consistency statement of the theory with "slow" axioms).
  5. Verification: Using the Emission ($\Box_\varphi \psi \to \Box_\varphi \triangle_\varphi \psi$) and Absorption ($\Box_\varphi \triangle_\varphi \psi \to \Box_\varphi \psi$) theorems, Visser shows that this construction satisfies the Lob conditions and the required flexibility properties.

3. Key Contributions and Results

1. Negative Resolution of Hamkins' Original Question:
   Visser definitively answers "No" to the existence of an extensional Rosser formula. The proof shows that the combination of Independence and full Extensionality leads to inconsistency for any theory extending $R$.

2. Introduction of Conditional Extensionality:
   The paper introduces and validates Conditional Extensionality as a viable alternative. It proves that there exists a $\Pi^0_1$-formula that is:

   • Independent (in the Rosser sense).
   • Conditionally Extensional.
   • $\Pi^0_1$-Flexible: This is a significant strengthening of the Rosser property, showing the formula can be made equivalent to any $\Pi^0_1$ sentence within the consistent extension.

3. Refinement of Shavrukov-Visser Results:
   The paper builds upon a previous result by Shavrukov and Visser ([SV14]) which provided a $\Delta^0_2$ formula with Conditional Extensionality. Visser improves this by:

   • Reducing the complexity from $\Delta^0_2$ to $\Pi^0_1$.
   • Proving $\Pi^0_1$-flexibility (a stronger independence property).

4. Open Question (Consistent Extensionality):
   The paper leaves open the question of Consistent Extensionality:

   • Definition: If $PA \nvdash \neg \varphi$ and $PA \vdash \varphi \leftrightarrow \psi$, then $PA \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$.
   • This condition sits strictly between full Extensionality (impossible) and Conditional Extensionality (possible). The status of a Rosser formula satisfying this intermediate condition remains unknown.

4. Significance

• Clarification of Independence Properties: The paper clarifies the precise boundaries of what is possible regarding "Rosser-style" independence formulas. It demonstrates that full extensionality is too strong a constraint to coexist with independence.
• Advancement in Provability Logic: The construction of the $\Pi^0_1$-flexible formula using "slow provability" and "uniform smallness" provides new tools for analyzing the structure of consistent extensions of arithmetic.
• Terminological Precision: The paper distinguishes between "extensional" (provable equivalence implies equivalence of the formula) and "conditionally extensional" (equivalence holds within the context of the assumption), highlighting a subtle but crucial distinction in the behavior of provability predicates.
• Superseding Preprint: The abstract notes that this preprint is superseded by a more recent work (ArXiv:2506.13524) by Kurahashi and Visser, suggesting that the field is rapidly evolving, but this paper establishes the foundational negative result and the positive construction for the conditional case.

In summary, Visser proves that while a "perfect" extensional Rosser formula is impossible, a highly flexible and conditionally extensional $\Pi^0_1$ formula can be constructed, effectively solving Hamkins' problem in a modified, yet mathematically rich, form.