A simple example of blocking the Craig trick
Main Article Content
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
Downloads
Download data is not yet available.
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.