A Relation on $(\omega, <)$ of Intermediate Degree Spectrum on a Cone

Basic Information

• Paper ID: 2412.01071
• Title: A relation on (ω,<) of intermediate degree spectrum on a cone
• Authors: Jad Damaj and Matthew Harrison-Trainor
• Classification: math.LO (Mathematical Logic)
• Publication Date: November 7, 2025 (arXiv v2: November 5, 2025)
• Paper Link: https://arxiv.org/abs/2412.01071

Abstract

This paper investigates the degree spectrum problem for relations on the natural number linear order $(\omega,<)$. Given an additional relation $R$ on $(\omega,<)$ (such as the successor relation), the degree spectrum of $R$ is the set of Turing degrees of $R$ across all computable copies of $(\omega,<)$. It is known that degree spectra of relations on $(\omega,<)$ fall into four categories: computable degree, all c.e. degrees, all $\Delta^0_2$ degrees, or intermediate spectra between c.e. degrees and $\Delta^0_2$ degrees. Examples of the first three categories are easily constructed, but until recently, whether there exist relations with intermediate spectra "on a cone" remained an open problem. Bazhenov et al. constructed examples of intermediate spectra, but these were "unnatural" (via diagonalization, dependent on choice of Gödel coding). This paper uses the "on-a-cone" framework to restrict study to "natural" relations, with the main result being the construction of a natural relation with intermediate degree spectrum based on structural reasons.

Research Background and Motivation

Core Problems

This paper addresses a fundamental question in computable structure theory: how is the intrinsic complexity of relations characterized through degree spectra. Specifically:

1. Degree Spectrum Classification Problem: Wright proved that degree spectra of relations on $(\omega,<)$ are either singleton sets (computable degree), contain all c.e. degrees, are all $\Delta^0_2$ degrees, or lie between c.e. degrees and $\Delta^0_2$ degrees. Examples of the first three categories are known, but whether true intermediate spectra exist remained unresolved for a long time.
2. Naturality Problem: Bazhenov, Kalociński, and Wrocławski BKW22 constructed examples of intermediate spectra, but this construction:
   • Relies on complex priority arguments and diagonalization
   • Is non-canonical (depends on choice of Gödel coding)
   • Cannot be relativized (intermediate property not preserved relative to 0')
   • Degree spectrum degenerates to c.e. degrees on a cone
3. "On-a-Cone" Framework: To capture the notion of "natural" relations, the paper adopts the "on-a-cone" formalization related to the Martin Conjecture: a property is considered "almost everywhere" true if it holds on all degrees above some fixed Turing degree. This excludes pathological examples dependent on special encodings.

Research Significance

• Theoretical Significance: Completely characterize the structure of degree spectra for relations on $(\omega,<)$, answering fundamental questions in computable structure theory
• Methodological Significance: Demonstrates the effectiveness of the "on-a-cone" framework in excluding unnatural constructions
• Technical Contribution: Develops the theory of coding sequences as a tool that may apply to other structures

Core Contributions

1. Main Theorem (Theorem 3.7): Constructs a computable unary function $f$ whose degree spectrum is strictly intermediate between c.e. degrees and $\Delta^0_2$ degrees on a cone, with cone base being the computable degree (i.e., holds for all oracles)
2. Explicit Description of Natural Relation: The function $f$ has a simple structural description—the domain is divided into cyclic blocks, with odd-positioned blocks enumerating natural numbers as $L_1L_2L_3\ldots$, and even-positioned blocks enumerating them as $L_1L_1L_2L_1L_2L_3\ldots$ so each number appears infinitely often
3. Degree Spectrum Characterization Theorems:
   • Theorem 3.3: A block function's spectrum contains non-c.e. degrees if and only if infinitely many blocks embed into later blocks
   • Theorem 3.6: When all but finitely many blocks embed into subsequent blocks, the spectrum is all $\Delta^0_2$ degrees if and only if there exists an infinite coding sequence
4. Diversity Result (Theorem 4.17): For any even ordinal $\alpha \geq 6$, there exists a block function whose spectrum contains all $\beta$-c.e. degrees ($\beta < \alpha$) but not all $\alpha$-c.e. degrees, proving the existence of uncountably many distinct spectra
5. Technical Innovation: Introduces the concepts of coding sequences and coding trees, developing rank theory for maximal/minimal coding trees to finely characterize degree spectra

Methodology Details

Task Definition

Degree Spectrum: Given a computable structure $\mathcal{A}$ and relation $R$, the degree spectrum is defined as $\text{DgSp}_\mathcal{A}(R) = \{\deg_T(\varphi(R)) : \mathcal{B} \text{ is a computable copy of } \mathcal{A}, \varphi: \mathcal{A} \cong \mathcal{B}\}$

Degree Spectrum on a Cone: A property is said to hold "on a cone" if there exists $X$ such that for all $Y \geq_T X$, the property holds for the relativized spectrum $\text{DgSp}^Y_\mathcal{A}(R)$.

Intermediate Spectrum Problem: Construct a relation $R$ such that on a cone:

• The spectrum strictly contains all c.e. degrees (there exist non-c.e. degrees)
• The spectrum is strictly contained in $\Delta^0_2$ degrees (there exist $\Delta^0_2$ degrees not in the spectrum)

Core Concepts: Block Functions and Coding Sequences

Block Functions

Definition 2.6: A function $f: (\omega,<) \to (\omega,<)$ is a block function if for each $n$, there exists an interval $[a,b]$ containing $n$ that is closed under $f$ and $f^{-1}$. The minimal such interval is called an $f$-block.

Key Properties:

• Blocks are disjoint; the domain decomposes into a union of blocks
• Each block has finite size; all block types $I_n$ can be enumerated
• Corresponds to string $\alpha_f(i) = n$ where $I_n$ is the type of the $i$-th block

Coding Sequences

Definition 3.4: An interval sequence $[a_1,b_1], [a_2,b_2], \ldots$ and maps $\varphi_i: [a_i,b_i] \to [a_{i+1},b_{i+1}]$ form an $f$-coding sequence if:

1. Each interval is closed under blocks
2. $\varphi_i$ is order-preserving non-decreasing embedding
3. $\varphi_{i+1} \circ \varphi_i$ preserves $f$
4. $\varphi_1$ does not preserve $f$ (there exists $x$ such that $\varphi_1(f(x)) \neq f(\varphi_1(x))$)
5. $a_{i+1} > b_i$ (intervals strictly increasing)

Intuitive Understanding: Coding sequences provide a mechanism for "encoding" $\Delta^0_2$ sets when constructing computable copies:

• As set elements enter/leave, by inserting elements in the linear order, the intervals corresponding to encoded tuples change
• The maps on odd/even steps alternately preserve/do not preserve $f$, corresponding to 0/1 status of set elements
• Infinite coding sequences allow element values to change infinitely often ($\Delta^0_2$ property)

Intermediate Spectrum Construction

Example Description (Function in Theorem 3.7)

Block sequence: $L_1, L_1, L_2, L_1, L_3, L_2, L_4, L_1, L_5, L_2, L_6, L_3, L_7, L_1, L_8, \ldots$

where $L_k$ is a cycle of length $k$. Pattern:

• Odd positions: $L_1, L_2, L_3, L_4, \ldots$ (increasing enumeration)
• Even positions: $L_1, L_1, L_2, L_1, L_2, L_3, \ldots$ (each number infinitely often)

Key Properties:

• Each block appears infinitely often → spectrum contains non-c.e. degrees (Theorem 3.3)
• Any two blocks are adjacent at most once → any coding sequence has length $\leq 5$ (links break)
• No infinite coding sequence → spectrum does not contain all $\Delta^0_2$ degrees (Theorem 3.6)

Proof Sketch for Containing Non-c.e. Degrees (Theorem 3.3)

Sufficiency (infinitely many blocks embed into later blocks):

• For any tuple $c$, choose $a$ as a block of size $>1$ larger than $c$
• Prove that $a$ is a d-free tuple over $c$
• For quantifier-free formula $\varphi(c,a,b)$, construct $a' = a+1, b' = b+1$
  • $a'$ is no longer a block, so $f$ changes value at $a'$
  • For existential formula $\psi(c,a',b')$, find $a'', b''$ such that $f$ has the same values on $c,a'',b''$ as on $c,a,b$
  • Use block embedding property: $a''$ is the target block where $a$ embeds
• By Theorem 3.2 (from HT18), spectrum strictly contains c.e. degrees

Proof Sketch for Not Containing All $\Delta^0_2$ Degrees (Theorem 3.6B)

Necessity (no infinite coding sequence):

• Construct $\Delta^0_2$ set $C$ such that for all computable copies $L_e \cong (\omega,<)$: $\Phi_i^{f^{L_e}} \neq C \text{ or } \Psi_j^C \neq f^{L_e}$
• Requirement $R_{e,i,j}$ strategy:
  1. Choose unconstrained $x$, initially $C(x)=0$ (Phase 0)
  2. When computation $\Phi_i^{f^{L_e}}(x)=C(x)$ and $\Psi_j^C[0,\ldots,m_0] = f^{L_e}[0,\ldots,m_0]$ appear, change $C(x)$ (Phase 1)
  3. Alternately change $C(x)$ each time to break computations
• Key Argument: If a requirement enters arbitrarily many stages, an infinite (weak) coding sequence is constructed
  • Stage $s_n$ corresponds to interval $[a_n, b_n]$ and map $\pi_{s_n}: L_e \to (\omega,<)$
  • Define $\varphi_i = \pi_{i+1} \circ \pi_i^{-1}$
  • By computability properties, $\varphi_i$ alternately preserve/do not preserve $f$ on odd/even stages
• By Lemma 3.5, weak coding sequences convert to strong coding sequences, contradiction

Coding Tree Theory (Section 4)

Maximal Coding Tree

• Definition 4.8: Nodes are all finite weak coding sequences, extension relation is sequence extension
• Rank: $\text{maxrank}(f) = \text{rank}(T_{\max}(f))$
• Theorem 4.9: If $\alpha = \text{maxrank}(f)$, then on a cone there exists a non-$\alpha$-c.e. degree not in the spectrum
  • Proof: In diagonalization construction maintain rank function $r(x,s): \omega^2 \to \alpha+1$
  • Each change of $C(x)$ corresponds to extending coding sequence, rank strictly decreases
  • By tree well-foundedness, $C$ is an $\alpha$-c.e. set

Minimal Coding Tree

• Definition 4.11: Nodes are finite strong coding sequences, but rank definition is more complex
• Permitting Relation: $\sigma$ permits $\tau$ if:
  • Last intervals $[a_n,b_n]$ and $[a'_n,b'_n]$ satisfy $a_n < a'_n$
  • There exists map $\psi: [a_n,b_n] \to [a'_n,b'_n]$ preserving $f$ and commuting with $\varphi_{n-1}, \varphi'_{n-1}$
• Rank Definition: $\text{minrank}(\sigma) \geq \alpha$ if:
  • There exists infinite sequence $\sigma_0, \sigma_1, \ldots$ where each permits the next
  • For all $\beta < \alpha$ and all $i$, there exists $\tau_i$ extending $\sigma_i$ with $\text{minrank}(\tau_i) \geq \beta$
• Theorem 4.12: If $\alpha = \text{minrank}(f)$, then spectrum contains all $\beta$-c.e. degrees ($\beta < \alpha$)
  • Proof: Given $\beta$-c.e. set $X$ (rank function $r: \omega^2 \to \beta$), construct $L \cong (\omega,<)$ with $f^L \equiv_T X$
  • For each $e$ maintain coding sequence $CS_{e,s}$ satisfying $\text{minrank}(CS_{e,s}) \geq r(e,s)$
  • When $X(e)$ changes, extend coding sequence (rank decreases)
  • When $X(e)$ stable but adjustment needed, move laterally to permitted sequence of same rank

Experimental Results (Theorem Verification)

Main Results

1. Existence of Intermediate Spectrum (Theorem 3.7)

Function: $f$ with block sequence $L_1L_1L_2L_1L_3L_2L_4L_1\ldots$

Verification:

• Contains Non-c.e. Degrees: Each $L_k$ appears infinitely often, satisfying Theorem 3.3 conditions
• Does Not Contain All $\Delta^0_2$ Degrees: Any coding sequence has length $\leq 5$
  • Proof: Any coding sequence has weak link in $[a_1,b_1]$ or $[a_2,b_2]$ becoming weak in $[a_2,b_2]$ or $[a_3,b_3]$
  • Weak link in $[a_{i+2},b_{i+2}]$ or $[a_{i+3},b_{i+3}]$ must break
  • Broken link cannot continue extending (parity contradiction)

Conclusion: This is the first computable, natural, relativizable intermediate spectrum example

2. Diversity of Spectra (Theorem 4.17)

Construction: For even ordinal $\alpha \geq 6$, construct function $f$ based on tree $T$ of rank $\alpha$

Block Types: For $\sigma = \langle a_0,\ldots,a_n \rangle \in T$, define $B_\sigma = x_0 + L_{2\ell(\sigma|_0)+2} + \cdots + L_{2\ell(\sigma|_n)+2} + x_1 + x_2 + x_3$ where "sandwich elements" $x_0,x_1,x_2,x_3$ have function values depending on parity of $|\sigma|$

Block Sequence:

• Even positions: $L_1, L_3, L_5, \ldots$ (odd-length cycles)
• Odd positions: $B_{\sigma_1}, L_{j(1)}, B_{\sigma_2}, L_{j(2)}, \ldots$
  • $\sigma_1, \sigma_2, \ldots$ recursively enumerate $T$, each infinitely often
  • $j(i)$ enumerates odd numbers, each infinitely often, with $j(i) \leq 2i+1$

Verification:

• Minimum Rank $\geq \alpha$: $T$ embeds into minimal coding tree (via natural map $\sigma \mapsto [a_1,b_1],\ldots,[a_{|\sigma|},b_{|\sigma|}]$)
• Maximum Rank $\leq \alpha$:
  • Weak link sequences have length $\leq 5 < \alpha$
  • Other sequences correspond to paths in $T^*$ (tree of pairs of elements in $T$)
  • Prove by induction $\text{rank}^*(T^*) \leq \alpha$ (key: $\alpha$ is even)

Conclusion: There exist uncountably many distinct spectra (corresponding to different $\alpha$)

Concrete Example Analysis (Example 4.15)

For the function $f$ in Theorem 3.7:

Maximum Coding Tree Rank: $\text{maxrank}(f) \leq 6$

• Any length-5 coding sequence has weak link
• Weak link breaks within 2 steps

Minimum Coding Tree Rank: $\text{minrank}(f) = 3$

• Lower Bound: For $\ell < m < n$, sequence $[a_1,b_1]$ (type $L_\ell$) → $[a_2,b_2]$ (type $L_m$) → $[a_3,b_3]$ (combination of $L_\ell$ and $L_n$) shows rank $\geq 3$
• Upper Bound: Any sequence with weak link has rank 0 (permitted sequences have broken links)

Spectrum Conclusion:

• Contains all 2-c.e. degrees (by $\text{minrank}=3$)
• Does not contain all 6-c.e. degrees (by $\text{maxrank} \leq 6$)
• By special argument: does not contain all 3-c.e. degrees

Related Work

Historical Context

1. Early Work:
   • Downey et al. DKMY09: Unary relation spectra are either computable or all $\Delta^0_2$ degrees
   • Knoll Kno09: Research on $\omega$ and $\zeta$
2. Wright's Classification Theorem Wri18:
   • Spectra are either singleton sets or contain all c.e. degrees
   • Excludes intermediate cases between computable and c.e. degrees
   • Leaves open: do intermediate spectra between c.e. and $\Delta^0_2$ degrees exist?
3. BKW Breakthrough BKW22:
   • First construction of intermediate spectrum unary function
   • Limitations:
     • Non-canonical (depends on Gödel coding)
     • Not relativizable (degenerates to c.e. degrees on cone)
     • Depends on non-computability of counting function
4. On-a-Cone Framework:
   • Originates from Martin Conjecture Mon19
   • Montalbán Mon13: Studies computable structure theory on cones
   • Harrison-Trainor HT18: First systematic study of degree spectra on cones
   • Csima & Harrison-Trainor CHT17: Categoricity degrees on cones

Advantages of This Paper Over Related Work

Technical Contribution Comparison

• This Paper's Coding Sequence Theory vs BKW's Counting Function Method:
  • Coding sequences provide geometric/combinatorial intuition
  • Rank theory of coding trees precisely characterizes $\alpha$-c.e. degrees
  • Allows systematic construction (Theorem 4.17)

Conclusions and Discussion

Main Conclusions

1. Existence: Natural (on-a-cone) intermediate spectrum relations exist
2. Diversity: Uncountably many distinct intermediate spectra exist
3. Characterization Theorem: Existence of coding sequences completely characterizes whether spectrum is all $\Delta^0_2$ degrees
4. Fine Structure: Ranks of minimal/maximal coding trees provide upper/lower bounds on $\alpha$-c.e. degree inclusion

Limitations

1. Gap Between Minimum and Maximum Ranks (Example 4.15):
   • $\text{minrank}(f) = 3$ but $\text{maxrank}(f) = 6$
   • Spectrum actually does not contain all 3-c.e. degrees (requires special argument)
   • Gap arises from complex behavior of "permitting" relation, not just sequence length
2. Odd Ordinal Case (Question 4.18):
   • Theorem 4.17 only proves even $\alpha \geq 6$
   • Odd case rank computation more complex (induction step fails)
3. Lack of Complete Characterization (Question 4.21):
   • Minimum/maximum ranks only give bounds
   • Exact determination of whether spectrum contains all $\alpha$-c.e. degrees remains difficult
4. Incomparable Spectra (Conjecture 4.16):
   • Authors conjecture existence of incomparable spectra
   • Requires constructing functions with different "permitting behaviors"

Future Directions

1. Open Questions:
   • Question 4.19: Does containing non-c.e. degrees imply containing all 2-c.e. degrees?
   • Question 4.20: Do infinite descending chains exist?
   • Question 4.21: Precisely characterize conditions for $\alpha$-c.e. degree inclusion
2. Generalization Directions:
   • Extend to other structures (not just $(\omega,<)$)
   • Study higher-arity relations (non-unary functions)
   • Connect to other aspects of Martin Conjecture
3. Technical Improvements:
   • Simplify coding tree rank computation
   • Develop general theory for handling "permitting" relations
   • Construct systematic methods for functions with specific spectrum properties

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Completely resolves "on-a-cone" intermediate spectrum problem
   • Develops complete theoretical framework for coding sequences/trees
   • Proves uncountable diversity (Theorem 4.17)
2. Technical Innovation:
   • Coding Sequence Concept: Elegantly captures essence of $\Delta^0_2$ encoding
   • Minimal/Maximal Coding Tree Dichotomy: Distinguishes "single-element encoding" from "multi-element independent encoding"
   • Rank Theory: Precisely connects to $\alpha$-c.e. hierarchy
3. Naturality:
   • Examples have explicit description ($L_1L_1L_2L_1L_3L_2\ldots$)
   • All parameters computable ($\alpha_f, c_f$, etc.)
   • Fully relativizable (cone base is computable degree)
4. Systematicity:
   • If-and-only-if conditions (Theorems 3.3, 3.6)
   • Unified framework (applies to all block functions)
   • Generalizability (construction scheme in Theorem 4.17)

Weaknesses

1. Technical Complexity:
   • Coding tree rank definition quite technical (Definition 4.11)
   • Inductive definition of minimum rank unintuitive
   • Theorem 4.17 proof requires delicate rank computation
2. Incompleteness of Results:
   • Gap between minimum/maximum ranks unresolved
   • Only handles even ordinals $\alpha$
   • Complete classification of spectra still lacking
3. Limitation of Examples:
   • Only considers block functions (special unary functions)
   • Higher-arity relations not explored
   • Connections to other structures unclear
4. Presentation Issues:
   • Heavy notation ($\pi_s, \pi_{s+1}$ distinctions)
   • Some proofs lengthy (Theorem 4.17)
   • Lacks intuitive diagrams (though simple figures included)

Impact

1. Contribution to Field:
   • Resolves Important Open Problem: "On-a-cone" version posed by Harrison-Trainor in HT18
   • Methodological Contribution: Demonstrates effectiveness of "on-a-cone" framework in excluding pathological examples
   • Theoretical Tool: Coding sequence theory may apply to other $\Delta^0_2$-classification problems
2. Practical Value:
   • Primarily theoretical contribution, no direct applications
   • But understanding degree spectra fundamental to computable model theory and reverse mathematics
3. Reproducibility:
   • Construction completely explicit, verifiable
   • Proof details sufficient (though technically demanding)
   • No computational experiments required

Applicable Scenarios

1. Theoretical Research:
   • Computable structure theory
   • Degree theory
   • Properties of $\alpha$-c.e. sets
2. Potential Generalizations:
   • Other classifiable structures (Boolean algebras, trees, etc.)
   • Higher-order hyperarithmetic levels
   • Encoding problems in reverse mathematics
3. Educational Value:
   • Demonstrates formalization of "naturality" concept
   • Combines priority arguments with structural properties
   • Advanced example in degree spectrum theory

Key References

1. BKW22 Bazhenov, Kalociński, Wrocławski: First intermediate spectrum example
2. HT18 Harrison-Trainor: Systematic study of degree spectra on cones, poses problem solved in this paper
3. Wri18 Wright: Four-way classification theorem for spectra
4. DKMY09 Downey et al.: Degree spectra of unary relations
5. Mar75 Martin: Borel determinacy (foundation of Martin measure)
6. AK00 Ash & Knight: Standard reference for computable structure theory

Summary Assessment

This paper represents significant progress in computable structure theory, thoroughly resolving the "natural" intermediate spectrum problem for relations on $(\omega,<)$ through the elegant theory of coding sequences. Compared to prior work, this paper's examples are not merely existent but computable, explicit, and fully relativizable, truly embodying "naturality."

The greatest highlight is the development of coding sequence/coding tree theory, which not only solves the existence problem but provides systematic tools for construction and classification (Theorem 4.17 proves uncountable diversity). This theoretical framework may have profound impact on degree spectrum research for other structures.

Main challenges lie in the gap between minimum/maximum coding tree ranks and the technical complexity introduced by the "permitting" relation. The authors correctly identify that complete spectrum characterization requires understanding these complex combinatorial behaviors, not merely coding sequence length.

Overall, this is a technically profound and important paper that provides new tools and perspectives for computable structure theory.