pith. sign in

arxiv: 2606.00845 · v1 · pith:SMUW4GNJnew · submitted 2026-05-30 · 🧮 math.LO

Conjunctive reducibilities and completeness

classification 🧮 math.LO
keywords completecompletenesssetsreducibilitiesconjunctiveexistprovereducibility
0
0 comments X
read the original abstract

In this article we study the notion of completeness for conjunctive reducibilities. We investigate the relationship between $c$-completeness and $r$-completeness of computably enumerable (c.e.) sets with respect to various strong reducibilities $\le_r$. By using simplicity properties of sets, we prove that there exist c.e. sets that are simultaneously $Q$-complete and $bd$-complete, yet fail to be $c$-complete. Similarly, there exist c.e. sets that are simultaneously $Q$-complete and $bwtt$-complete (respectively, $btt$-complete) but not $c$-complete. Furthermore, we study two restrictions of $c$-reducibility, namely $c_1$- and $c_{1,N}$-reducibility, and show that they are distinct on the c.e. sets. Nevertheless, we prove that the notions of completeness for $c$, $c_1$, and $c_{1,N}$ coincide.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.