A simple example of blocking the Craig trick
##plugins.themes.bootstrap3.article.sidebar##
Published:
07.11.2023
##plugins.themes.bootstrap3.article.main##
Abstract
William Craig observed that, under quite general conditions, a theory with a recursively enumerable axiomatization is also recursively axiomatizable. The paper discusses these conditions and builds a simple example of a theory for which the conditions of the Craig’s theorem are not satisfied; in particular, the constructed theory has a recursively enumerable axiomatization, but does not have a recursive axiomatization with the same set of inference rules. At the same time, extending the set of inference rules with some rules adm
##plugins.generic.usageStats.downloads##
##plugins.generic.usageStats.noStats##
##plugins.themes.bootstrap3.article.details##
How to Cite
Rybakov M. A simple example of blocking the Craig trick // Logicheskie Issledovaniya / Logical Investigations. 2023. VOL. 29. № 2. C. 36-58.
Issue
Section
Symbolic Logic
Copyright (c) 2023 Михаил Николаевич Рыбаков
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
Верещагин, Шень, 2017 – Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Ч. 3. Вычислимые функции. М: МЦНМО, 2017.
Роджерс, 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.
Роджерс, 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.