Weihrauch Reductions for Paths Through Ill-Founded Trees

Definitions and mathematical statement

Write ${\mathbb{N}}^{<{\mathbb{N}}}=\bigcup_{n\in{\mathbb{N}}}{\mathbb{N}}^n$. A tree on ${\mathbb{N}}$ is a set $T\subseteq{\mathbb{N}}^{<{\mathbb{N}}}$ closed under initial segments. Its set of infinite paths is \[ [T]=\{p\in{\mathbb{N}}^{{\mathbb{N}}}: (\forall n\in{\mathbb{N}})\ p\mathbin{\upharpoonright}n\in T\}. \] Call $T$ ill-founded when $[T]\ne\varnothing$. Under the usual finite-sequence interpretation of the source's phrase "an ill-founded subtree of ${\mathbb{N}}^{{\mathbb{N}}}$", the underlying multivalued path problem is \[ \operatorname{dom}(\mathrm{CNN})=\{T\subseteq{\mathbb{N}}^{<{\mathbb{N}}}:T\text{ is a tree and }[T]\ne\varnothing\}, \qquad \mathrm{CNN}(T)=[T]. \] This explicitly interprets the source wording; the record does not specify how input trees are represented, so it does not yet determine a represented multivalued problem.

For multivalued problems $P,Q$ on fixed represented spaces, ordinary Weihrauch reducibility $P\leq_{\mathrm W}Q$ means that there are computable transformations $K,H$ on names such that, for every name $p$ of any input in $\operatorname{dom}(P)$, $K(p)$ names an input in $\operatorname{dom}(Q)$, and for every name $q$ of any valid $Q$-output on that input, $H(p,q)$ names a valid $P$-output on the original input. The same transformations must work for all inputs and all valid oracle outputs.

The supplied question asks, separately, whether \[ \mathrm{CNN}\leq_{\mathrm W}\Sigma^0_1\text{-}\mathrm{RT} \qquad\text{and whether}\qquad \mathrm{CNN}\leq_{\mathrm W}\mathrm{wFindHS}\text{-}\Pi^0_1. \] Here the target names are retained exactly in mathematical content from the record. Their input domains, output requirements, promises, and representations are not defined there. Consequently these are provisional reduction questions in the source's intended conventions; a fully specified mathematical formulation requires those definitions and the representation of $\mathrm{CNN}$. No choice of such missing conventions is asserted in this draft.

Short English statement

Given an ill-founded tree, can one uniformly obtain an infinite path using a single application of either named target problem, with computable processing before and after that application? The two reductions are separate questions. The supplied record leaves the target problems and input representations unspecified, so this statement requires clarification and human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004679$, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year $2021$ and names no individual proposer.
• Supplied source citation: Computability Theory (2022), Oberwolfach Reports, DOI 10.4171/owr/2021/21, pp. 1149--1190. https://doi.org/10.4171/owr/2021/21. The record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. Its title year and the report identifier are reproduced as supplied.
• Supplied literature source: Goh, Pauly and Valenti, "weakness of DS". https://arxiv.org/abs/2401.11807.
• Supplied literature source: Marcone and Valenti, "open and clopen Ramsey theorems". https://doi.org/10.1017/jsl.2021.10.
• Supplied literature source: Oberwolfach Report 21/2021. https://ems.press/content/serial-article-files/46899.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the record "partially solved" and reports that the 2024 primary paper proves that $\mathrm{KL}$ is not Weihrauch reducible to $\mathrm{DS}$ or $\mathrm{BS}$, while the queued $\mathrm{CNN}$ reductions and the broader $\Gamma$-presented hierarchy questions are not fully characterized. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment; the record itself requests independent verification of time-sensitive status and cited claims. It does not identify either displayed $\mathrm{CNN}$ reduction as settled.
• The supplied statement status is corrected_verified. Its accompanying verification note says only formula delimiters, notation, grammar, and typography were repaired, with mathematical content and scope preserved. This is a supplied editorial qualification, not independent mathematical verification.