The arithmetical hierarchy: A realizability-theoretic perspective
Abstract
In this paper, we investigate the arithmetical hierarchy from the perspective of realizability theory. An experimental observation in classical computability theory is that the notion of degrees of unsolvability for natural arithmetical decision problems only plays a role in counting the number of quantifiers, jumps or mind-changes. In contrast, we reveal that when the realizability interpretation is combined with many-one reducibility, it becomes possible to classify natural arithmetical problems in a very nontrivial way.
Fields of Study & Subjects
History and Theory of Mathematics
Advanced Optimization Algorithms Research
Publication details
- Journal / source
- Journal of Mathematical Logic
- Publisher
- World Scientific Pub Co Pte Ltd
- Publication date
- 23 August 2026
- Language
- EN