Abstract
We show that, in general, there is no degree corresponding to the composition of two problems in the computable reducibility lattice. We show the same in the strong computable reducibility setting.
Get full access to this article
View all access options for this article.
References
1.
Fiori-Carones
M
Shafer
P
Soldà
G
. An inside/outside Ramsey theorem and recursion theory . Trans Am Math Soc 2021 ; 375 : 1977 –2024 .
2.
Dzhafarov
D
Mummert
C
. Reverse mathematics . Cham : Springer International Publishing , 2022 .
3.
Hirschfeldt
D
Jockusch
C
. On notions of computability-theoretic reduction between
principles . J Math Logic 2016 ; 16 : 1650002 .
4.
Goh
JL
. Compositions of multivalued functions . Computability 2020 ; 9 : 231 –247 .
5.
Brattka
V
Gherardi
G
Marcone
A
. The Bolzano–Weierstrass theorem is the jump of weak König’s lemma . Ann Pure Appl Logic 2012 ; 163 : 623 –655 .
6.
Brattka
V
Pauly
A
. On the algebraic structure of Weihrauch degrees . Log Methods Comput Sci 2018 ; 14 : 1 –36 .
7.
Dzhafarov
DD
Hirschfeldt
DR
Reitzes
S
. Reduction games, provability and compactness . J Math Logic 2022 ; 22 : 2250009 .