On Elementary Theories of Ordinal Notation Systems based on Reflection\n Principles

2013/12/10 by Fedor Pakhomov, Pakhomov, Fedor
Computer Science · #03B25 #FOS: Mathematics #Logic (math.LO) #Mathematics, Computing, and Information Processing

paper · pdf · doi:10.48550/arxiv.1312.3002

openalex publication_date 2013/12/10 · openalex created_date 2022/10/07 · openalex updated_date 2026/07/28

Abstract

We consider the constructive ordinal notation system for the ordinal\n\ε₀ that were introduced by L.D. Beklemishev. There are fragments of\nthis system that are ordinal notation systems for the smaller ordinals\n\ω_n (towers of \ω-exponentiations of the height n). This\nsystems are based on Japaridze's provability logic \GLP. They are\nclosely related with the technique of ordinal analysis of \PA and\nfragments of \PA based on iterated reflection principles. We consider\nthis notation system and it's fragments as structures with the signatures\nselected in a natural way. We prove that the full notation system and it's\nfragments, for ordinals \≥\ω₄, have undecidable elementary theories.\nWe also prove that the fragments of the full system, for ordinals\n\≤\ω₃, have decidable elementary theories. We obtain some results\nabout decidability of elementary theory, for the ordinal notation systems with\nweaker signatures.\n

Related

• Ordinal Notation
• Deducibility and Independence in Beklemishev's Autonomous Provability Calculus
• Proof theory for theories of ordinals III: Π_N-reflection
• Worms and Spiders: Reflection calculi and ordinal notation systems
• Polymorphic Ordinal Notations