التفاصيل البيبلوغرافية
| العنوان: |
Searching problems above arithmetical transfinite recursion |
| المؤلفون: |
Suzuki, Yudai, Yokoyama, Keita |
| سنة النشر: |
2023 |
| المجموعة: |
Mathematics |
| مصطلحات موضوعية: |
Mathematics - Logic |
| الوصف: |
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} $. |
| نوع الوثيقة: |
Working Paper |
| URL الوصول: |
http://arxiv.org/abs/2305.07321 |
| رقم الانضمام: |
edsarx.2305.07321 |
| قاعدة البيانات: |
arXiv |