Простой пример блокировки аргумента Крейга
Article Sidebar
Main Article Content
Аннотация
Уильям Крейг сделал наблюдение, состоящее в том, что при довольно общих условиях выполняется следующее: если теория имеет рекурсивно перечислимую аксиоматику, то она имеет и рекурсивную аксиоматику. В работе обсуждаются эти условия и строится пример теории, когда условия теоремы Крейга не выполнены; в частности, построенная теория имеет рекурсивно перечислимую аксиоматику, но не имеет рекурсивной аксиоматики. При этом, добавив к правилам вывода построенной теории допустимое в ней правило, получаем теорию с тем же множеством теорем, но уже имеющую рекурсивную аксиоматику.
Скачивания
Article Details
Copyright (c) 2023 Михаил Николаевич Рыбаков
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Литература
Роджерс, 1972 – Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М: Мир, 1972.
Рыбаков, Чагров, 2000 – Рыбаков М.Н., Чагров А.В. Стандартные переводы неклассических формул и относительная разрешимость логик // Труды научноисследовательского семинара Логического центра Института философии РАН. М., 2000. Вып. XIV. С. 81–98.
Рыбаков, 2018 – Рыбаков М.Н. Аксиоматизируемость ненормальных и квазинормальных модальных предикатных логик первопорядково определимых классов шкал Крипке // Вестник ТвГУ. Серия: Прикладная математика. 2018. № 3. С. 81–94.
Craig, 1953 – Craig W. On axiomatizability within a system // The Journal of Symbolic Logic. 1953. Vol. 18. No. 1. P. 30–32.
Gabbay et al., 2009 – D. Gabbay, V. Shehtman, D. Skvortsov. Quantification in Nonclassical Logic, Vol. 1. Elsevier, 2009.
Harel, 1986 – Harel D. Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness // Journal of the ACM. 1986. Vol. 33. P. 224–248.
Kuznetsov et al., 2019 – Kuznetsov S., Lugovaya V., Ryzhova A. Craig’s trick and a non-sequential system for the Lambek calculus and its fragments // Logic Journal of the IGPL. 2019. Vol. 27. No. 3. P. 252–266.
Lambek, 1991 – Lambek J. On the calculus of syntactic types // In Structure of Language and Its Mathematical Aspects / R. Jakobson ed. American Mathematical Society, Providence, RI, 1991. P. 166–178.
Rybakov, Shkatov, 2018 – Rybakov M., Shkatov D. A recursively enumerable Kripke complete first-order logic not complete with respect to a first-order definable class of frames // Advances in Modal Logic 12. 2018. P. 531–540.
Rybakov, Shkatov, 2020 – Rybakov M., Shkatov D. Recursive enumerability and elementary frame definability in predicate modal logic // Journal of Logic and Computation. 2020. Vol. 30. No. 2. P. 549–560.
van Benthem, 1983 – J.A.F.K. van Benthem. Modal Logic and Classical Logic. Bibliopolis, Napoli, 1983.