ТЕОРЕМА О ПОНИЖЕНИИ МОЩНОСТИ ДЛЯ ЛОГИК QHC И QH4 (2022)
Рассматривается совместная логика задач и высказываний QHC, введённая С. А. Мелиховым, а также интуиционистская модальная логика QH4. Рассмотрено погружение этих логик в классическую логику предикатов первого порядка. Установлен аналог теоремы Лёвенгейма-Сколема о счётной элементарной подмодели для логик QHC и QH4.
Идентификаторы и классификаторы
- Префикс DOI
- 10.33048/alglog.2022.61.604
- eLIBRARY ID
- 54693360
Объединённая логика задач и высказываний QHC, рассматриваемая в настоящей работе, введена С. А. Мелиховым [1, 2]. В этой логике каждая переменная и каждая формула имеют один из двух сортов: либо высказывание, либо задача. Формулы сорта высказывание и сорта задача связаны между собой двумя модальностями ? и !. Применив ! к высказыванию p, мы получим задачу !p, которую можно неформально понимать как „доказать высказывание p“. А применив ? к задаче α, мы получим высказывание ?α, которое можно неформально понимать как „задача α имеет решение“. Создание и изучение системы QHC мотивировано неформальным исчислением задач А. Н. Колмогорова и лежит в русле исследований
конструктивной семантики Брауэра–Гейтинга–Колмогорова, [3–20].
Список литературы
1. | S. A. Melikhov, A Galois connection between classical and intuitionistic logics. I: Syntax, arXiv:1312.2575 [math.LO]. | |
---|---|---|
2. | S. A. Melikhov, A Galois connection between classical and intuitionistic logics. II: Semantics, arXiv:1504.03379 [math.LO]. | |
3. | А. Н. Колмогоров, Избранные труды. Математика и механика, М., Наука, 1985. | |
4. | А. Н. Колмогоров, О принципе tertium non datur, Матем. сб., 32, № 4 (1925), 646-667. | |
5. | A. Heyting, Intuitionism. An introduction (Stud. Logic Found. Math.), Amsterdam, North-Holland Publ. Co., 1956. | |
6. | S. A. Melikhov, Mathematical semantics of intuitionistic logic, arXiv: 1504.03380 [math.LO]. | |
7. | A. S. Troelstra, Aspects of constructive mathematics, in: J. Barwise (ed.), Handbook of mathematical logic (Stud. Logic Found. Math., 90), Amsterdam-New York-Oxford, North-Holland Publ. Co., 1977, 973-1052. | |
8. | A. S. Troelstra, H. Schwichtenberg, Basic proof theory (Camb. Tracts Theor.Comput. Sci., 43), Cambridge, Cambridge Univ. Press, 1996. | |
9. | G. Kreisel, Perspectives in the philosophy of pure mathematics, in: P. Suppes (ed.) et al., Logic, methodology and philosophy of science. IV. Proc. Fourth Int. Congr. Logic, Methodol. Philos. Sci. (Bucharest, August 29-September 4, 1971), (Stud. Logic Found. Math., 74), Amsterdam-London, North-Holland Publ. Co.; New York, American Elsevier Publ. Co., 1973, 255-277. | |
10. | P. Martin-Lof Intuitionistic Type Theory. Notes by Giovanni Sambin of a Series of Lectures given in Padua, June 1980 (Studies in Proof Theory. Lecture Notes, 1), Napoli, Bibliopolis, 1984. | |
11. | С. К. Клини, Введение в метаматематику, М., Иностр. лит-ра, 1957. | |
12. | S. N. Artemov, Explicit provability and constructive semantics, Bull. Symb. Log., 7, No. 1 (2001), 1-36. EDN: LGWGLX | |
13. | С. Н. Артёмов, Подход Колмогорова и Гёделя к интуиционистской логике и работы последнего десятилетия в этом направлении, УМН, 59, № 2(356) (2004), 9-36. | |
14. | K. Godel, Eine Interpretation des intuitionistischen Aussagenkalkuls, Ergebnis-se Math. Kolloquium Wien, 4 (1933), 39-40. | |
15. | K. Godel, Vortrag bei Zilsel, in: S. Feferman (ed.), Kurt Godel Collected Works, v. III: Unpublished essays and lectures, New York, NY, Oxford Univ. Press, 1995, 86-113. | |
16. | S. C. Kleene, On the interpretation of intuitionistic number theory, J. Symb. Log., 10, No. 4 (1945), 109-124. | |
17. | Ю. Т. Медведев, Финитные задачи, Докл. АН СССР, 142, № 5 (1962), 1015-1018. | |
18. | A. S. Troelstra, D. Van Dalen, Constructivism in mathematics (Stud. Logic Found. Math., 121, 123), Amsterdam etc., North-Holland, 1988. | |
19. | J. Yu, Self-referentiality of Brouwer-Heyting-Kolmogorov semantics, Ann. Pure Appl. Logic, 165, No. 1 (2014), 371-388. EDN: SRNJGV | |
20. | S. Artemov, T. Protopopescu, Intuitionistic epistemic logic, Rev. Symb. Log., 9, No. 2 (2016), 266-298. EDN: WUWTBZ | |
21. | D. M. Gabbay, An overview of fibred semantics and the combination of logics, in: F. Baader (ed.) et al., Frontiers of combining systems. First int. workshop (Munich, Germany, March 26-29, 1996), (Appl. Log. Ser., 3), Dordrecht, Kluwer Academic Publ., 1996, 1-55. | |
22. | L. Farinas del Cerro, A. Herzig, Combining classical and intuitionistic logic. Or: Intuitionistic implication as a conditional., in: F. Baader (ed.) et al., Frontiers of combining systems. First int. workshop (Munich, Germany, March 26-29, 1996), (Appl. Log. Ser., 3), Dordrecht, Kluwer Academic Publ., 1996, 93-102. | |
23. | C. Caleiro, J. Ramos, Combining classical and intuitionistic implications, in: Konev, Boris (ed.) et al., Frontiers of combining systems. 6th international symposium, FroCoS 2007 (Liverpool, UK, September 10-12, 2007), Proc. (Lecture Notes Comput. Sci., 4720; Lecture Notes Artif.Intell.), Berlin, Springer, 2007, 118-132. | |
24. | C. Caleiro, J. Ramos, From fibring to cryptofibring. A solution to the collapsing problem, Log. Univers., 1, No. 1 (2007), 71-92. | |
25. | S. Lewitzka, A modal logic amalgam of classical and intuitionistic propositional logic, J. Log.Comput., 27, No. 1 (2017), 201-212. | |
26. | S. Niki, H. Omori, Another combination of classical and intuitionistic conditionals, Electron. Proc. Theor.Comput. Sci., 358 (2022), 174-188. EDN: GWKMAL | |
27. | А. А. Оноприенко, Предикатный вариант совместной логики задач и высказываний, Матем. сб., 213, № 7 (2022), 97-120. EDN: TKKZSF | |
28. | R. I. Goldblatt, Grothendieck topology as geometric modality, Z. Math. Logik Grundlagen Math., 27 (1981), 495-529. | |
29. | R. I. Goldblatt, Cover semantics for quantified lax logic, J. Log.Comput., 21, No. 6 (2011), 1035-1063. EDN: XYZZBR | |
30. | А. Г. Драгалин, Математический интуиционизм. Введение в теорию доказательств, М., Наука, 1979. | |
31. | M. Fairtlough, M. Mendler, Propositional lax logic, Inf.Comput., 137, No. 1 (1997), 1-33. EDN: XRLXUW | |
32. | M. Fairtlough, M. Walton, Quantified lax logic, Tech. Report CS-97-11, Dep.Comput. Sci., Univ. Sheffield, July 1997. | |
33. | P. Aczel, The Russell-Prawitz modality, Math. Struct.Comput. Sci., 11, No. 4 (2001), 541-554. EDN: FKYDLH | |
34. | S. Artemov, T. Protopopescu, Intuitionistic epistemic logic, arXiv:1406.1582v2[math.LO]. | |
35. | А. А. Оноприенко, Семантика типа Крипке для пропозициональной логки задач и высказываний, Матем. сб., 211, № 5 (2020), 98-125. EDN: LFUFVT | |
36. | А. А. Оноприенко, Топологические модели пропозициональной логики задач и высказываний, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2022, № 5, 25-30. EDN: TWUONF | |
37. | D. M. Gabbay, D. Skvortsov, V. Shehtman, Quantification in nonclassical logic. Vol. I (Stud. Logic Found. Math., 153), Amsterdam, Elsevier, 2009. | |
38. | J. van Benthem, Modal logic and classical logic (Indices. Monogr. Philos. Logic Formal Linguist., III), Napoli, Bibliopolis, 1985. | |
39. | М. Н. Рыбаков, А. В. Чагров, Стандартные переводы неклассических формул и относительная разрешимость логик, Труды научно-исследовательского семинара Логического центра Института философии РАН, XIV, М., Изд-во Института философии РАН, 2000, 81-98. | |
40. | Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов, Ч. 2. Языки и исчисления, 4-е изд., испр., М., МЦНМО, 2012. | |
41. | В. Е. Плиско, В. Х. Хаханян, Интуиционистская логика, М., Изд-во при мех.-мат. ф-те МГУ, 2009. | |
42. | M. Kracht, Modal consequence relation, in: P. Blackburn (ed.), Handbook of Modal Logic (Stud. Log. Pract. Reason., 3), Amsterdam, Elsevier, 2007. | |
43. | С. П. Одинцов, С. О. Сперанский, С. А. Дробышевич, Введение в неклассические логики, учеб. пособие, Новосибирск, РИЦ НГУ, 2014. |
Выпуск
Другие статьи выпуска
Понятие P-стабильности является частным случаем обобщённой стабильности полных теорий. Изучаются инъективные S-полигоны с P-стабильной теорией. Доказывается, что класс инъективных S-полигонов (P,1)-стабилен только в том случае, когда моноид S одноэлементен. Кроме того, описываются коммутативные и линейно упорядоченные моноиды S, класс инъективных S-полигонов над которыми (P,s)-, (P,a)- и (P,e)-стабилен.
Генерические алгоритмы решают проблемы на множествах почти всех входов, выдавая неопределённый ответ для остальных редких входов. В статье доказывается, что проблема равенства генерически разрешима в конечно порождённых полугруппах S, для которых существует такая конгруэнция θ, что полугруппа S/θ является бесконечным финитно аппроксимируемым моноидом с сокращениями и с разрешимой проблемой равенства. Это обобщает ранее полученный результат автора о генерической разрешимости проблемы равенства в конечно определённых полугруппах, которые остаются бесконечными при добавлении свойств коммутативности и сокращения. Отметим, что примерами таких полугрупп служат полугруппы с одним определяющим соотношением, а также так называемые сбалансированные полугруппы, для которых Вон доказал генерическую разрешимость проблемы равенства. В частности, сбалансированными являются классические полугруппы Цейтина и Маканина с неразрешимой проблемой равенства.
Доказывается, что сингулярная супералгебра с 2-мерной чётной частью изоморфна супералгебре B2∣3(φ,ξ,ψ). В частности, не существует бесконечномерных простых сингулярных супералгебр с 2-мерной чётной частью. Доказывается, что если сингулярная супералгебра содержит нечётный левый аннулятор, то она содержит невырожденный переключатель. Наконец, устанавливается, что для любого числа N≥5, за исключением чисел 6,7,8,11, существуют сингулярные супералгебры с переключателем размерности N. Для чисел N=6,7,8,11 не существует сингулярных N-мерных супералгебр с переключателем. |
---|
Изучаются семейства PI, состоящие из перестановок натурального ряда ω, степени которых принадлежат идеалу тьюринговых степеней I, и их скачки P′I. Для любого счётного тьюрингова идеала I приводятся описания спектров степеней семейств PI и их скачков P′I. Для некоторых идеалов I, порождённых в. п. степенями, определяются спектры семейств PI.
Рассматривается класс обобщённых дифференцирований, возникающий в связи с задачей присоединения единицы к алгебре с обобщённым дифференцированием, а также поиска обёртывающих для алгебр Новикова-Пуассона. Приводятся условия существования локализации алгебры с тернарным дифференцированием, а также условия, при которых по алгебре с тернарным дифференцированием можно построить алгебру Новикова-Пуассона и Йорданову супералгебру. И наконец, показывается, как простота алгебры с обобщённым дифференцированием по Брешару связана с простотой соответствующей алгебры Новикова.
Ранее К. Дошен и М. Божич ввели четыре независимые интуиционистские модальные логики - по одной для каждого из четырёх типов модальных операторов: необходимости N, возможности P, невозможности Im и не-необходимости Un. Эти логики обозначаются HKM, где M∈{N,P,Un,Im}. Интерес к тому, чтобы рассматривать четыре типа модальных операторов по отдельности, связан именно с тем, что над интуиционистской логикой они не могут быть сведены друг к другу. Здесь изучаются расширения логик HKM, у которых есть нормальные напарники. Оказывается, что нормальные напарники есть у всех расширений логик HKN и HKUn. Для расширений HKP и HKIm получен критерий существования нормальных напарников, который заключается в присутствии некоторого модального закона двойного отрицания. Также показывается, как добавление этого закона влияет на выразительные возможности логики. Особый интерес представляет результат о том, что расширения HKP и HKIm имеют нормальных напарников, только если они дефинициально эквивалентны расширениям HKN и HKUn соответственно. Этот результат является ещё одним примером различия в поведении четырёх типов модальных операторов над интуиционистской логикой.
Издательство
- Издательство
- НГУ
- Регион
- Россия, Новосибирск
- Почтовый адрес
- 630090, Новосибирская область, г. Новосибирск, ул. Пирогова, д. 1.
- Юр. адрес
- 630090, Новосибирская область, г. Новосибирск, ул. Пирогова, д. 1.
- ФИО
- Федорук Михаил Петрович (Руководитель)
- E-mail адрес
- rector@nsu.ru
- Контактный телефон
- +7 (383) 3634000
- Сайт
- https://www.nsu.ru/