Стройный порядок на строго позитивных формулах
Автор: Святловский М.В.
Журнал: Труды Московского физико-технического института @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.
Статья научная
