Many-one reducibility with realizability
<|reference_start|>Many-one reducibility with realizability: In this article, we propose a new classification of $\Sigma^0_2$ formulas under the realizability interpretation of many-one reducibility (i.e., Levin reducibility). For example, ${\sf Fin}$, the decision of being eventually zero for sequences, is many-one/Levin complete among $\Sigma^0_2$ formulas of the form $\exists n\forall m\geq n.\varphi(m,x)$, where $\varphi$ is decidable. The decision of boundedness for sequences ${\sf BddSeq}$ and for width of posets ${\sf FinWidth}$ are many-one/Levin complete among $\Sigma^0_2$ formulas of the form $\exists n\forall m\geq n\forall k.\varphi(m,k,x)$, where $\varphi$ is decidable. However, unlike the classical many-one reducibility, none of the above is $\Sigma^0_2$-complete. The decision of non-density of linear order ${\sf NonDense}$ is truly $\Sigma^0_2$-complete.<|reference_end|>
@article{kihara2024many-one,
    title={Many-one reducibility with realizability},
    author={Takayuki Kihara},
    journal={arXiv preprint arXiv:2403.16027},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.16027},
    primaryClass={math.LO cs.LO}
}