Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T06:06:17.920Z Has data issue: false hasContentIssue false
  • English
  • Français

Sufficient conditions for the undecidability of intuitionistic theories with applications1

Published online by Cambridge University Press:  12 March 2014

Dov M. Gabbay
Dov M. Gabbay*
Affiliation:
Stanford University, Stanford, [California] 94305
Get access Rights & Permissions [Opens in a new window]

Extract

Let Δ be a set of axioms of a theory Tc(Δ) of classical predicate calculus (CPC); Δ may also be considered as a set of axioms of a theory TH(Δ) of Heyting's predicate calculus (HPC). Our aim is to investigate the decision problem of TH(Δ) in HPC for various known theories Δ of CPC.

Theorem I(a) of §1 states that if Δ is a finitely axiomatizable and undecidable theory of CPC then TH(Δ) is undecidable in HPC. Furthermore, the relations between theorems of HPC are more complicated and so two CPC-equivalent axiomatizations of the same theory may give rise to two different HPC theories, in fact, one decidable and the other not.

Semantically, the Kripke models (for which HPC is complete) are partially ordered families of classical models. Thus a formula expresses a property of a family of classical models (i.e. of a Kripke model). A theory Θ expresses a set of such properties. It may happen that a class of Kripke models defined by a set of formulas Θ is also definable in CPC (in a possibly richer language) by a CPC-theory Θ′! This establishes a connection between the decision problem of Θ in HPC and that of Θ′ in CPC. In particular if Θ′ is undecidable, so is Θ. Theorems II and III of §1 give sufficient conditions on Θ to be such that the corresponding Θ′ is undecidable. Θ′ is shown undecidable by interpreting the CPC theory of a reflexive and symmetric relation in Θ′.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 37 , Issue 2 , June 1972 , pp. 375 - 384
Copyright
Copyright © Association for Symbolic Logic 1972

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.)

Footnotes

1

This research has been supported in part by National Science Foundation grant GJ-443X. I am indebted to Professor Kreisel for very helpful criticism. All possible shortcomings are entirely my responsibility.

References

REFERENCES

[1]Maslov, S. Y., Minc, G. B. and Orevkov, V. P., Unsolvability of the constructive predicate calculus of certain classes of formulas containing only monadic predicate variables, Soviet Mathematics Doklady, vol. 163 (1965), pp. 918–920.Google Scholar
[2]Slomson, A. B., An undecidable two sorted predicate calculus, this Journal, vol. 34 (1969), pp. 21–23.Google Scholar
[3]Kripke, S. A., Semantic analysis for intuitionistic logic. II (mimeographed).Google Scholar
[4]Kripke, S. A., The undecidability of monadic modal quantification theory, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 8 (1962), pp. 113–116.CrossRefGoogle Scholar
[5]Orevkov, V. P., The undecidability of a class of formulas containing just one single place predicate variable in modal calculus, Studies in constructive mathematics and mathematical logic, New York, 1969, pp. 67–70.Google Scholar
[6]Smorynski, C., Some recent results on elementary intuitionistic theories, Stanford University, California (mimeographed).Google Scholar
[7]Gabbay, D. M., Decidability of some intuitionistic predicate theories this Journal (to appear).Google Scholar
[8]Kripke, S. A., Semantic analysis for intuitionistic logic. I, Formal systems and recursive functions, North-Holland, Amsterdam 1965.Google Scholar
[9]Rogers, H., Certain logical reduction and decision problems, Annals of Mathematics, vol. 64 (1956), pp. 264–284.CrossRefGoogle Scholar
[10]Gabbay, D. M., Applications of trees to intermediate logics, this Journal, vol. 37 (1972) pp. 135–138.Google Scholar
[11]Lifshits, V. A., Problem of decidability for some constructive theories of equality, Studies of constructive mathematics and mathematical logic, New York, 1969.Google Scholar
[12]Gabbay, D. M., The undecidability of intuitionistic theories of algebraic and real closed fields, Stanford University, California (mimeographed).Google Scholar