Cardinality reduction theorem for logics ${\mathrm{QHC}}$ and ${\mathrm{QH4}}$

A. A. Onoprienko

Algebra i logika, Tome 61 (2022) no. 6, pp. 720-741.

Résumé

The joint logic of problems and propositions ${\mathrm{QHC}}$ introduced by S. A. Melikhov, as well as intuitionistic modal logic ${\mathrm{QH4}}$, is studied. An immersion of these logics into classical first-order predicate logic is considered. An analog of the Löwenheim–Skolem theorem on the existence of countable elementary submodels for ${\mathrm{QHC}}$ and ${\mathrm{QH4}}$ is established.

Détail

Keywords: nonclassical logics, Kripke semantics, translation.

Bibliographie

[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] A. N. Kolmogorov, Izbrannye trudy. Matematika i mekhanika, Nauka, M., 1985

[4] A. N. Kolmogorov, “O printsipe tertium non datur”, Matem. sb., 32:4 (1925), 646–667

[5] A. Heyting, Intuitionism. An introduction, Stud. Logic Found. Math., North-Holland Publ. Co, Amsterdam, 1956 | MR | Zbl

[6] S. A. Melikhov, Mathematical semantics of intuitionistic logic, arXiv: 1504.03380 [math.LO]

[7] A. S. Troelstra, “Aspects of constructive mathematics”, Handbook of mathematical logic, Stud. Logic Found. Math., 90, ed. J. Barwise, North-Holland Publ. Co., Amsterdam–New York–Oxford, 1977, 973–1052 | DOI | MR

[8] A. S. Troelstra, H. Schwichtenberg, Basic proof theory, Camb. Tracts Theor. Comput. Sci., 43, Cambridge Univ. Press, Cambridge, 1996 | MR | Zbl

[9] G. Kreisel, “Perspectives in the philosophy of pure mathematics”, 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, eds. P. Suppes et al.,, North-Holland Publ. Co., Amsterdam-London; American Elsevier Publ. Co., New York, 1973, 255–277 | DOI | MR

[10] P. Martin-Löf, Intuitionistic Type Theory. Notes by Giovanni Sambin of a Series of Lectures given in Padua, June 1980, Studies in Proof Theory. Lecture Notes, 1, Bibliopolis, Napoli, 1984 | MR | Zbl

[11] S. K. Klini, Vvedenie v metamatematiku, Inostr. lit-ra, M., 1957

[12] S. N. Artemov, “Explicit provability and constructive semantics”, Bull. Symb. Log., 7:1 (2001), 1–36 | DOI | MR | Zbl

[13] S. N. Artemov, “Podkhod Kolmogorova i Gedelya k intuitsionistskoi logike i raboty poslednego desyatiletiya v etom napravlenii”, UMN, 59:2(356) (2004), 9–36 | DOI | MR

[14] K. Gödel, “Eine Interpretation des intuitionistischen Aussagenkalküls”, Ergebnisse Math. Kolloquium Wien, 4 (1933), 39–40 | Zbl

[15] K. Gödel, “Vortrag bei Zilsel”, Kurt Gödel Collected Works, v. III, Unpublished essays and lectures, ed. S. Feferman, Oxford Univ. Press, New York, NY, 1995, 86–113 | MR

[16] S. C. Kleene, “On the interpretation of intuitionistic number theory”, J. Symb. Log., 10:4 (1945), 109–124 | DOI | MR | Zbl

[17] Yu. T. Medvedev, “Finitnye zadachi”, Dokl. AN SSSR, 142:5 (1962), 1015–1018 | Zbl

[18] A. S. Troelstra, D. Van Dalen, Constructivism in mathematics, Stud. Logic Found. Math., 121, 123, North-Holland, Amsterdam etc., 1988 | Zbl

[19] J. Yu, “Self-referentiality of Brouwer-Heyting-Kolmogorov semantics”, Ann. Pure Appl. Logic, 165:1 (2014), 371–388 | DOI | MR | Zbl

[20] S. Artemov, T. Protopopescu, “Intuitionistic epistemic logic”, Rev. Symb. Log., 9:2 (2016), 266–298 | DOI | MR | Zbl

[21] D. M. Gabbay, “An overview of fibred semantics and the combination of logics”, Frontiers of combining systems, First int. workshop (Munich, Germany, March 26-29, 1996), Appl. Log. Ser., 3, eds. F. Baader et al., Kluwer Academic Publ., Dordrecht, 1996, 1–55 | DOI | MR | Zbl

[22] L. Fariñ as del Cerro, A. Herzig, “Combining classical and intuitionistic logic. Or: Intuitionistic implication as a conditional”, Frontiers of combining systems, First int. workshop (Munich, Germany, March 26-29, 1996), Appl. Log. Ser., 3, eds. F. Baader et al., Kluwer Academic Publ., Dordrecht, 1996, 93–102 | DOI | MR | Zbl

[23] C. Caleiro, J. Ramos, “Combining classical and intuitionistic implications”, Frontiers of combining systems, 6th international symposium, FroCoS 2007, Proc. (Liverpool, UK, September 10-12, 2007), Lecture Notes Comput. Sci., Lecture Notes Artif. Intell., 4720, eds. Konev B. et al., Springer, Berlin, 2007, 118–132 | DOI | Zbl

[24] C. Caleiro, J. Ramos, “From fibring to cryptofibring. A solution to the collapsing problem”, Log. Univers., 1:1 (2007), 71–92 | DOI | MR | Zbl

[25] S. Lewitzka, “A modal logic amalgam of classical and intuitionistic propositional logic”, J. Log. Comput., 27:1 (2017), 201–212 | DOI | MR | Zbl

[26] S. Niki, H. Omori, “Another combination of classical and intuitionistic conditionals”, Electron. Proc. Theor. Comput. Sci., 358 (2022), 174–188 | DOI | MR

[27] A. A. Onoprienko, “Predikatnyi variant sovmestnoi logiki zadach i vyskazyvanii”, Matem. sb., 213:7 (2022), 97–120 | DOI | MR

[28] R. I. Goldblatt, “Grothendieck topology as geometric modality”, Z. Math. Logik Grundlagen Math., 27 (1981), 495–529 | DOI | MR | Zbl

[29] R. I. Goldblatt, “Cover semantics for quantified lax logic”, J. Log. Comput., 21:6 (2011), 1035–1063 | DOI | MR | Zbl

[30] A. G. Dragalin, Matematicheskii intuitsionizm. Vvedenie v teoriyu dokazatelstv, Nauka, M., 1979 | MR

[31] M. Fairtlough, M. Mendler, “Propositional lax logic”, Inf. Comput., 137:1 (1997), 1–33 | DOI | MR | Zbl

[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:4 (2001), 541–554 | DOI | MR | Zbl

[34] S. Artemov, T. Protopopescu, Intuitionistic epistemic logic, arXiv: 1406.1582v2 [math.LO]

[35] A. A. Onoprienko, “Semantika tipa Kripke dlya propozitsionalnoi logki zadach i vyskazyvanii”, Matem. sb., 211:5 (2020), 98–125 | DOI | MR | Zbl

[36] A. A. Onoprienko, “Topologicheskie modeli propozitsionalnoi logiki zadach i vyskazyvanii”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 2022, no. 5, 25–30 | MR

[37] D. M. Gabbay, D. Skvortsov, V. Shehtman, Quantification in nonclassical logic, v. I, Stud. Logic Found. Math., 153, Elsevier, Amsterdam, 2009 | MR | Zbl

[38] J. van Benthem, Modal logic and classical logic, Indices. Monogr. Philos. Logic Formal Linguist., III, Bibliopolis, Napoli, 1985 | MR

[39] M. N. Rybakov, A. V. Chagrov, “Standartnye perevody neklassicheskikh formul i otnositelnaya razreshimost logik”, Trudy nauchno-issledovatelskogo seminara Logicheskogo tsentra Instituta filosofii RAN, XIV, Izd-vo Instituta filosofii RAN, M., 2000, 81–98

[40] N. K. Vereschagin, A. Shen, Lektsii po matematicheskoi logike i teorii algoritmov, v. 2, Yazyki i ischisleniya, 4-e izd., ispr., MTsNMO, M., 2012

[41] V. E. Plisko, V. Kh. Khakhanyan, Intuitsionistskaya logika, Izd-vo pri mekh.-mat. f-te MGU, M., 2009

[42] M. Kracht, “Modal consequence relation”, Handbook of Modal Logic, Stud. Log. Pract. Reason, 3, ed. P. Blackburn, Elsevier, Amsterdam, 2007 | MR

[43] S. P. Odintsov, S. O. Speranskii, S. A. Drobyshevich, Vvedenie v neklassicheskie logiki, ucheb. posobie, RITs NGU, Novosibirsk, 2014