Geodesic
Undecidability of the elementary theory of the semilattice of GLP-words
Sbornik. Mathematics, Tome 203 (2012) no. 8, pp. 1211-1229
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The Lindenbaum algebra of Peano PA can be enriched by the $n$-consistency operators which assign, to a given formula, the statement that the formula is compatible with the theory PA extended by the set of all true $\Pi_n$-sentences. In the Lindenbaum algebra of PA, a lower semilattice is generated from $\mathbf{1}$ by the $n$-consistency operators. We prove the undecidability of the elementary theory of this semilattice and the decidability of the elementary theory of the subsemilattice (of this semilattice) generated by the $0$-consistency and $1$-consistency operators only. Bibliography: 16 titles.
Keywords: provability logic, elementary theories, undecidability. 
@article{SM_2012_203_8_a6,
     author = {F. N. Pakhomov},
     title = {Undecidability of the elementary theory of the semilattice of {GLP-words}},
     journal = {Sbornik. Mathematics},
     pages = {1211--1229},
     year = {2012},
     volume = {203},
     number = {8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2012_203_8_a6/}
}
TY  - JOUR
AU  - F. N. Pakhomov
TI  - Undecidability of the elementary theory of the semilattice of GLP-words
JO  - Sbornik. Mathematics
PY  - 2012
SP  - 1211
EP  - 1229
VL  - 203
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/SM_2012_203_8_a6/
LA  - en
ID  - SM_2012_203_8_a6
ER  - 
%0 Journal Article
%A F. N. Pakhomov
%T Undecidability of the elementary theory of the semilattice of GLP-words
%J Sbornik. Mathematics
%D 2012
%P 1211-1229
%V 203
%N 8
%U http://geodesic.mathdoc.fr/item/SM_2012_203_8_a6/
%G en
%F SM_2012_203_8_a6
F. N. Pakhomov. Undecidability of the elementary theory of the semilattice of GLP-words. Sbornik. Mathematics, Tome 203 (2012) no. 8, pp. 1211-1229. http://geodesic.mathdoc.fr/item/SM_2012_203_8_a6/

[1] A. Tarski, “Arithmetical classes and types of Boolean algebras”, Bull. Amer. Math. Soc., 55 (1949), 63–64

[2] A. Grzegorezyk, “Undecidability of some topological theories”, Fund. Math., 38 (1951), 137–152 | MR | Zbl

[3] V. V. Rybakov, “Elementary theories of free topo-Boolean and pseudo-Boolean algebras”, Math. Notes, 37:6 (1985), 435–438 | DOI | MR | Zbl

[4] 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

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

[6] L. D. Beklemishev, “Reflection principles and provability algebras in formal arithmetic”, Russian Math. Surveys, 60:2 (2005), 197–268 | DOI | MR | Zbl

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

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

[9] G. Lee, “A comparison of well-known ordinal notation systems for $\varepsilon_0$”, Ann. Pure Appl. Logic, 147:1–2 (2007), 48–70 | DOI | MR | Zbl

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

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

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

[13] 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

[14] J. R. Büchi, “Weak second-order arithmetic and finite automata”, Z. Math. Logik Grundlagen Math., 6 (1960), 66–92 | DOI | MR | Zbl

[15] C. C. Elgot, M. O. Rabin, “Decidability and undecidability of extensions of second (first) order theory of (generalized) successor”, J. Symbolic Logic, 31:2 (1966), 169–181 | DOI | Zbl

[16] J. R. Büchi, “Decision methods in the theory of ordinals”, Bull. Amer. Math. Soc., 71:5 (1965), 767–770 | DOI | MR | Zbl