OpenFrontiers
← Back to the index
OP-11822Status unassessedLogic and foundations

Strong jump traceability versus LR reducibility — Problem 2.2

Strong jump traceability versus LR reducibility — Problem 2.2. Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.

Editorial MSC2020 mapping of Strong jump traceability versus LR reducibility — Problem 2.2. https://arxiv.org/html/2608.26628v2#S2.Thmproblem2 Not an author-supplied code.

Licensed source statementAs of 2608.26628v2; current status unassessedSource & evidence ↓

Problem statement

Problem 2.2.

Does ≤SJT\leq_{SJT} imply ≤LR\leq_{LR}?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Background

Computability Theory

Assume throughout that A,B⊂NA,B\subset\mathbb{N}. One writes

A≤SJTBA\leq_{SJT}B

if for every order function hh there exists a uniformly BB-c.e. trace (Tn)(T_{n}) satisfying that

∣Tn∣≤h(n)|T_{n}|\leq h(n)

and

JA(n)↓⟹JA(n)∈Tn.J^{A}(n)\downarrow\Longrightarrow J^{A}(n)\in T_{n}.

Also recall that

A≤LRB  ⟺  MLRB⊆MLRA.A\leq_{LR}B\iff{\rm MLR}^{B}\subseteq{\rm MLR}^{A}.

We note that A≤SJT∅A\leq_{SJT}\emptyset implies A≤LR∅A\leq_{LR}\emptyset, namely, every strongly jump traceable set is KK-trivial, equivalently, low for ML-random. For background and references, see [1]. The authors there give several characterisations of ≤SJT\leq_{SJT} on the KK-trivials; for instance, for A,BA,B KK-trivial,

A≤SJTB  ⟺  ∀ Y ω-c.a. and Y∈MLR(A≤TB⊕Y).A\leq_{SJT}B\iff\forall\,Y\,\omega\text{-c.a. and }Y\in{\rm MLR}\Bigl(A\leq_{T}B\oplus Y\Bigr).

Let Rec denote the class of recursive sets.

Progress & source assessment

Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.

References
  1. [1]Barmpalias, George; Gao, Su; He, Jialiang; Kihara, Takayuki; Nies, Andre; Slaman, Theodore; Tran, Chieu-Minh; Turetsky, Daniel; Welch, Philip; Yu, Liang; Zhang, Hang. Tianyuan Workshop — Open Problems in Mathematical Logic (2026).; Strong jump traceability versus LR reducibility — Problem 2.2 linkhttp://creativecommons.org/licenses/by/4.0/; attributed adaptation; HTML converted to Markdown with original mathematical notation and source links.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.