Geodesic
Linear $\mathrm{GLP}$-algebras and their elementary theories
Izvestiya. Mathematics , Tome 80 (2016) no. 6, pp. 1159-1199.

Voir la notice de l'article provenant de la source Math-Net.Ru

The polymodal provability logic $\mathrm{GLP}$ was introduced by Japaridze in 1986. It is the provability logic of certain chains of provability predicates of increasing strength. Every polymodal logic corresponds to a variety of polymodal algebras. Beklemishev and Visser asked whether the elementary theory of the free $\mathrm{GLP}$-algebra generated by the constants $\mathbf{0}$, $\mathbf{1}$ is decidable [1]. For every positive integer $n$ we solve the corresponding question for the logics $\mathrm{GLP}_n$ that are the fragments of $\mathrm{GLP}$ with $n$ modalities. We prove that the elementary theory of the free $\mathrm{GLP}_n$-algebra generated by the constants $\mathbf{0}$, $\mathbf{1}$ is decidable for all $n$. We introduce the notion of a linear $\mathrm{GLP}_n$-algebra and prove that all free $\mathrm{GLP}_n$-algebras generated by the constants $\mathbf{0}$, $\mathbf{1}$ are linear. We also consider the more general case of the logics $\mathrm{GLP}_\alpha$ whose modalities are indexed by the elements of a linearly ordered set $\alpha$: we define the notion of a linear algebra and prove the latter result in this case.
Keywords: provability logics, free algebras, elementary theories, Japaridze logic.
Mots-clés : modal algebras 
@article{IM2_2016_80_6_a8,
     author = {F. N. Pakhomov},
     title = {Linear $\mathrm{GLP}$-algebras and their elementary theories},
     journal = {Izvestiya. Mathematics },
     pages = {1159--1199},
     publisher = {mathdoc},
     volume = {80},
     number = {6},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2016_80_6_a8/}
}
TY  - JOUR
AU  - F. N. Pakhomov
TI  - Linear $\mathrm{GLP}$-algebras and their elementary theories
JO  - Izvestiya. Mathematics 
PY  - 2016
SP  - 1159
EP  - 1199
VL  - 80
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2016_80_6_a8/
LA  - en
ID  - IM2_2016_80_6_a8
ER  - 
%0 Journal Article
%A F. N. Pakhomov
%T Linear $\mathrm{GLP}$-algebras and their elementary theories
%J Izvestiya. Mathematics 
%D 2016
%P 1159-1199
%V 80
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2016_80_6_a8/
%G en
%F IM2_2016_80_6_a8
F. N. Pakhomov. Linear $\mathrm{GLP}$-algebras and their elementary theories. Izvestiya. Mathematics , Tome 80 (2016) no. 6, pp. 1159-1199. http://geodesic.mathdoc.fr/item/IM2_2016_80_6_a8/

[1] L. Beklemishev, A. Visser, “Problems in the logic of provability”, Mathematical problems from applied logic. I, Int. Math. Ser. (N. Y.), 4, Springer, New York, 2006, 77–136 | DOI | MR | Zbl

[2] R. M. Solovay, “Provability interpretations of modal logic”, Israel J. Math., 25:3-4 (1976), 287–304 | DOI | MR | Zbl

[3] G. K. Dzhaparidze, Modalno-logicheskie sredstva issledovaniya dokazuemosti, Diss. $\dots$ kand. filos. nauk, MGU, M., 1986, 177 pp.

[4] L. D. Beklemishev, “A simplified proof of arithmetical completeness theorem for provability logic $\mathbf{GLP}$”, Proc. Steklov Inst. Math., 274 (2011), 25–33 | DOI | MR | Zbl

[5] L. D. Beklemishev, “Provability algebras and proof-theoretic ordinals. I”, Ann. Pure Appl. Logic, 128:1-3 (2004), 103–123 | DOI | MR | Zbl

[6] K. N. Ignatiev, “On strong provability predicates and the associated modal logics”, J. Symbolic Logic, 58:1 (1993), 249–290 | DOI | MR | Zbl

[7] L. D. Beklemishev, J. J. Joosten, M. Vervoort, “A finitary treatment of the closed fragment of Japaridze's provability logic”, J. Logic Comput., 15:4 (2005), 447–463 | DOI | MR | Zbl

[8] A. Tarski, “Arithmetical classes and types of mathematical systems”, Bull. Amer. Math. Soc., 55 (1949), 63

[9] F. Montagna, “The undecidability of the first-order theory of diagonalizable algebras”, Studia Logica, 39:4 (1980), 355–359 | DOI | MR | Zbl

[10] C. Smoryński, “The finite inseparability of the first-order theory of diagonalisable algebras”, Studia Logica, 41:4 (1982), 347–349 | DOI | MR | Zbl

[11] S. N. Artemov, L. D. Beklemishev, “On propositional quantifiers in provability logic”, Notre Dame J. Formal Logic, 34:3 (1993), 401–419 | DOI | MR | Zbl

[12] V. Yu. Shavrukov, “Undecidability in diagonalizable algebras”, J. Symbolic Logic, 62:1 (1997), 79–116 | DOI | MR | Zbl

[13] F. N. Pakhomov, “Undecidability of the elementary theory of the semilattice of GLP-words”, Sb. Math., 203:8 (2012), 1211–1229 | DOI | DOI | MR | Zbl

[14] F. N. Pakhomov, “On elementary theories of ordinal notation systems based on reflection principles”, Proc. Steklov Inst. Math., 289:1 (2015), 194–212 | DOI | DOI | Zbl

[15] G. K. Dzhaparidze, “Polimodalnaya logika dokazuemosti”, Intensionalnye logiki i logicheskaya struktura teorii (Telavi, 1985), Metsniereba, Tbilisi, 1988, 16–48 | MR | Zbl

[16] L. D. Beklemishev, “Kripke semantics for provability logic GLP”, Ann. Pure Appl. Logic, 161:6 (2010), 756–774 | DOI | MR | Zbl

[17] L. D. Beklemishev, “Veblen hierarchy in the context of provability algebras”, Logic, methodology and philosophy of science (Oviedo, Spain, 2003), King's College Publ., London, 2005, 65–78 | Zbl

[18] G. Birkhoff, “On the structure of abstract algebras”, Proc. Cambridge Philos. Soc., 31:4 (1935), 433–454 | DOI | Zbl

[19] S. Burris, H. P. Sankappanavar, A course in universal algebra, Grad. Texts in Math., 78, Springer-Verlag, New York–Berlin, 1981, xvi+276 pp. | MR | Zbl

[20] F. W. Lawvere, Functorial semantics of algebraic theories, Ph.D. thesis, Columbia Univ., 1963, 121 pp.

[21] L. D. Beklemishev, D. Fernández-Duque, J. J. Joosten, “On provability logics with linearly ordered modalities”, Studia Logica, 102:3 (2014), 541–566 | DOI | MR | Zbl