2011/06/05 by Antonio Montalbán, Antonio Montalban, Montalban, Antonio
Computer Science · Mathematics · #03D45 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03D45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1106.0908
arxiv created 2011/06/05 · openalex publication_date 2011/06/05 · arxiv updated 2011/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Assuming that 0^# exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure \mathcal A such that Sp(\mathcal A) = \\bf x':\bf x∈ Sp (\mathcal A)\, where Sp (\mathcal A) is the set of Turing degrees which compute a copy of \mathcal A. It turns out that, more interesting than the result itself, is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full nth-order arithmetic for all n, cannot prove the existence of such a structure.