Searching problems above arithmetical transfinite recursion

arXiv2305.07321MaRDI QIDQ6510083FDOQ6510083

Authors: Yudai Suzuki, Keita Yokoyama 

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^{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( heta(X) o exists Y eta(X, Y )) with arithmetical formulas heta, 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}^{rfn} and mathsf{C}_{omega^omega} .

This page was built for publication: Searching problems above arithmetical transfinite recursion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510083)