Paper detail

On Elementary Theories of Ordinal Notation Systems based on Reflection Principles

We consider the constructive ordinal notation system for the ordinal ${ε_0}$ that were introduced by L.D. Beklemishev. There are fragments of this system that are ordinal notation systems for the smaller ordinals ${ω_n}$ (towers of $ω$-exponentiations of the height $n$). This systems are based on Japaridze's provability logic $\mathbf{GLP}$. They are closely related with the technique of ordinal analysis of $\mathbf{PA}$ and fragments of $\mathbf{PA}$ based on iterated reflection principles. We consider this notation system and it's fragments as structures with the signatures selected in a natural way. We prove that the full notation system and it's fragments, for ordinals ${\geω_4}$, have undecidable elementary theories. We also prove that the fragments of the full system, for ordinals ${\leω_3}$, have decidable elementary theories. We obtain some results about decidability of elementary theory, for the ordinal notation systems with weaker signatures.