On elementary theories of ordinal notation systems based on reflection principles

DOI10.1134/S0081543815040124zbMATH Open1373.03124arXiv1312.3002OpenAlexW2964204347MaRDI QIDQ281010FDOQ281010

Authors: Fedor N. Pakhomov 

Publication date: 10 May 2016

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• \(\Pi_1^0\)-ordinal analysis beyond first-order arithmetic
• 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)