Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-22T20:31:10.453Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite and finitely separable intermediate propositional logics

Published online by Cambridge University Press:  12 March 2014

Fabio Bellissima
Fabio Bellissima*
Affiliation:
Dipartimento di Matematica, Università Degli Studi di Siena, 53100 Siena, Italy
Get access Rights & Permissions [Opens in a new window]

Extract

§0. Introduction and material background. The present paper is devoted to the study of intermediate propositional logics, and it is based on [Be, §§1 and 2].

§2 (§§0 and 1 are introductory) concerns the axiomatization of finite logics. In the literature several effective procedures to axiomatize finite logics are present (cf., for instance, [MK] and [Wr]), but, in each case, the number of propositional variables which are used is redundant. In this direction, Theorem 2.2 provides (a) a criterion to determine, given a finite logic L, the least n such that L is axiomatizable by formulas in n variables, and (b) an effective axiomatization by an n-formula. As a corollary we obtain a negative answer to Problem 7.10 of [Ho/On], showing that there is no connection between the slice to which L belongs and the number of propositional variables necessary to axiomatize L.

The principal results of the paper are in §3. In fact, a great deal of research has been done on the correspondence between conditions on the relation of Kripke-structures from one side, and axioms added to Int from the other. In this section we (a) introduce the concept of finitely separable class of Kripke-frames, and show, by means of several examples, that this concept is “wide”, in the sense that all the most studied classes of frames determined by semantical conditions are finitely separable; (b) show that each finitely separable class is axiomatizable, and that the axioms can be found by means of semantical considerations only; and (c) establish the finite model property for all the finitely separable logics.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 53 , Issue 2 , June 1988 , pp. 403 - 420
Copyright
Copyright © Association for Symbolic Logic 1988

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

[Be] Bellissima, F., Finitely generated free Heyting algebras, this Journal, vol. 51 (1986), pp. 152–165.Google Scholar
[Ga] Gabbay, D. M., Semantical investigations in Heyting's intuitionistic logic, Reidel, Dordrecht, 1981.CrossRefGoogle Scholar
[Ga/DJ] Gabbay, D. M. and de Jongh, D. H. J., A sequence of decidable finitely axiomatizable intermediate logics with the disjunction property, this Journal, vol. 39 (1974), pp. 67–78.Google Scholar
[Ha] Harrop, R., On the existence of finite models and decision procedures for prepositional calculi, Proceedings of the Cambridge Philosophical Society, vol. 54 (1958), pp. 1–13.CrossRefGoogle Scholar
[Ho] Hosoi, T., On intermediate logics. I, Journal of the Faculty of Science, University of Tokyo, Section I, vol. 14 (1967), pp. 293–312.Google Scholar
[Ho/]n] Hosoi, T. and Ono, H., Intermediate prepositional logics (a survey), Journal of Tsuda College, vol. 5 (1973), pp. 67–82.Google Scholar
[Ja] Jankov, V. A., The construction of a sequence of strongly independent superintuitionistic propositional calculi, Doklady Akademii Nauk SSSR, vol. 181 (1968), pp. 33–34; English translation, Soviet Mathematics Doklady , vol. 9 (1968), pp. 806–807.Google Scholar
[Ma] Maksimova, L. L., Pretabular superintuitionistic logics, Algebra i Logika, vol. 11 (1972), pp. 558–570; English translation, Algebra and Logic , vol. 11 (1972), pp. 308-314.Google Scholar
[MK] McKay, C. G., On finite logics, Indagationes Mathematicae, vol. 29 (1967), pp. 95–96.Google Scholar
[On] Ono, H., Some results on the intermediate logics, Publications of the Research Institute for the Mathematical Sciences, vol. 8 (1972/1973), pp. 619–649.CrossRefGoogle Scholar
[Se] Segerberg, K., Prepositional logics related to Heyting's and Johansson's, Theoria, vol. 34 (1968), pp. 26–61.CrossRefGoogle Scholar
[Sm] Smoryński, C., Investigations on intuitionistic formal systems by means of Kripke models, Ph.D. thesis, University of Illinois, Urbana, Illinois, 1973.Google Scholar
[Wr] Wronski, A., An algorithm for finding finite axiomatizations of finite intermediate logics, Polish Academy of Sciences, Institute of Philosophy and Sociology, Bulletin of the Section of Logic, vol. 2 (1972), pp. 38–44.Google Scholar