New constants in pretabular superintuitionistic logics: P.~Novikov's approach

A. K. Koshcheeva

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 47 (2016) no. 1, pp. 3-33.

Résumé

In the late fifties of the twentieth century a problem was posed by P. S. Novikov concerning new logical connectives as extranotions for a language with standard logical connectives $\vee$, $\wedge$, $\rightarrow$, $\neg$. Ya. S. Smetanich has given exact formulations for approach of Novikov to the concept of new logical connectives in superintuitionistic logics (new logical connective, Novikov completeness). In the present paper, the Novikov problem concerning new additional constants is considered in pretabular superintuitionistic logics $LC,$ $L2,$ $L3$: the logic of chains, the logic of rooted frames of the depth not exceeding $2$ (fans), the logic of rooted frames with the top and with the depth not exceeding $3$ (diamonds). The classification for the family of all Novikov-complete extensions of the pretabular superintuitionistic logics in a language containing additional logical constants is described. For these logics, the classification is obtained in the terms of finite frame with coloring: in the language with several additional constants for $LC$ and $L2$ and with a single additional constant for $L3$. Decidability of the (algorithmic) conservativeness problem for extensions of all pretabular superintuitionistic logics is established. The algorithmic problem of conservativeness recognition is investigated.

Détail

Keywords: pretabular superintuitionistic logics, new logical constants, Novikov's completeness, algorithmic problem of the conservativeness.

Bibliographie

[1] Grigoliya R. Sh., “Free S4.3-algebra with a finite number of generators”, Studies in nonclassical logics and formal systems, Nauka, M., 1983, 281–287 (in Russian)

[2] Ershov Yu. L., Palyutin E. A., Mathematical logic, Nauka, M., 1987, 336 pp.

[3] Zakharyaschev M. V., “Syntax and semantics of intermediate logics”, Algebra and Logic, 28:4 (1989), 262–282 | MR | Zbl

[4] Kleene S. C., Introduction to metamathematics, D. Van Nostrand Company, New York, 1952 | MR

[5] Koshcheeva A. K., “Axiomatics of P. S. Novikov complete extensions of the superintuitionistic logic $L2$ in the language containing an additional constant”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2014, no. 3, 28–39 (in Russian)

[6] Koshcheeva A. K., “A new constant in superintuitionistic logic $L3$”, Algebra and Logic, 54:1 (2015), 23–35 | DOI | MR | Zbl

[7] Koshcheeva A. K., New constants in pretabular superintuitionistic logics, Cand. Sci. (Phys.-Math.) Dissertation, Krasnoyarsk, 2015, 84 pp. (in Russian)

[8] Kuznetsov A. V., “Some properties of the structure of manifolds of pseudoboolean algebras”, Proceedings of XI All-Union Algebraic Colloquium (Chisinau, 1971), 255–256 (in Russian)

[9] Kuznetsov A. V., Gerchiu V. Ya., “Superintuitionistic logics and finite approximability”, Sov. Math., Dokl., 11 (1970), 1614–1619 | MR | MR | Zbl

[10] Lavrov I. A., Maksimova L. L., Tasks in set theory, mathematical logic and the theory of algorithms, Fizmatlit, M., 2004, 256 pp.

[11] Maksimova L. L., “Pretabular superintuitionistic logics”, Algebra and Logic, 11:5 (1972), 308–314 | DOI | MR | Zbl

[12] Maksimova L. L., Schreiner P. A., “Algorithms of the recognition of the tabularity and pretabularity in the extensions of the intuitionistic calculus”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 6:3 (2006), 49–58 (in Russian) | MR

[13] Novikov P. S., Constructive mathematical logic from the point of view classical logic, Nauka, M., 1977, 328 pp.

[14] Plisko V. E., Khakhanyan V. H., Intuitionistic logic, Moscow State University, M., 2009, 159 pp.

[15] Rasiowa H., Sikorski R., The mathematics of metamathematics, PWN, Warszawa, 1963 | MR

[16] Skvortsov D. P., “On intuitionistic propositional calculus with an additional logical connective”, Studies in nonclassical logics and formal systems, Nauka, M., 1983, 154–173 (in Russian)

[17] Smetanich Ya. S., “On the completeness of the propositional calculus with additional operations in one argiment”, Tr. Mosk. Mat. Obs., 9, 1960, 357–371 (in Russian) | MR | Zbl

[18] Smetanich Ya. S., “On statement calculi with an additional operation”, Soviet Math. Doklady, 2 (1961), 937–939 | MR | Zbl

[19] Chagrov A. V., “Undecidable properties of superintuitionistic logics”, Matematicheskie voprosy kibernetiki, 5, Fizmatlit, M., 1994, 62–108 (in Russian) | Zbl

[20] Esakia L. L., Heyting algebras, Metsniereba, Tbilisi, 1985, 104 pp.

[21] Yankov V. A., “Constructing a sequence of strongly independent superintuitionistic propositional calculi”, Soviet Math. Dokl., 9 (1968), 806–807 | MR | Zbl

[22] Yashin A. D., “A new regular constant in intuitionistic propositional logic”, Siberian Math. Journal, 37:6 (1996), 1242–1258 | DOI | MR | Zbl

[23] Yashin A. D., “On a new constant in intuitionistic propositional logic”, Fundam. Prikl. Mat., 5:3 (1999), 903–926 (in Russian) | MR | Zbl

[24] Yashin A. D., “Classification of Novikov complete logics with extra logical constants”, Algebra and Logic, 42:3 (2003), 207–216 | DOI | MR | Zbl

[25] Yashin A. D., “New constants in two pretabular superintuitionistic logics”, Algebra and Logic, 50:2 (2011), 171–186 | DOI | MR | Zbl

[26] Yashin A. D., Koshcheeva A. K., “New constants in the superintuitionistic logic $L2$”, Mathematical Notes, 94:5 (2013), 938–950 | DOI | DOI | MR | Zbl

[27] Bezhanishvili N., de Jongh D., Intuitionistic logic, http://www.illc.uva.nl/Research/Publications/Reports/PP-2006-25.text.pdf

[28] Chagrov A., Zakharyaschev M., Modal logic, Oxford University Press, Oxford, 1997, 605 pp. | MR | Zbl

[29] Dubashi D. P., “On decidable varieties of Heyting algebras”, J. Symb. Log., 57:3 (1992), 988–991 | DOI | MR

[30] Dummett M. A., “A propositional calculus with denumerable matrix”, J. Symb. Log., 24:2 (1959), 97–106 | DOI | MR | Zbl

[31] Dunn J. M., Meyer R. K., “Algebraic completeness results for Dummet's LC and its extensions”, Zeitschr. Math. Log. und Grundl. Math., 17 (1971), 225–230 | DOI | MR | Zbl

[32] Fitting M., Intuitionistic logic, model theory and forcing, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam–London, 1969, 191 pp. | MR | Zbl

[33] Gabbay D. M., “On some new intuitionistic propositional connectives, I”, Studia Logica, 36:1–2 (1977), 127–139 | DOI | MR | Zbl

[34] Goldblatt R. I., “Metamathematics of modal logics, I”, Rep. on Math. Logic, 6 (1976), 41–78 | MR

[35] Goldblatt R. I., “Metamathematics of modal logics, II”, Rep. on Math. Logic, 7 (1976), 21–52 | MR

[36] Hosoi T., “On intermediate logics, I”, J. Fac. Sci. Univ. Tokyo. Sec. 1, 1967, no. 14, 293–312 | MR

[37] Hosoi T., Ono H., “The intermediate logics of the second slice”, J. Fac. Sci. Univ. Tokyo. Sec. 1, 1970, no. 17, 457–461 | MR | Zbl

[38] Kirk R. E., “A characterization of the classes of finite tree frames which are adequate for the intuitionistic logic”, Zeitschr. Math. Log. und Grundl. Math., 26:6 (1980), 497–501 | DOI | MR | Zbl

[39] Kolmogoroff A., “Zur Deutung der intuitionistischen Logik”, Math. Z., 35:1 (1932), 58–65

[40] Ono H., “Kripke models and intermediate logics”, Publs. Res. Inst. Math. Sci. Kyoto Univ., 6:71 (1970), 461–476 | DOI | MR

[41] Yashin A. D., “New intuitionistic logical constants and Novikov completeness”, Studia Logica, 63:2 (1999), 151–180 | DOI | MR | Zbl

[42] Zakharyaschev M., Wolter F., Chagrov A., “Advanced modal logic”, Handbook of Philosophical Logic, v. 3, eds. Gabbay D. M., Guenthner F., Kluwer Acad. Publ., 2001, 83–266 | MR | Zbl