On elementary theories of ordinal notation systems based on reflection principles

DOI10.1134/S0081543815040124MaRDI QIDQ281010zbMATH OpenOpenAlexFDO

Authors Fedor N. Pakhomov

Publication date 10 May 2016

Published in Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.3002

zbMATH Keywords

decidabilityordinal notation systempolymodal provability logicreflection schemes

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30) Recursive ordinals and ordinal notations (03F15) Relative consistency and interpretations (03F25) Provability logics and related algebras (e.g., diagonalizable algebras) (03F45)

Abstract: We consider the constructive ordinal notation system for the ordinal $epsilo{n}_0$ that were introduced by L.D. Beklemishev. There are fragments of this system that are ordinal notation systems for the smaller ordinals $omeg{a}_n$ (towers of $omega$-exponentiations of the height $n$). This systems are based on Japaridze's provability logic $mathbfGLP$. They are closely related with the technique of ordinal analysis of $mathbfPA$ and fragments of $mathbfPA$ 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 $geomeg{a}_4$, have undecidable elementary theories. We also prove that the fragments of the full system, for ordinals $leomeg{a}_3$, have decidable elementary theories. We obtain some results about decidability of elementary theory, for the ordinal notation systems with weaker signatures.

Recommendations

• A comparison of well-known ordinal notation systems for \(\varepsilon _{0}\)
• Provability algebras and proof-theoretic ordinals. I
• scientific article; zbMATH DE number 1390279
• \(\Pi_1^0\)-ordinal analysis beyond first-order arithmetic
• A new system of proof-theoretic ordinal functions

Cites work

• scientific article; zbMATH DE number 3720895 (Why is no real title available?)
• scientific article; zbMATH DE number 1144041 (Why is no real title available?)
• scientific article; zbMATH DE number 1390277 (Why is no real title available?)
• scientific article; zbMATH DE number 5046774 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3316936 (Why is no real title available?)
• A comparison of well-known ordinal notation systems for \(\varepsilon _{0}\)
• All maps of type 2^{∞} are boundary maps
• Covering of ordinals
• Decision methods in the theory of ordinals
• Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen
• On notation for ordinal numbers
• On strong provability predicates and the associated modal logics
• Proof theory. 2nd ed
• Proof theory. The first step into impredicativity
• Proof-theoretic analysis by iterated reflection
• Provability algebras and proof-theoretic ordinals. I
• Reflection principles and provability algebras in formal arithmetic
• The constructive second number class
• The inverse limit space and the dynamics of a graph map
• Undecidability of the elementary theory of the semilattice of GLP-words
• Wie die Beweistheorie zu ihren Ordinalzahlen kam und kommt
• Worms, gaps, and hydras

Cited in

(6)

• \(\Pi_1^0\)-ordinal analysis beyond first-order arithmetic
• scientific article; zbMATH DE number 1420856 (Why is no real title available?)
• Reflection calculus and conservativity spectra
• Franco Montagna's work on provability logic and many-valued logic
• How to compare Buchholz-style ordinal notation systems with Gordeev-style notation systems
• A simplified ordinal analysis of first-order reflection

This page was built for publication: On elementary theories of ordinal notation systems based on reflection principles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281010)