Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-16T13:41:03.398Z Has data issue: false hasContentIssue false
  • English
  • Français

The superintuitionistic predicate logic of finite Kripke frames is not recursively axiomatizable

Published online by Cambridge University Press:  12 March 2014

Dmitrij Skvortsov
Dmitrij Skvortsov*
Affiliation:
All-Russian Institute of Scientific and Technical Information, Molodogvardejskaja 22, Korp. 3, KV. 29, 121351, Moscow, Russia, E-mail: skvortsov@viniti.ru
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that an intermediate predicate logic characterized by a class of finite partially ordered sets is recursively axiomatizable iff it is “finite”, i.e., iff it is characterized by a single finite partially ordered set. Therefore, the predicate logic LFin of the class of all predicate Kripke frames with finitely many possible worlds is not recursively axiomatizable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 2 , June 2005 , pp. 451 - 459
Copyright
Copyright © Association for Symbolic Logic 2005

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] Gabbay, D. M., Decidability of some inluitionistic predicate theories, this Journal, vol. 30 (1972), pp. 579–587.Google Scholar
[2] Ono, H., Some problems in intermediate predicate logics, Reports on Mathematical Logic, vol. 21 (1987), pp. 55–67.Google Scholar
[3] Shimura, T., Kripke completeness of some intermediate predicate logics with the axiom of constant domain and a variant of canonical formulas, Studia Logica, vol. 52 (1993), no. 1, pp. 23–40.Google Scholar
[4] Skvortsov, D., On axiomatizability of some intermediate predicate logics {summary), Reports on Mathematical Logic, vol. 22 (1988), pp. 115–116.Google Scholar
[5] Skvortsov, D., On the predicate logic of finite Kripke frames, Studia Logica, vol. 54 (1995), pp. 79–88.Google Scholar
[6] Skvortsov, D., Not every “tabular” predicate logic is finitely axiomatizable, Studia Logica, vol. 59 (1997), pp. 387–396.Google Scholar
[7] Skvortsov, D., On non-axiomatizability of some intermediate predicate logics, in preparation.Google Scholar
[8] Smoryński, C. A., Applications of Kripke models, Metamathematical investigations of intuitionistic arithmetic and analysis (Troelstra, A. S., editor). Lecture Notes in Mathematics, vol. 344, Springer-Verlag, Berlin, Heidelberg, New York, 1973, pp. 324–391.Google Scholar
[9] Trachtenbrot, B. A., Impossibility of an algorithm for the decision problem infinite classes, Doklady Akademii Nauk SSSR, vol. 70 (1950), no. 4, pp. 569–572, in Russian; English translation: American Mathematical Society Translations, Series 2 , vol. 23 (1963), pp. 1–5.Google Scholar