A finitary treatment of the closed fragment of Japaridze's provability logic
Lev D. Beklemishev, Joost J. Joosten, Marco Vervoort
Abstract:
We study a propositional polymodal provability logic GLP introduced by
G. Japaridze. The previous treatments of this logic, due to Japaridze
and Ignatiev, heavily relied on some non-finitary principles such as
transfinite induction up to \epsilon_0 or reflection principles. In
fact, the closed fragment of GLP gives rise to a natural system of
ordinal notation for \epsilon_0 that was used for a proof-theoretic
analysis of Peano arithmetic and for constructing simple combinatorial
independent statements. In this paper, we study Ignatiev's universal
model for the closed fragment of this logic. Using bisimulation
techniques, we show that several basic results on the closed fragment
of GLP, including the normal form theorem, can be proved by purely
finitary means formalizable in elementary arithmetic. As a corollary,
the system of ordinal notation for \epsilon_0 based on the closed
fragment of GLP is shown to be provably isomorphic to the standard
system of ordinal notation up to \epsilon_0. We also settle negatively
some conjectures by Ignatiev.