arxiv: 2604.28067 · v2 · submitted 2026-04-30 · 🧮 math.LO

Recognition: unknown

Hallucination, abstention, and computable inseparability

Takuma Imamura

Pith reviewed 2026-05-08 02:53 UTC · model grok-4.3

classification 🧮 math.LO

keywords hallucinationabstentioncomputable inseparabilityarithmetical hierarchyseparatorundecidabilityformal domains

0 comments

The pith

Abstaining systems that avoid hallucination cannot guarantee correct answers on large domains in expressive formal languages.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that abstention avoids giving incorrect definite answers in yes-or-no formal domains but cannot do so while covering arbitrarily large sets of inputs. Any abstaining system that answers yes on every member of one set and no on every member of a disjoint set must compute a separator for those sets. Classical results show that certain pairs of sets in the arithmetical hierarchy have no computable separator, so abstention forces a choice between covering both sides of such a pair or risking hallucination on one. This creates a precise trade-off: larger domains of guaranteed correct answers require accepting the possibility of wrong definite outputs on some inputs.

Core claim

Given disjoint sets A and B, any system that answers Yes on all queries indexed by A and No on all queries indexed by B induces a separator of A from B. By combining this observation with the classical existence theorem of Δ_n^0-inseparable pairs of Σ_n^0-sets, abstention yields a computability-theoretic trade-off between avoiding hallucination and maintaining a large domain of guaranteed coverage in sufficiently expressive formal domains.

What carries the argument

The reduction showing that an abstaining yes-no answerer on disjoint sets A and B computes a separator for A and B, which cannot exist for Δ_n^0-inseparable Σ_n^0 pairs.

If this is right

For each n there exist disjoint sets A and B such that no abstaining system can correctly answer yes on all of A and no on all of B while remaining hallucination-free on both.
The largest possible domain of guaranteed non-abstaining answers for a hallucination-avoiding system is bounded above by the non-existence of separators for inseparable pairs.
Classical undecidability theorems extend directly to abstention mechanisms once domains contain inseparable sets from the arithmetical hierarchy.
Abstention can eliminate hallucination only by restricting coverage to sets that admit computable separations at the relevant level.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same inseparability argument may limit the size of safe answer sets in any computational model that attempts to decide statements from expressive formal languages.
Neighbouring problems such as partial computable functions or oracle computations could admit analogous trade-offs between abstention and coverage.
Explicit constructions of inseparable pairs could be used to test whether concrete abstaining procedures achieve the maximal possible safe domain size.

Load-bearing premise

That any system answering yes exactly on all members of A and no exactly on all members of B must induce a computable separator of A from B.

What would settle it

An explicit computable function that separates some pair of sets previously shown to be Δ_n^0-inseparable would falsify the claimed trade-off at that level of the hierarchy.

read the original abstract

The impossibility of eliminating hallucination, understood here as incorrect definite answers, in sufficiently expressive yes-or-no formal domains is an immediate consequence of classical undecidability theorems. This note does not revisit that forced-answer obstruction as its main claim. Instead, it attempts to formally describe the corresponding limitation for abstaining systems. Abstention can trivially avoid hallucination if the system is allowed to abstain on every input; the substantive question is how large the domain of guaranteed correct non-abstaining answers can be. We formulate this question using separation in the arithmetical hierarchy. Given disjoint sets $A$ and $B$, any system that answers Yes on all queries indexed by $A$ and No on all queries indexed by $B$ induces a separator of $A$ from $B$. By combining this observation with the classical existence theorem of $\Delta_{n}^{0}$-inseparable pairs of $\Sigma_{n}^{0}$-sets, we yield a computability-theoretic trade-off between avoiding hallucination by abstention and maintaining a large domain of guaranteed coverage.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

A direct application of arithmetical inseparability that cleanly bounds safe coverage for abstaining systems in formal domains.

read the letter

The main thing to know is that this note shows abstaining systems cannot safely answer on large domains in expressive formal settings without either hallucinating or abstaining too much, because any definite yes/no pattern on disjoint sets A and B would separate them, and classical results supply inseparable pairs at each level of the hierarchy. It is a short, focused observation rather than a deep new theorem. What it does well is state the modeling step plainly: a system that answers yes exactly on A and no exactly on B induces a separator, then invokes the standard existence of Δ_n^0-inseparable Σ_n^0 pairs to get the coverage-versus-abstention trade-off. The argument stays within classical recursion theory, adds no free parameters, and keeps the AI interpretation secondary to the computability fact. That keeps it honest and easy to check. The soft spots are minor and proportional. The note assumes the formal domain is rich enough to contain the relevant inseparable pairs, which holds for most interesting logics but is not illustrated with a concrete example. It also treats the abstaining system as inducing a computable separator at the right level, which fits the setting but leaves open how non-computable or hybrid AI components would change the picture. Neither issue undercuts the central claim. This is for readers who already know the arithmetical hierarchy and want a precise way to think about reliability limits in formal AI tasks. A logician or theoretical computer scientist working on verification or AI safety would find it useful as a quick reference point. I would send it to peer review as a short note; the observation is solid, the application is new, and referees can easily assess whether the modeling needs more detail.

Referee Report

0 major / 3 minor

Summary. The paper claims that while abstention can avoid hallucination (incorrect definite answers) in yes-or-no formal domains, there is a computability-theoretic limit on the size of the domain of guaranteed correct non-abstaining answers. Any system that answers Yes exactly on all members of a set A and No exactly on all members of a disjoint set B induces a separator of A from B. Combining this modeling observation with the classical existence of Δ_n^0-inseparable pairs of Σ_n^0 sets (for each n) yields an inherent trade-off: larger guaranteed-coverage domains require stronger separators that cannot exist at the corresponding level of the arithmetical hierarchy.

Significance. If the central observation holds, the note supplies a clean, parameter-free link between AI-style abstention mechanisms and classical recursion-theoretic inseparability results. It quantifies, in terms of the arithmetical hierarchy, how much abstention is forced once a domain is sufficiently expressive, without introducing new axioms or fitted parameters. This framing may be useful for formalizing reliability bounds in computable systems that must sometimes refuse to answer.

minor comments (3)

The abstract refers to 'the classical existence theorem of Δ_n^0-inseparable pairs of Σ_n^0-sets' without a specific citation or theorem number; adding a reference (e.g., to Post or to a standard text on the arithmetical hierarchy) would help readers locate the precise statement being invoked.
The modeling step—that a system answering Yes exactly on A and No exactly on B 'induces a separator'—is stated concisely in the abstract. A short paragraph in the body clarifying the precise sense in which the system's decision procedure is assumed to be Δ_n^0 (or recursive) would make the reduction fully explicit.
The manuscript is described as 'this note'; if it is intended as a short communication, a brief concluding paragraph summarizing the precise trade-off statement (e.g., 'no Δ_n^0 system can guarantee coverage on both sides of an inseparable pair') would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive recommendation to accept and for the accurate summary of the paper's central observation. No major comments were raised, so we have no points requiring revision or further defense.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's derivation applies a standard definitional observation—that a system answering Yes exactly on all of A and No exactly on all of B induces a computable separator of A from B—to the classical, externally established existence of Δ_n^0-inseparable pairs of Σ_n^0 sets. This produces a trade-off result in the arithmetical hierarchy without any self-definitional reduction, fitted-parameter predictions, load-bearing self-citations, or ansatz smuggling. The argument remains self-contained against independent recursion-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the classical existence of inseparable pairs in the arithmetical hierarchy and on the modeling of abstention as set separation; no free parameters or new entities are introduced.

axioms (1)

standard math For each n there exist Δ_n^0-inseparable pairs of Σ_n^0 sets
Classical theorem in recursion theory invoked to establish the trade-off.

pith-pipeline@v0.9.0 · 5477 in / 1254 out tokens · 49083 ms · 2026-05-08T02:53:16.306620+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

7 extracted references · 4 canonical work pages

[1]

Calibrated language models must hallucinate,

[Online]. Avail- able: https://projecteuclid.org/ebooks/perspectives-in-logic/Metamathematics- of-First-Order-Arithmetic/toc/pl/1235421926 A. T. Kalai and S. S. Vempala, “Calibrated language models must hallucinate,” inProceedings of the 56th Annual ACM Symposium on Theory of Computing, ser. STOC

work page arXiv
[2]

TruthfulQA: Measuring How Models Mimic Hu- man Falsehoods,

New York, NY, USA: Association for Computing Machinery, 2024, p. 160–171. [Online]. Available: https://doi.org/10.1145/3618260.3649777 S. Lin, J. Hilton, and O. Evans, “TruthfulQA: Measuring How Models Mimic Hu- man Falsehoods,” inProceedings of the 60th Annual Meeting of the Association for Computational Linguistics, vol

work page doi:10.1145/3618260.3649777 2024
[3]

3214–3252

Association for Computational Linguist- ics, 2022, pp. 3214–3252. P. Odifreddi,Classical Recursion Theory, 1st ed., ser. Studies in Logic and the Foundations of Mathematics. North Holland,

2022
[4]

Über der Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die Addition als einzige Operation hervortritt,

M. Presburger, “Über der Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die Addition als einzige Operation hervortritt,” in Comptes Rendus Premier Congrès des Mathématicienes des Pays Slaves, Varso- vie 1929, F. Leja, Ed., 1930, pp. 92–101. H. Rogers, Jr.,Theory of Recursive Functions and Effective Computability. The MIT Press,

1929
[5]

A decision method for elementary algebra and geometry,

[Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19580040705 A. Tarski, “A decision method for elementary algebra and geometry,” inQuantifier Elimination and Cylindrical Algebraic Decomposition, B. F. Caviness and J. R. Johnson, Eds. Vienna: Springer Vienna, 1998, pp. 24–84. A. M. Turing, “On computable numbers, with an applicatio...

work page doi:10.1002/malq.19580040705 1998
[6]

Software

[Online]. Available: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230 B. Wen, J. Yao, S. Feng, C. Xu, Y. Tsvetkov, B. Howe, and L. L. Wang, “Know your limits: A survey of abstention in large language models,”Transactions of the Association for Computational Linguistics, vol. 13, pp. 529–556,

work page doi:10.1112/plms/s2-42.1.230
[7]

Hallucination is inevitable: An innate limita- tion of large language models,

[Online]. Available: https://aclanthology.org/2025.tacl-1.26/ Z. Xu, S. Jain, and M. Kankanhalli, “Hallucination is inevitable: An innate limita- tion of large language models,”

2025