Turing Degree of Finite-Set Cardinality Indices

Definitions and mathematical statement

The supplied record asks about a family denoted by $K_e$, but does not define this family, its indexing convention, or the range of $e$. Its title refers to finite sets, and a supplied reference is labelled "K-trivial counting theorem"; neither supplies the missing definition. Consequently, the intended counting function cannot be uniquely specified from this record.

The following formalization is conditional on the missing context specifying a family $(K_e)_{e\in{\mathbb{N}}}$ of finite sets. Define its cardinality function by \[ f:{\mathbb{N}}\longrightarrow{\mathbb{N}},\qquad f(e)=|K_e|. \] Fix a computable pairing function and represent an oracle for $f$ by its graph \[ G_f=\{\langle e,n\rangle:e,n\in{\mathbb{N}}\text{ and }f(e)=n\}. \] For sets $A,B\subseteq{\mathbb{N}}$, write $A\leq_T B$ when an oracle Turing machine with oracle $B$ decides membership in $A$. For a fixed standard effective enumeration $(\Phi_i)_{i\in{\mathbb{N}}}$ of oracle Turing machines, define \[ \varnothing'=\{i\in{\mathbb{N}}:\Phi_i^{\varnothing}(i)\text{ halts}\},\qquad \varnothing''=\{i\in{\mathbb{N}}:\Phi_i^{\varnothing'}(i)\text{ halts}\}. \] The source question, with "compute" interpreted as Turing computability, is:

For the intended family $(K_e)$, does $\varnothing'\leq_T G_f$ hold? Does the stronger assertion $\varnothing''\leq_T G_f$ hold?

These are questions about the particular source-defined family, not assertions quantified over all families of finite sets. The conditional domain and finiteness assumptions above require confirmation from the missing source context.

The supplied dated curation labels the problem partially solved and reports that the counting function is "Delta-three and not Delta-two", while the stronger jump-computation questions remain unresolved by the literature located during that curation. These are supplied assessments, not independently verified mathematical or current-status claims.

Short English statement

The question asks whether knowing the exact sizes of the intended sets $K_e$ lets one decide the halting problem, or even its second jump. The supplied record does not define $K_e$, so the displayed formulation is conditional and requires the original notation and indexing context before it becomes a fully specified problem.

Sources

• Local UnsolvedMath registry: supplied record with permanent ID $30001986$, source problem code catalogue entry, title "Turing Degree of Finite-Set Cardinality Indices". The record gives proposed year 2012 and does not identify a proposer.
• Supplied report citation: Computability Theory (2012), Oberwolfach Reports, pp. 397--455, DOI 10.4171/owr/2012/08. Source URL and literature-source label "original Oberwolfach report": https://doi.org/10.4171/owr/2012/08. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature-source label "K-trivial counting theorem": https://doi.org/10.1016/j.tcs.2011.09.020. No authors, full title, theorem number, or theorem text are supplied.
• Literature assessment checked on 2026-08-21: the supplied curation reports a partially solved status, a Delta-three but not Delta-two counting function, and no resolution of the stronger jump-computation questions in the located literature. This is supplied dated curation derived from the supplied Oberwolfach curation, not independently verified; its status and cited claims require independent checking.
• The supplied statement-status label is corrected_verified. Its accompanying verification note reports comparison with the official Oberwolfach report and normalization of notation, context, and question form without changing the source-level claim. That verification is reported by the record and has not been independently performed here.