Searching problems above arithmetical transfinite recursion

Abstract

We investigate some Weihrauch problems between ${\mathsf{ATR}}_2$ and ${\mathsf{C}}_{{\omega }^{\omega }}$ . We show that the fixed point theorem for monotone operators on the Cantor space (a weaker version of the Knaster-Tarski theorem) is not Weihrauch reducible to ${\mathsf{ATR}}_2$. Furthermore, we introduce the $\omega$-model reflection ${\mathsf{ATR}}_2^{\mathrm{rfn}}$ of $\mathsf{ATR}$ and show that it is an upper bound for problems provable from the axiomatic system ${\mathrm{ATR}}_0$ which are of the form $\forall X(\theta (X)\to \exists Y\eta (X,Y))$ with arithmetical formulas $\theta ,\eta$. We also show that Weihrauch degrees of relativized least fixed point theorem for monotone operators on the Cantor space forms a linear hierarchy between ${\mathsf{ATR}}^{\mathrm{rfn}}$ and ${\mathsf{C}}_{{\omega }^{\omega }}$.