Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2606.00845 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913176244715520 |
|---|---|
| author | Chitaia, Irakli Ng, Keng Meng Omanadze, Roland Sorbi, Andrea |
| author_facet | Chitaia, Irakli Ng, Keng Meng Omanadze, Roland Sorbi, Andrea |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00845 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Conjunctive reducibilities and completeness Chitaia, Irakli Ng, Keng Meng Omanadze, Roland Sorbi, Andrea Logic 03D25, 03D30 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. |
| title | Conjunctive reducibilities and completeness |
| topic | Logic 03D25, 03D30 |
| url | https://arxiv.org/abs/2606.00845 |