Source-linked AI summary
Jump Closure and Limit Uniformization in the Ideal Completion of the Turing Degrees
Miara Sung
TL;DR
The paper asks how the absence of jump fixed points on individual Turing degrees changes after ideal completion and how limit coding extends the resulting fixed ideal. It lifts jump closure to a Scott-continuous operator on ideals and introduces a monotone, non-Scott-continuous uniformization gate. The resulting closure ordinals are ω, ω · 2, and ω2, with uniformization reopening diagonalization.
Problem
Individual Turing degrees have no jump fixed point, while the distinction between successor jumps and limit-stage uniform coding requires an ideal-theoretic account.
Method
The paper uses ideal completion to study Scott-continuous jump closure and defines limit uniformization to adjoin a uniform code only after all stages of an increasing degree sequence are present.
Results
The first closure ordinals of the semantics are ω, ω · 2, and ω2.
Takeaways & Limitations
Non-uniform jump closure reaches fixed ideals, whereas uniformly coding an infinite prior hierarchy is discontinuous and restarts diagonalization.
Takeaways & Limitations
Extending the construction to arbitrary recursive ordinals requires careful stage indexing and deriving notation invariance from classical hyperarithmetic machinery.
Abstract
from arXiv · showhide
The Turing jump has no fixed point on the Turing degrees: $\mathbf a <_T \mathbf a'$ for every degree $\mathbf a$. After passing to the ideal completion, however, a natural fixed-point phenomenon appears. We study the Scott-continuous lifting $Γ:\operatorname{Idl}(\mathbf D_T)\to\operatorname{Idl}(\mathbf D_T)$, given by $Γ(I)=\downarrow\{\mathbf a':\mathbf a\in I\}$. Starting from the computable degree, Kleene iteration reaches its first fixed point at stage $ω$, namely the Turing ideal of arithmetical degrees; more generally, above $\mathbf a$ the least fixed point is the ideal of degrees arithmetical in $\mathbf a$. To pass beyond this fixed point, we introduce a limit-uniformization operator. Although the ideal of finite jumps contains every $\mathbf 0^{(n)}$, it does not contain the uniform limit oracle $\mathbf 0^{(ω)}=°_T\!\left(\bigoplus_{n < ω}0^{(n)}\right)$. The uniformization operator adjoins this oracle only when all finite jump degrees are present. It is monotone but not Scott-continuous. Composing jump closure with one such gate yields closure ordinal $ω\cdot 2$; gates at $ω,2ω,3ω,\ldots$ yield closure ordinal $ω^2$. Thus non-uniform closure under relativized halting problems is Scott-continuous and reaches fixed ideals, while uniform coding of an entire prior hierarchy is infinitary, discontinuous, and reopens diagonalization. This gives a domain-theoretic semantics for the successor/limit distinction in transfinite Turing-jump hierarchies and links failures of Scott continuity with closure ordinals.
1 Introduction
The paper reframes the successor/limit structure of transfinite Turing-jump hierarchies through ideal completion: jump closure reaches fixed ideals, while limit uniformization is discontinuous and reopens diagonalization.
- Motivation: Individual Turing degrees have no jump fixed point, but collections of degrees can be closed under taking jumps.Turing ideals closed under the jump occur as second-order parts of ω-models of arithmetical comprehension.
- Ideal completion: Ideal completion treats directed lower sets as completed informational states and extends the Turing jump to a Scott-continuous operator Γ on ideals.Principal ideals embed the original degrees as compact approximants.
- Fixed point: At stage ω, iteration from the computable degree reaches the ideal of arithmetical degrees, which is already jump-closed.By Post’s theorem, this ideal is precisely the arithmetical degrees, and its closure ordinal is exactly ω.
- Limit distinction: The arithmetical ideal contains every finite jump non-uniformly but excludes 0(ω), whose uniform coding packages all finite jumps into one oracle.Admitting 0(ω) allows its relativized halting problem to reopen the jump hierarchy.
- Limit uniformization: Limit uniformization waits for every member of an increasing sequence before adjoining a uniform code, making it monotone but not Scott-continuous.The all-stages requirement has no finite witness and detects completion of an infinite directed chain.
- Closure ordinals: One uniformization gate at ω gives closure ordinal ω · 2, while gates at successive ω-block boundaries give closure ordinal ω2.The construction decomposes the semantics into continuous non-uniform jump closure and discontinuous uniform escape operations.
2 Turing degrees and ideal completion
The paper represents Turing degrees through their ideal completion, where directed lower sets serve as completed informational states. This type shift lets a progressive operation such as the jump acquire a nonprincipal fixed point.
- Turing ideals: A Turing ideal is a nonempty downward-closed set of degrees closed under binary joins.
- Turing ideals: Turing ideals are equivalently directed lower subsets of the Turing degrees ordered by inclusion.
- Ideal completion: The ideal completion embeds each degree as a principal ideal and forms a dcpo whose directed suprema are unions.
- Canonical lifting: For any monotone map on a poset, the canonical ideal-completion extension is Scott-continuous.
- Type shift: The completion permits a progressive operation to lack fixed points among principal elements while possessing a nonprincipal fixed point.
3 The jump-closure fixed point
The lifted jump has exactly the jump-closed Turing ideals as fixed points. Starting from any degree, its least fixed point is reached at stage ω; from the computable degree, this is the ideal of arithmetical degrees.
- Fixed points: The lifted jump is inflationary, and its fixed points are exactly the jump-closed Turing ideals.
- Least fixed point: The least fixed point above degree a is the union of its finite iterated jumps, reached at closure ordinal ω.
- Iteration: No finite stage is fixed because each finite jump strictly increases the degree.
- Computable base: For the computable degree, this fixed point is the ideal of degrees of arithmetical sets.
- Nonprincipality: No principal Turing ideal is fixed by the lifted jump, so the fixed point is intrinsically nonprincipal.
4 Uniformization at a limit
The finite-jump ideal contains every individual finite jump but not their uniform limit oracle. A uniformization gate adds that oracle only after the entire chain is present, making the operator monotone and inflationary but not Scott-continuous.
- Limit information: The arithmetical fixed point contains every finite jump degree but excludes the uniform limit oracle 0^(ω).
- Uniformity: Uniform membership of all finite stages does not provide one ideal element from which the whole sequence can be uniformly recovered.
- Uniformization gate: A uniformization gate waits until a strictly increasing degree chain is complete, then makes its designated uniform upper bound available.
- Discontinuity: The uniformization operator is monotone and inflationary but not Scott-continuous.
- Discontinuity: Its discontinuity arises because completion of the entire chain cannot be witnessed by any finite member of a directed system.
- Renewed progression: After uniformization escapes the jump-closed ideal, diagonalization resumes, so fixed closure and renewed diagonalization alternate.
5 A closure ordinal of ω · 2
Combining jump closure with one uniformization gate produces two successive ω-blocks: the first closes finite jumps, and the gate packages that block into a uniform limit oracle. The resulting closure ordinal is exactly ω · 2.
- Combined operator: The combined operator is monotone and inflationary but not Scott-continuous.
- Closure ordinal: The closure ordinal of the combined operator from ↓0 is exactly ω · 2.
- No earlier fixed stage: No earlier stage is fixed: successor stages move under the jump, and the stage ω ideal moves under uniformization.
- First ω-block: The first ω-block closes under all finite jumps, while limit uniformization packages that block into 0^(ω).
- Second ω-block: A second ω-block then closes under every finite jump relative to the new uniform limit oracle.
- Limit repetition: The resulting ideal contains every 0^(ω+n) but not the next uniform limit oracle 0^(ω·2).
6 Finite blocks and closure ordinal ω2
Finite block operators alternate successor jump closure with uniformization gates at block boundaries. With gates at every finite multiple of ω, the least fixed point is reached at closure ordinal ω^2, and no earlier stage is fixed.
- Uniformization gates adjoin jωk when the corresponding finite-jump ideal Aωk is already present.
- For every integer m ≥1, the finite-block operator Θm has closure ordinal ωm and a least fixed point.
- At successor stages, strict jump progression prevents stabilization; at block boundaries, the corresponding gate forces further movement.
- The operators with gates are not Scott-continuous because they can adjoin 0(ω) at the union of an ω-chain although no finite stage contains it.
7 Halting problems, transfinite jumps, and ordinal analysis
The paper distinguishes individual degrees, jump-closed ideals, and uniform limit degrees, using this distinction to explain successor/limit behavior and operator-dependent closure ordinals. It frames future work around canonical transfinite operators while limiting its own analysis to ω^2.
- Three distinct objects: An individual degree is never fixed under the jump, whereas a jump-closed Turing ideal can be fixed under non-uniform jump closure.
- Three distinct objects: The uniform limit degree 0(ω) packages the preceding hierarchy into one oracle but lies outside the fixed ideal it codes.
- Three distinct objects: Uniformization triggers a new jump sequence, 0(ω) → 0(ω+1) → ···, because the newly introduced uniform oracle is subject to diagonalization.
- Successor and limit operations: Successor jump closure is Scott-continuous, while limit uniformization requires an entire cofinal family and therefore fails Scott continuity.
- Ordinal analysis: Closure ordinals describe operators and approximation architectures rather than Turing degrees alone; here ω^2 reflects repeated block dependencies.
- Open problems and scope: The proposed general program seeks recursive-ordinal operators whose closure ranks are representation-invariant and whose discontinuities occur at limit-uniformization nodes.
- Open problems and scope: The paper addresses semantic closure ordinals only through ω^2, not the proof-theoretic strength of theories formalizing these constructions.
8 Relation to bounded informational fixed points
The jump-ideal construction parallels bounded informational fixed points: finite-dependency operators stabilize at an ω-chain, while uniformization requires an entire cofinal chain and changes continuity and closure behavior.
- A local extension operator based on finite observations forms an ascending chain whose Scott supremum is reached at ω.
- Finite dependency, rather than literal self-simulation time, determines the bounded operator’s informational progression.
- The jump-ideal operator Γ is Scott-continuous, so its iterative closure is exhausted by an ω-chain.
- Uniformization marks the first non-finite dependency: a gate must receive the entire cofinal chain before firing.
- The Turing jump supplies canonical computational successor operations for a broader hierarchy of informational operators.
9 Discussion
The discussion reframes the absence of fixed points for individual Turing degrees through ideal completion, where non-uniform jump closure reaches fixed ideals but uniformization reopens diagonalization. It relates this distinction to closure ordinals while identifying a broader canonical-presentation question.
- Passing to ideal completion changes the fixed-point structure without changing the individual-degree impossibility theorem.
- The canonical ideal extension is Scott-continuous, and its least fixed point above a is the ideal of degrees arithmetical in a.
- The true closure equation captures memberwise relativized halting closure, whereas the contrasting uniform limit construction does not internalize the entire hierarchy in one oracle.
- Limit uniformization detects completion of an infinite directed chain, fails Scott continuity, and makes the new oracle subject to the jump again.
- The broader open question is whether effective transfinite jump hierarchies have a canonical domain-theoretic presentation recovering recursive ordinal structure from characterized failures of finite information and Scott continuity.