Listing the hyperarithmetical functions

Gian Marco Osso; Isabella Scott; Joseph S. Miller

arxiv: 2605.21194 · v1 · pith:4TMWKLXAnew · submitted 2026-05-20 · 🧮 math.LO

Listing the hyperarithmetical functions

Joseph S. Miller , Gian Marco Osso , Isabella Scott This is my paper

Pith reviewed 2026-05-21 01:19 UTC · model grok-4.3

classification 🧮 math.LO

keywords hyperarithmeticTuring idealdominating functionlist of functionsweak listhyperjumpSigma-0-2

0 comments

The pith

A real computes a list of all hyperarithmetic functions if and only if it dominates every such function and the hyperjump is Sigma-0-2 relative to it.

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

The paper studies when a real can serve as an enumeration of every function inside a countable Turing ideal. For several natural ideals it establishes that this happens exactly when the real dominates all functions belonging to the ideal. For the hyperarithmetic ideal the authors obtain a sharper equivalence: domination must be supplemented by the condition that the hyperjump is definable at the Sigma-0-2 level from the real. They also produce hyperarithmetic-dominating reals that fail to compute even a weak list of the hyperarithmetic functions, thereby answering a question left open in prior work, and extend the negative result to every countable ideal closed downward under hyperarithmetic reduction.

Core claim

For a countable Turing ideal I, x computes a list of I precisely when the sections of x recover exactly the members of I. The authors prove that this is equivalent to x computing a dominating function for several natural ideals. They further show that x computes a list of the hyperarithmetic ideal if and only if x is hyperarithmetic-dominating and O is Sigma-0-2(x). They also exhibit hyperarithmetic-dominating reals that compute no weak list of the hyperarithmetic ideal and generalize the separation to any countable ideal downward closed under hyperarithmetic reducibility.

What carries the argument

A list of an ideal I is a real x whose sections x^[n] recover exactly the functions in I; the key additional mechanism for the hyperarithmetic case is the requirement that the hyperjump O be Sigma-0-2 definable from x.

If this is right

For several natural countable Turing ideals, computing a list is equivalent to computing a dominating function.
Hyperarithmetic-strongly null engulfing does not guarantee even a weak list of the hyperarithmetic functions.
The separation between domination and listing extends to every countable ideal that is downward closed under hyperarithmetic reducibility.
Any real computing a list of the hyperarithmetic ideal must be hyperarithmetic-dominating and must render O Sigma-0-2 definable from it.

Where Pith is reading between the lines

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

The extra definability condition on the hyperjump may separate domination from listing in other reducibility notions.
Concrete oracles where the hyperjump fails to be Sigma-0-2 could be checked directly against the characterization.
The construction of separating reals might adapt to other countable ideals that are not downward closed under hyperarithmetic reduction.

Load-bearing premise

The standard definitions of countable Turing ideals and hyperarithmetic reducibility hold, along with the prior result that hyperarithmetic-strongly null engulfing implies hyperarithmetic-domination.

What would settle it

A real x that dominates every hyperarithmetic function, makes O Sigma-0-2 relative to x, yet whose sections miss some hyperarithmetic function would falsify the claimed characterization.

read the original abstract

Given a countable Turing ideal $\mathcal{I} \subseteq \omega^{\omega}$, we say that $x$ is a list (resp. weak list) of $\mathcal{I}$ if $\mathcal{I}=\{x^{[n]} : n \in \omega\}$ (resp. if $\mathcal{I} \subseteq \{x^{[n]} :n \in \omega\}$). We show that, for several natural ideals $\mathcal{I}$, $x$ computes a list of $\mathcal{I}$ if and only if it computes a function dominating all the functions in $\mathcal{I}$. On the other hand, we provide reals which are $\mathsf{HYP}$-strongly null engulfing (and hence $\mathsf{HYP}$-dominating, by results of Greenberg, Kuyper and Turetsky) but which cannot compute a weak list for $\mathsf{HYP}$, solving a problem left open in a recent paper by Greenberg and the second author. This result can be generalized to any countable ideal which is downward closed under $\leq_{\mathsf{HYP}}$. We also give a characterization of reals which compute a list of $\mathsf{HYP}$: $x$ computes a list of $\mathsf{HYP}$ if and only if $x$ is $\mathsf{HYP}$-dominating and $\mathcal{O}$ is $\Sigma^0_2(x)$.

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

The paper solves an open problem by separating HYP-domination from weak listing and adding a characterization via the hyperjump O.

read the letter

This paper claims to close a question left open by Greenberg and the second author: whether every HYP-dominating real can weakly list the hyperarithmetic sets. It answers no, by exhibiting reals that are HYP-strongly null engulfing (hence dominating, via the Greenberg-Kuyper-Turetsky result) yet fail to compute even a weak list for HYP. The same separation is said to extend to any countable ideal downward closed under HYP-reducibility. A second result gives an exact characterization: a real lists HYP if and only if it is HYP-dominating and the hyperjump O is Sigma^0_2 relative to it. For several other natural ideals the paper equates listing with domination outright. These are the concrete advances. The work is useful because it organizes the distinction between domination and listing inside the hyperarithmetic ideal and supplies a clean necessary-and-sufficient condition involving O. The abstract is clear about what is claimed and what is new relative to the cited prior papers. The main limitation is that only the abstract is available, so there is no way to inspect the constructions or verify that the counterexamples really avoid weak listing while satisfying the engulfing property. The argument also rests on the earlier domination result without re-proving it, which is acceptable if that result is already accepted but leaves the new claims dependent on it. The paper is aimed at specialists in computability theory who care about ideals, domination, and hyperarithmetic reducibility. A reader already following work on HYP and null engulfing will find the equivalences and the counterexample directly relevant. It is worth sending to peer review so that the constructions and the proof of the O characterization can be checked in detail.

Referee Report

0 major / 1 minor

Summary. The paper studies listing and weak listing of countable Turing ideals I, focusing on the hyperarithmetic ideal HYP. It establishes that for several natural ideals, a real x computes a list of I if and only if x computes a function dominating all members of I. It constructs reals that are HYP-strongly null engulfing (hence HYP-dominating) yet fail to compute a weak list of HYP, resolving an open problem of Greenberg and the second author; this is generalized to any countable ideal downward closed under ≤_HYP. A characterization is given: x computes a list of HYP if and only if x is HYP-dominating and O is Σ^0_2(x).

Significance. If the stated equivalences, counterexamples, and characterization hold, the work clarifies the computational strength needed to enumerate hyperarithmetic functions and relates domination, strong null engulfing, and listing properties in a precise way. It builds directly on the Greenberg-Kuyper-Turetsky result that HYP-strongly null engulfing implies HYP-domination and supplies falsifiable predictions via the listed equivalences and the explicit characterization involving the jump O.

minor comments (1)

The abstract is compact and assumes familiarity with terms such as 'HYP-strongly null engulfing' and 'downward closed under ≤_HYP'; a brief parenthetical reminder or reference to the relevant prior definitions would aid readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the paper and for recognizing the significance of the results in clarifying the relations between listing, weak listing, domination, and strong null engulfing for countable Turing ideals, particularly HYP. The 'uncertain' recommendation is understandable given that only the abstract was available to the referee. The full manuscript is posted on arXiv:2605.21194 and contains the complete proofs of all stated equivalences, the counterexample construction resolving the open problem from Greenberg and the second author, the generalization to downward-closed ideals, and the characterization involving HYP-domination and the jump O being Sigma^0_2(x). We have no specific major comments to address point by point.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The abstract states new equivalences for natural ideals (list iff dominating), provides explicit counterexamples to an open question from prior work, generalizes to downward-closed ideals under ≤_HYP, and gives a characterization (list of HYP iff HYP-dominating and O is Σ^0_2(x)). These rely on standard definitions of Turing ideals and hyperarithmetic reducibility plus one external citation to Greenberg-Kuyper-Turetsky for the engulfing-to-domination implication. No equation, definition, or claim in the available text reduces a result to a self-definition, fitted parameter, or unverified self-citation chain by construction; the cited implication and open-problem reference are not load-bearing for the new constructions or characterization. With only the abstract available and no internal derivations shown that collapse to inputs, the paper's claims remain independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper works entirely within established concepts of computability theory; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

standard math Standard properties of countable Turing ideals and the hyperarithmetic reducibility relation ≤_HYP
All definitions of list, weak list, domination, and the generalization rest on these background notions from recursion theory.

pith-pipeline@v0.9.0 · 5741 in / 1308 out tokens · 54385 ms · 2026-05-21T01:19:31.122133+00:00 · methodology

Listing the hyperarithmetical functions

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)