Стройный порядок на строго позитивных формулах

Автор: Святловский М.В.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 3 (55) т.14, 2022 года.

Бесплатный доступ

Рассматривается фрагмент языка модальной логики, состоящий из формул, построенных из конечного набора переменных и константы ⊤ с помощью связок ∧ и ✸. Дляестественного порядка следования в K4 на этом фрагменте доказано, что он является стройным предпорядком (well-quasi order), и найдены оценки его ординального типа. Также доказано, что теория, двойственная к произвольной теории в этом фрагменте, имеет конечную аксиоматизацию.

Строго позитивные логики, частичный порядок

Короткий адрес: https://sciup.org/142236614

IDR: 142236614

Список литературы Стройный порядок на строго позитивных формулах

Kruskal J.В. The theory of well quasi-ordering: a frequently discovered concept // J. Combin. Theory. 1972. Ser. A 13. P. 297-305.
Nash-Williams C.St.J.A. On well-quasi-ordering finite trees // Proceedings of Cambridge Phil.Soc 59. 1963. P. 833-835.
Rathjen М., Van der Meeren J., Weiermann A. Well-partial-orderings and the big Veblen number // Archive for Mathematical Logic. 2015. V. 54. P. 193-230.
de Jongh D.H.J., Parikh R. Well-partial orderings and hierarchies // Nederl. Akad. Wetensch. 1977. Proc. Ser. A 80 = Indag. Math. 39, N 3. P. 195-207.
Дашков E.B. О позитивном фрагменте полимодальной логики доказуемости GLP // Математические Заметки. 2012. Вып. 91, № 3. С. 331-346.
Sofronie-Stokkermans V. Locality and subsumption testing in EL and some of its extensions // Advances in Modal Logic. 2008. V. 7 (eds.: C.Areces and R.Goldblatt). P. 315-339.
Boolos G. The Logic of Provability. Cambridge University Press, 1993.
Shapirovskiy I. PSPACE-decidabilitv of Japaridze's polvmodal logic // Advances in Modal Logic. 2008. V. 7 (College Publications, London). P. 289-304.
Beklemishev L.D. Positive provability logic for uniform reflection principles // Annals of Pure and Applied Logic. 2014. V. 165. P. 82-105.
Beklemishev L.D. On the reflection calculus with partial conservativitv operators // Lecture Notes in Computer Science. 2017. V. 10388. P. 48-67.
Beklemishev L.D. A universal algebra for the variable-free fragment of RCV // Symposium on Logical Foundations of Computer Science, S. Artemov and A. Nerode, editors, Lecture Notes in Computer Science. 2018.
Jackson M. Semilattices with closure // Algebra Universalis. 2004. V. 52. P. 1-37.
Kikot S., Kurucz A., Tanaka Y., Wolter F., Zakharyaschev M. Kripke completeness of strictly positive modal logics over meet-semilattices with operators // Journal of Symbolic Logic. 2019. V. 84. P. 533-588.
Baader F., Brandt S., Lutz C. Pushing the EL envelope // Proc. of the 19th Joint International Conference of Artificial Intelligence. 2005.
Baader F., Brandt S., Lutz C. Pushing the EL envelope. LTCS-Report 05-01, Institute for Theoretical Computer Science, Dresden University of Technology, 2005.
Baader F., Brandt S., Suntisrivaraporn Is tractable reasoning in extensions of the description logic EL useful in practice? Proc. of the Methods for Modalities Workshop, Berlin, Germany, 2005.
Gabelaia D., Kurucz A., Wolter F., M. Zakharyaschev M. Non-primitive recursive decidability of products of modal logics with expanding domains // Annals of Pure and Applied Logic. 2006. V. 142(1-3). P. 245-268.
Simpson S.G. Nichtbeweisbarkeit von gewissen kombinatorischen Eigenschaften endlicher Baume // Arch. Math. Logik Grundlag. 1985. V. 25(1). P. 45-65.
Dzamonja M., Schmitz S., Schnoebelen P. On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders // Well-Quasi Orders in Computation, Logic, Language and Reasoning. 2020. Trends in Logic, V. 53 (Schuster P., Seisenberger M., Weiermann A. editors), Springer, Cham. P. 29-54.
Simpson S. BQO theory and Fraisse's Conjecture. Recursive Aspects of Descriptive Set Theory. 1985. Mansfield R., Weitkamp G. editors, Oxford University Press, Oxford.
Laver R. On Fraisse's order type conjecture // Annals of Mathematics. 1971. V. 93. P. 89-111.
Carlucci L. Worms, gaps, and hydras // Mathematical Logic Quarterly. 2005. V. 51(4). P. 342-350.
Gallier J. WThat's so special about Kruskal's theorem and the ordinal Г0? A survey of some results in proof theory // Annals of Pure and Applied Logic. 1991. V. 53. P. 199-260.
Schuster P., Seisenberger M., Weiermann A. (editors) Well-Quasi Orders in Computation, Logic, Language and Reasoning // Trends in Logic. 2020. V. 53.

Еще

Статья научная