Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-19T03:08:15.859Z Has data issue: false hasContentIssue false
  • English
  • Français

On an interpretation of second order quantification in first order intuitionistic propositional logic

Published online by Cambridge University Press:  12 March 2014

Andrew M. Pitts
Andrew M. Pitts*
Affiliation:
Computer Laboratory, Cambridge University, Cambridge CB2 3QG, England, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove the following surprising property of Heyting's intuitionistic propositional calculus, IpC. Consider the collection of formulas, ϕ, built up from propositional variables (p, q, r, …) and falsity (⊥) using conjunction (∧), disjunction (∨) and implication (→). Write ⊢ϕ to indicate that such a formula is intuitionistically valid. We show that for each variable p and formula ϕ there exists a formula Apϕ (effectively computable from ϕ), containing only variables not equal to p which occur in ϕ, and such that for all formulas ψ not involving p, ⊢ψ → Apϕ if and only if ⊢ψ → ϕ. Consequently quantification over propositional variables can be modelled in IpC, and there is an interpretation of the second order propositional calculus, IpC2, in IpC which restricts to the identity on first order propositions.

An immediate corollary is the strengthening of the usual interpolation theorem for IpC to the statement that there are least and greatest interpolant formulas for any given pair of formulas. The result also has a number of interesting consequences for the algebraic counterpart of IpC, the theory of Heyting algebras. In particular we show that a model of IpC2 can be constructed whose algebra of truth-values is equal to any given Heyting algebra.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 1 , March 1992 , pp. 33 - 52
Copyright
Copyright © Association for Symbolic Logic 1992

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

[1]Balbes, R. and Dwinger, P., Distributive lattices, University of Missouri Press, Columbia, Missouri, 1974.Google Scholar
[2]Dershowitz, N. and Manna, Z., Proving termination with multiset orderings, Communications of the Association for Computing Machinery, vol. 22 (1979), pp. 465–476.CrossRefGoogle Scholar
[3]Dragalin, A. G., Mathematical intuitionism, American Mathematical Society, Providence, Rhode Island, 1988.Google Scholar
[4]Dyckhoff, R., Contraction-free sequent calculi for intuitionistic logic, preprint, St. Andrews University, 1990.Google Scholar
[5]Gabbay, D. M., Semantical investigations in Heyting's intuitionistic logic, Synthese Library, vol. 148, Reidel, Dordrecht, 1981.CrossRefGoogle Scholar
[6]Hudelmaier, J., Bounds for cut elimination in intuitionistic propositional logic, Ph.D. Thesis, University of Tübingen, Tübingen, 1989.Google Scholar
[7]Kock, A. and Reyes, G. E., Doctrines in categorical logic, Handbook of Mathematical Logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, Chapter A.8, pp. 283–313.CrossRefGoogle Scholar
[8]Lincoln, P., Scedrov, A. and Shankar, N., Linearizing intuitionistic implication, Proceedings of the sixth annual symposium on logic in computer science, IEEE Computer Society Press, Washington, D.C., 1991 (to appear).Google Scholar
[9]Pitts, A. M., Amalgamation and interpolation in the category of Heyting algebras, Journal of Pure and Applied Algebra, vol. 29 (1983), pp. 155–165.CrossRefGoogle Scholar
[10]Pitts, A. M., Polymorphism is set theoretic, constructively, Category theory and computer science, proceedings, Edinburgh, 1987 (Pitt, D.et al., editors), Lecture Notes in Computer Science, vol. 283, Springer-Verlag, Berlin, 1987, pp. 12–39.Google Scholar
[11]Prawitz, D., Natural deduction, Almqvist & Wiksell, Stockholm, 1965.Google Scholar
[12]Seely, R. A. G., Categorical semantics for higher order polymorphic lambda calculus, this Journal, vol. 52 (1987) pp. 969–989.Google Scholar
[13]Vorob'ev, N. N., A new algorithm for derivability in the constructive propositional calculus, American Mathematical Society Translations, ser. 2, vol. 94 (1970), pp. 37–71.Google Scholar
[14]de Lavalette, G. R. Renardel, Interpolation in fragments of intuitionistic propositional logic, this Journal, vol. 54 (1989), pp. 1419–1430.Google Scholar