The simple substitution property for superintuitionistic propositional logics and its relation to the separability property

V. I. Khomich

Izvestiya. Mathematics , Tome 67 (2003) no. 2, pp. 377-404.

Résumé

We study the simple substitution property for superintuitionistic propositional calculi, which are axiomatizations of superintuitionistic propositional logic, and obtain an algebraic criteria for the existence of this property. This is used to prove that many logics, including almost all of those generated by formulae in one variable, do not have the simple substitution property. We obtain a series of results that establish a connection between separability and possession of this property by axiomatizations of the logics considered.

Bibliographie

[1] Sasaki K., “The simple substitution property of the intermediate propositional logics”, Bulletin of the Section of Logic. Polish Acad. Sci. Inst. Phil. and Sociol., 18:3 (1989), 94–99 | MR | Zbl

[2] Klini S. K., Vvedenie v metamatematiku, IL, M., 1957

[3] Wajsberg M., “Untersuchungen über den Aussagenkalkül von A. Heyting”, Wiadomos̀ci matematyczne, 46 (1938), 45–101

[4] Hosoi T., Sasaki K., “Finite logics and simple substitution property”, Bulletin of the Section of Logic. Polish Acad. Sci. Inst. Phil. and Sociol., 19:3 (1990), 74–78 | MR | Zbl

[5] Sasaki K., “The simple substitution property of the intermediate propositional logics of finite slices”, Studia Logica, 52:1 (1993), 41–62 | DOI | MR | Zbl

[6] Nishimura I., “On formulas of one veriable in intuitionistic propositional calculus”, J. Symbolic Logic, 25:4 (1960), 327–331 | DOI | MR | Zbl

[7] Hosoi T., “On intermediate logics, I”, J. of the faculty of science. University Tokyo. Section I, 14:2 (1967), 293–312 | MR

[8] Maksimova L. L., “Predtablichnye superintuitsionistskie logiki”, Algebra i logika, 11:5 (1972), 558–570 | MR | Zbl

[9] Khomich V. I., “O svoistve prostoi podstanovki dlya superintuitsionistskikh propozitsionalnykh logik”, Dokl. RAN, 374:3 (2000), 318–320 | MR | Zbl

[10] Khomich V. I., “O svoistve prostoi podstanovki dlya superintuitsionistskikh propozitsionalnykh ischislenii i logik”, Tr. IV Mezhdunarodnoi konferentsii “Diskretnye modeli v teorii upravlyayuschikh sistem”, MAKS Press, M., 2000, 125–127

[11] Kreisel G., Putnam H., “Eine Unableitbarkeitsbeweismethode für den intuitionistischen Aussagenkalkül”, Arch. f. Math. Logik Grundlagenforschung, 3 (1957), 74–78 | DOI | MR | Zbl

[12] McKay C. G., “The non-separability of a certain finite extension of Heyting's propositional logic”, Proceedings Koninklijke Nederlandse Akad. van Wetenschappen. Ser. A, 71:3 (1968), 312–315 | MR | Zbl

[13] Hosoi T., “Non-separable intermediate propositional logics”, J. Tsuda College, 8 (1976), 13–18 | MR

[14] Khomich V. I., “Teorema otdelimosti dlya superintuitsionistskikh ischislenii vyskazyvanii”, DAN SSSR, 229:6 (1976), 1327–1329 | MR | Zbl

[15] Khomich V. I., “Otdelimost superintuitsionistskikh propozitsionalnykh logik”, Issledovaniya po teorii algorifmov i matematicheskoi logike, Nauka, M., 1979, 98–115 | MR

[16] Khomich V. I., “O probleme otdelimosti dlya superintuitsionistskikh propozitsionalnykh logik”, DAN SSSR, 254:4 (1980), 820–823 | MR | Zbl

[17] Khomich V. I., “Ob otdelimykh superintuitsionistskikh propozitsionalnykh ischisleniyakh i o kon'yunktivno nerazlozhimykh elementakh v implikativnykh polustrukturakh”, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 32:2 (1986), 149–180 | DOI | MR | Zbl

[18] Khomich V. I., “O svoistvakh superintuitsionistskikh propozitsionalnykh ischislenii”, Sib. matem. zhurn., 31:6 (1990), 158–175 | MR | Zbl

[19] Horn A., “The separation theorem of intuitionist propositional calculus”, J. Symbolic Logic, 27:4 (1962), 391–399 | DOI | MR

[20] Hosoi T., “On the separation theorem of intermediate propositional calculi”, Proc. Japan Acad., 42:6 (1966), 535–538 | DOI | MR | Zbl

[21] Hosoi T., “The separation theorem on the classical system”, J. of the faculty of science. University Tokyo. Section I, 12:2 (1966), 223–230 | MR | Zbl

[22] Karri Kh. B., Osnovaniya matematicheskoi logiki, Mir, M., 1969

[23] Raseva E., Sikorskii R., Matematika metamatematiki, Nauka, M., 1972 | MR

[24] Khomich V. I., “O vlozhimosti nekotorykh obobschenii psevdobulevykh algebr”, Dokl. RAN, 350:2 (1996), 174–177 | MR | Zbl

[25] Khomich V. I., “O vlozhenii implikatur”, Voprosy matematicheskoi logiki i teorii algoritmov, VTs AN SSSR, M., 1988, 17–33 | MR

[26] Birkgof G., Teoriya struktur, IL, M., 1952

[27] Khomich V. I., “O superintuitsionistskikh propozitsionalnykh logikakh, svyazannykh s chastichno uporyadochennymi mnozhestvami”, Izv. AN SSSR. Ser. matem., 55:2 (1991), 384–406 | MR | Zbl

[28] Khomich V. I., “O svoistve superintuitsionistskikh propozitsionalnykh ischislenii, svyazannom s otdelimostyu etikh ischislenii”, Matematicheskie voprosy kibernetiki, no. 7, Nauka, M., 1998, 227–242 | MR

[29] Jaskows̀ki S., “Recherches sur le système de la logique intuitioniste”, Actualites scientifiques et industrielles, 393, Paris, 1936, 58–61 | Zbl

[30] Pilchak B. Yu., “Ob ischislenii zadach”, Ukr. matem. zhurn., 4:2 (1952), 174–194 | MR | Zbl

[31] Khomich V. I., “O predstavlenii konechnykh psevdobulevykh algebr i ob odnom ego primenenii”, Matem. zametki, 52:2 (1992), 127–137 | MR

[32] Khomich V. I., “Ob izomorfnoi vlozhimosti psevdobulevykh algebr i nekotorykh ikh obobschenii”, Matematicheskie voprosy kibernetiki, no. 8, Nauka, M., 1999, 191–218 | MR

[33] McKay C. G., “On finite logics”, Proceedings Koninklijke Nederlandse Akad. van Wetenschappen. Ser. A, 70:3 (1967), 363–365 | MR | Zbl