We answer the following question by Arno Pauly: “Is there a square root operator on the Weihrauch degrees?”. In fact, we show that there are uncountably many pairwise incomparable Weihrauch degrees without any roots. We also prove that the omniscience principles of and do not have roots.
BishopE.BridgesD., Constructive Analysis, Springer-Verlag, Berlin, Heidelberg, 1985. ISBN 978-3-642-61667-9. doi:10.1007/978-3-642-61667-9.
2.
BrattkaV., Recursive and computable operations over topological structures, PhD thesis, Department of Computer Science, University of Hagen, Hagen, Germany, 1998.
3.
BrattkaV.GherardiG., Weihrauch degrees, omniscience principles and weak computability, The Journal of Symbolic Logic76(1) (2011), 143–176. doi:10.2178/jsl/1294170993.
4.
BrattkaV.GherardiG.MarconeA., The Bolzano–Weierstrass theorem is the jump of weak Kőnig’s lemma, Annals of Pure and Applied Logic163(6) (2012), 623–655, Computability in Europe 2010. doi:10.1016/j.apal.2011.10.006.
5.
BrattkaV.GherardiG.PaulyA., Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis, BrattkaV.HertlingP., eds, Springer International Publishing, Cham, 2021, pp. 367–417. ISBN 978-3-030-59234-9. doi:10.1007/978-3-030-59234-9_11.
6.
BrattkaV.PaulyA., On the algebraic structure of Weihrauch degrees, Logical Methods in Computer Science14 (2018), 1–36. doi:10.23638/LMCS-14(4:4)2018.
7.
BridgesD.RichmanF., Varieties of Constructive Mathematics, London Mathematical Society Lecture Note Series, Cambridge University Press, 1987. doi:10.1017/CBO9780511565663.
8.
HiguchiK.PaulyA., The degree structure of Weihrauch reducibility, Log. Methods Comput. Sci.9(2) (2013), 1–17. doi:10.2168/LMCS-9(2:2)2013.
9.
KleeneS.C.PostE.L., The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2)59 (1954), 379–407. doi:10.2307/1969708.
10.
KreitzC.WeihrauchK., Theory of representations, Theoretical Computer Science38 (1985), 35–53. doi:10.1016/0304-3975(85)90208-7.
11.
NeumannE.PaulyA., A topological view on algebraic computation models, J. Complexity44 (2018), 1–22. doi:10.1016/j.jco.2017.08.003.
12.
PaulyA., On the (semi)lattices induced by continuous reducibilities, Mathematical Logic Quarterly56(5) (2010), 488–502. doi:10.1002/malq.200910104.
13.
PaulyA., An update on Weihrauch complexity, and some open questions, 2020, arXiv:2008.11168. doi:10.48550/arXiv.2008.11168.
14.
ShoenfieldJ.R., An uncountable set of incomparable degrees, Proc. Amer. Math. Soc.11 (1960), 61–62. doi:10.2307/2032716.
15.
SoldàG.ValentiM., Algebraic properties of the first-order part of a problem, Ann. Pure Appl. Logic174(7) (2023), 1–41. Paper no. 103270. doi:10.1016/j.apal.2023.103270.
16.
WeihrauchK., The TTE-Interpretation of Three Hierarchies of Omniscience Principles, Informatik Berichte, Vol. 130, FernUniversität Hagen, Hagen, 1992.
17.
WestrickL., A note on the diamond operator, Computability10(2) (2021), 107–110. doi:10.3233/COM-200295.
