×

zbMATH — the first resource for mathematics

Propositional quantification in the topological semantics for \(\mathbf S4\). (English) Zbl 0949.03020
Summary: K. Fine and S. Kripke extended S5, S4, S4.2 and such to produce propositionally quantified systems such as \(\text{S5} \pi+,\text{S4}\pi +\), and \(\text{S}4.2 \pi+\): Given a Kripke frame, the quantifiers range over all the sets of possible worlds. \(\text{S}5\pi+\) is decidable and, as Fine and Kripke showed, many of the other systems are recursively isomorphic to second-order logic. In the present paper we consider the propositionally quantified system that arises from the topological semantics for S4, rather than from the Kripke semantics. The topological system, dubbed \(\text{S4}\pi t\), is strictly weaker than its Kripkean counterpart. We prove that second-order arithmetic can be recursively embedded in \(\text{S4}\pi t\). In the course of the investigation, we also sketch a proof of Fine’s and Kripke’s result that the Kripkean system \(\text{S}4\pi+\) is recursively isomorphic to second-order logic.

MSC:
03B45 Modal logic (including the logic of norms)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bull, R. A., “On modal logic with propositional quantifiers,” The Journal of Symbolic Logic , vol. 34 (1969) pp. 257–63. JSTOR: · Zbl 0184.28101
[2] Chellas, B., Modal Logic , Cambridge University Press, Cambridge, 1980. · Zbl 0431.03009
[3] Dishkant, H., “Set theory as modal logic,” Studia Logica , vol. 39 (1980), pp. 335–45. · Zbl 0463.03007
[4] Fine, K., “Propositional quantifiers in modal logic,” Theoria , vol. 36 (1970), pp. 336–46. · Zbl 0302.02005
[5] Gabbay, D., “Montague type semantics for modal logics with propositional quantifiers,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 17 (1971), pp. 245–49. · Zbl 0226.02015
[6] Gabbay, D., “On 2nd order intuitionistic propositional calculus with full comprehension,” Archiv für mathematische Logik und Grundlagenforsch , vol. 16 (1974), pp. 177–86. · Zbl 0289.02016
[7] Gabbay, D., Semantical investigations in Heyting’s intuitionistic logic , Reidel, Dordrecht, 1981. · Zbl 0453.03001
[8] Ghilardi, S., and M. Zawadowski, “Undefinability of propositional quantifiers in the modal system S4 ,” Studia Logica , vol. 55 (1995), pp. 259–71. · Zbl 0831.03008
[9] Gurevich, Y., and S. Shelah, “Interpreting second-order logic in the monadic theory of order,” The Journal of Symbolic Logic , vol. 48 (1983), pp. 816–28. JSTOR: · Zbl 0559.03008
[10] Gurevich, Y., and S. Shelah, “Monadic theory of order and topology in ZFC,” Annals of Mathematical Logic , vol. 23 (1983), pp. 179–98. · Zbl 0516.03007
[11] Henkin, L., “Completeness in the theory of types,” The Journal of Symbolic Logic , vol. 15 (1950), pp. 81–91. JSTOR: · Zbl 0039.00801
[12] Jech, T., Set Theory , Academic Press, San Diego, 1978. · Zbl 0419.03028
[13] Kaminski, M., and M. Tiomkin, “The expressive power of second-order propositional modal logic,” Notre Dame Journal of Formal Logic , vol. 37 (1996), pp. 35–43. · Zbl 0895.03005
[14] Kaplan, D., “S5 with quantifiable propositional variables,” The Journal of Symbolic Logic , vol. 35 (1970), p. 355.
[15] Kreisel, G., “Monadic operators defined by means of propositional quantification in intuitionistic logic,” Reports on Mathematical Logic , vol. 12 (1981), pp. 9–15. · Zbl 0464.03051
[16] Kremer, P., “Quantifying over propositions in relevance logic: non-axiomatisability of \(\forall p\) and \(\exists p\),” The Journal of Symbolic Logic , vol. 58 (1993), pp. 334–49. JSTOR: · Zbl 0786.03016
[17] Kremer. P., “On the complexity of propositional quantification in intuitionistic logic,” The Journal of Symbolic Logic , vol. 62 (1997), pp. 529–44. JSTOR: · Zbl 0887.03002
[18] Kripke, S., “A completeness theorem in modal logic,” The Journal of Symbolic Logic , vol. 24 (1959), pp. 1–14. JSTOR: · Zbl 0091.00902
[19] Kripke, S., “Semantical analysis of modal logic I, normal propositional calculi,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 9 (1963), pp. 67–96. · Zbl 0118.01305
[20] Kripke, S., [1963b], Semantical analysis of
[21] Lewis, C. I., and C. H. Langford, Symbolic Logic , 2d edition, Dover Publications, New York, 1932. · Zbl 0087.00802
[22] Löb, M. H., “Embedding first order predicate logic in fragments of intuitionistic logic,” The Journal of Symbolic Logic , vol. 41 (1976), pp. 705–18. JSTOR: · Zbl 0358.02012
[23] McKinsey, J. J. C., “A solution of the decision problem for the Lewis systems S.2 and S.4 with an application to topology,” The Journal of Symbolic Logic , vol. 6 (1941), pp. 117–34. JSTOR: · Zbl 0063.03863
[24] McKinsey, J. J. C.,and A. Tarski, “The algebra of topology,” Annals of Mathematics , vol. 45 (1944), pp. 141–91. JSTOR: · Zbl 0060.06206
[25] McKinsey, J. J. C., and A. Tarski, “On closed elements in closure algebras,” Annals of Mathematics , vol. 47 (1946), pp. 122–62. JSTOR: · Zbl 0060.06207
[26] McKinsey, J. J. C., and A. Tarski, “Some theorems about the sentential calculi of Lewis and Heyting,” The Journal of Symbolic Logic , vol. 13 (1948), pp. 1–15. JSTOR: · Zbl 0037.29409
[27] Montague, R., “Pragmatics and intensional logic,” Synthese , vol. 22 (1970), pp. 68–94. · Zbl 0228.02017
[28] Murungi, R. W., “Lewis’ postulate of existence disarmed,” Notre Dame Jornal of Formal Logic , vol. 21 (1980), pp. 181–91. · Zbl 0363.02020
[29] Nerode, A., and R. A. Shore, “Second order logic and first order theories of reducibility orderings,” pp. 181–90 in The Kleene Symposium , edited by J. Barwise, H. J. Keisler, and K. Kunen, North-Holland, Amsterdam, 1980. · Zbl 0465.03024
[30] Pitts, A. M., “On an interpretation of second order quantification in first order intuitionistic propositional logic,” The Journal of Symbolic Logic , vol. 57 (1992), pp. 33–52. JSTOR: · Zbl 0763.03009
[31] Polacik, T., “Operators defined by propositional quantification and their interpretation over Cantor space,” Reports on Mathematical Logic , vol. 27 (1993), pp. 67–79. · Zbl 0806.03008
[32] Polacik, T., “Second order propositional operators over Cantor space,” Studia Logica , vol. 53 (1994), pp. 93–105. · Zbl 0790.03005
[33] Rabin, M. O., “Decidability of second-order theories and automata on infinite trees,” Transactions of the American Mathematical Society , vol. 131 (1969), pp. 1–35. · Zbl 0221.02031
[34] Rabin, M. O., “Decidable Theories,” pp. 595–629 in The Handbook of Mathematical Logic , edited by J. Barwise, North-Holland, Amsterdam, 1977.
[35] Rasiowa, H., and R. Sikorski, The Mathematics of Metamathematics , Państwowe Wydawnictwo Naukowe, Warsaw, 1963. · Zbl 0122.24311
[36] Scedrov, A., “On some extensions of second-order intuitionistic propositional calculus,” Annals of Pure and Applied Logic , vol. 27 (1984), pp. 155–64. · Zbl 0569.03026
[37] Scott, D., “Advice on modal logic,” pp. 143–173 in Philosophical Problems in Logic: Some Recent Developments , edited by K. Lambert, Reidel, Dordrecht, 1970. · Zbl 0295.02013
[38] Segerberg, K., An Essay on Classical Modal Logic , Filosofiska Institutionem vid Uppsala Universitet, Uppsala, 1971. · Zbl 0311.02028
[39] Sobolev, S. K., “On the intuitionistic propositional calculus with quantifiers” (in Russian), Akademiya Nauk Soyuza S.S.R. Matematicheskie Zamietki , vol. 22 (1977), pp. 69–76.
[40] Shelah, S., “The monadic theory of order,” Annals of Mathematics , vol. 102 (1975), pp. 379–419. JSTOR: · Zbl 0345.02034
[41] Tsao-Chen, T., “Algebraic postulates and a geometric interpretation for the Lewis calculus of strict implication,” Bulletin of the American Mathematical Society , vol. 44 (1938), pp. 737–44. · Zbl 0019.38504
[42] Troelstra, A. S., “On a second-order propositional operator in intuitionistic logic,” Studia Logica , vol. 40 (1981), pp. 113–39. · Zbl 0473.03022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.