Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-24T23:48:33.056Z Has data issue: false hasContentIssue false
  • English
  • Français

On the complexity of propositional quantification in intuitionistic logic

Published online by Cambridge University Press:  12 March 2014

Philip Kremer
Philip Kremer*
Affiliation:
Department of Philosophy, Yale University, P.O. Box 208306, New Haven, CT 06520-8306, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We define a propositionally quantified intuitionistic logic Hπ+ by a natural extension of Kripke's semantics for propositional intuitionistic logic. We then show that Hπ+ is recursively isomorphic to full second order classical logic. Hπ+ is the intuitionistic analogue of the modal systems S5π+, S4π+, S4.2π+, K4π+, Tπ+, Kπ+ and Bπ+, studied by Fine.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 62 , Issue 2 , June 1997 , pp. 529 - 544
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1970] Fine, K., Propositional quantifiers in modal logic, Theoria, pp. 336–346.Google Scholar
[1974] Gabbay, D., On 2nd order intuitionistic propositional calculus with full comprehension, Archiv für Mathematische Logik und Grundlagenforsch, pp. 177–186.Google Scholar
[1981] Gabbay, D., Semantical investigations in Heyting's intuitionistic logic, D. Reidel, Dordrecht.CrossRefGoogle Scholar
[1950] Henkin, L., Completeness in the theory of types, this Journal, pp. 81–91.Google Scholar
[1970] Kaplan, D., S5 with quantifiable propositional variables, this Journal, p. 355.Google Scholar
[1981] Kreisel, G., Monadic operators defined by means of propositional quantification in intuitionistic logic, Reports on Mathematical Logic, pp. 9–15.Google Scholar
[1993] Kremer, P., Quantifying over propositions in relevance logic: Non-axiomatisability of ∀p and ∃p, this Journal, pp. 334–349.Google Scholar
[1963] Kripke, S., Semantical analysis of intuitionistic logic I, Formal systems and recursive functions: Proceedings of the eighth logic colloquium (Crossley, J. N. and Dummett, M. A. E., editors), North-Holland, Amsterdam, pp. 92–130.Google Scholar
[1976] Löb, M. H., Embedding first order predicate logic in fragments of intuitionistic logic, this Journal, pp. 705–718.Google Scholar
[1980] Nerode, A. and Shore, R., Second order logic and first order theories of reducibility orderings, The Kleene symposium (Barwise, J., Keisler, H. J., and Kunen, K., editors), North-Holland, Amsterdam, pp. 181–200.CrossRefGoogle Scholar
[1992] Pitts, A. M., On an interpretation of second order quantification in first order intuitionistic propositional logic, this Journal, pp. 33–52.Google Scholar
[1965] Rabin, M., A simple method for undecidability proofs and some applications, Logic, methodology and the philosophy of science, proceeding of the 1964 international congress (Bar-Hillel, Y., editor), North-Holland, Amsterdam, pp. 58–68.Google Scholar
[1984] Scedrov, A., On some extensions of second-order intuitionistic propositional calculus, Annals of Pure and Applied Logic, pp. 155–164.Google Scholar
[1977] Sobolev, S. K., On the intuitionistic propositional calculus with quantifiers (in Russian), Akademiya Nauk Soyuza SSR. Matematicheskie Zamietki, pp. 69–76.Google Scholar