Weihrauch degrees without roots

Article type: Research Article

Authors: Uftring, Patrick^{; *}

Affiliations: Institute of Mathematics, University of Würzburg, Emil-Fischer-Straße 40, 97074 Würzburg, Germany

Correspondence: [*] Corresponding author. patrick.uftring@uni-wuerzburg.de.

Abstract: 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 LPO and LLPO do not have roots.

Keywords: Weihrauch reducibility, compositional product, limited principle of omniscience

DOI: 10.3233/COM-230471

Journal: Computability, vol. Pre-press, no. Pre-press, pp. 1-14, 2024