← Back to arXiv
arXivLogicarXiv:2609.37478

Pseudo-Hyperjump Inversion Fails for Turing Degrees

The paper resolves an open question in mathematical logic about a specific kind of operator called a "pseudo-hyperjump." To understand the context: computability theorists study ways of measuring the complexity of mathematical objects called "reals" (infinite sequences of 0s and 1s). One way to compare complexity is through "Turing degrees," which group together objects of the same computational strength. An "operator" takes a real as input and produces a more complex real as output. The classical hyperjump is a well-known such operator, and pseudo-hyperjumps are a broad family of generalizations that satisfy a certain definability condition. A natural question is whether these operators are "invertible" in a useful sense: if you know the output's complexity level, can you always find an input that produces it? This is called inversion.

Jananthan and Simpson conjectured that every pseudo-hyperjump operator should admit inversion above a certain benchmark level of complexity known as Kleene's O. The paper disproves this conjecture by constructing a specific operator that acts as a genuine counterexample. The constructed operator always produces an output strictly more complex than its input, which might make you expect it to cover a wide range of complexity levels. Yet the authors show it completely skips over an entire interval of Turing degrees sitting just above Kleene's O. In other words, there is a whole stretch of complexity levels that the operator can never hit, no matter what input you feed it.

Beyond settling the main conjecture, the paper also dismantles three related properties that Jananthan and Simpson had identified as potential routes to proving the conjecture. Since each of those properties would have implied the conjecture, and the conjecture is now false, none of those properties can hold for any collection of reals whatsoever, even without imposing any definability restrictions. This collapses a broader research program aimed at characterizing certain natural classes of reals through these jump-like operators, showing the approach is fundamentally limited.

Read original →