Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-22T06:42:00.094Z Has data issue: false hasContentIssue false
  • English
  • Français

The undecidability of entailment and relevant implication

Published online by Cambridge University Press:  12 March 2014

Alasdair Urquhart
Alasdair Urquhart*
Affiliation:
University of Toronto, Toronto, Ontario M5S 1A1, Canada
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper we show that the propositional logics E of entailment, R of relevant implication and T of ticket entailment are undecidable. The decision problem is also shown to be unsolvable in an extensive class of related logics. The main tool used in establishing these results is an adaptation of the von Neumann coordinatization theorem for modular lattices.

Interest in the decision problem for these systems dates from the late 1950s. The earliest result was obtained by Anderson and Belnap who proved that the first degree fragment of all these logics is decidable. Kripke [11] proved that the pure implicational fragments R→ and E→ of R and E are decidable. His methods were extended by Belnap and Wallace to the implication-negation fragments of these systems [3]; Kripke's methods also extend easily to include the implication-conjunction fragments of R and E. Meyer in his thesis [14] extended the result for R to include a primitive necessity operator. He also proved decidable the system R-mingle, an extension of R, and ortho-R (OR), the logic obtained from R by omitting the distribution axiom. Various weak relevant logics are also known to be decidable by model-theoretic proofs of the finite model property (see Fine [5]). Finally, S. Giambrone [7] has solved the decision problem for various logics obtained by the omission of the contraction axiom (A → ⦁ A → B) → ⦁ A → B, including R+ − W (R+ minus contraction). It is worth noting that even where positive results were obtained, the decision methods were usually of a complexity considerably greater than in the case of other nonclassical logics such as intuitionistic logic or modal logic, a fact which already indicates the difficulty of the decision problem.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 49 , Issue 4 , December 1984 , pp. 1059 - 1073
Copyright
Copyright © Association for Symbolic Logic 1984

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]Anderson, A. R., Some open problems concerning the system E of entailment, Acta Philosophica Fennica, fasc. 16 (1963), pp. 7–18.Google Scholar
[2]Anderson, A. R. and Belnap, N. D. Jr., Entailment. Vol. 1, Princeton University Press, Princeton, New Jersey, 1975.Google Scholar
[3]Belnap, N. D. Jr., and Wallace, J. R., A decision procedure for the system Eī of entailment with negation, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 11 (1965), pp. 277–289.CrossRefGoogle Scholar
[4]Davis, M., Computability and unsolvability, McGraw-Hill, New York, 1958.Google Scholar
[5]Fine, K., Models for entailment, Journal of Philosophical Logic, vol. 3 (1973), pp. 347–372.Google Scholar
[6]Freese, R., Free modular lattices, Transactions of the American Mathematical Society, vol. 261 (1980), pp. 81–91.CrossRefGoogle Scholar
[7]Giambrone, S., Gentzen systems and decision procedures for relevant logics, Ph.D. thesis, Australian National University, Canberra, 1983.Google Scholar
[8]Grätzer, G., General lattice theory, Academic Press, New York, 1978.CrossRefGoogle Scholar
[9]Gurevič, J. S., The problem of equality of words for certain classes of semigroups, Algebra i Logika Seminar, vol. 5 (1966), no. 5, pp. 25–35. (Russian)Google Scholar
[10]Hutchinson, G., Recursively unsolvable word problems of modular lattices and diagram-chasing, Journal of Algebra, vol. 26 (1973), 385–399.CrossRefGoogle Scholar
[11]Kripke, S. A., The problem of entailment (abstract), this Journal, vol. 24 (1959), p. 324.Google Scholar
[12]Linial, S. and Post, E. L., Recursive unsolvability of the deducibility, Tarski's completeness and independence of axioms problems of propositional calculus (abstract), Bulletin of the American Mathematical Society, vol. 55 (1949), p. 50.Google Scholar
[13]Lipshitz, L., The undecidability of the word problems for projective geometries and modular lattices, Transactions of the American Mathematical Society, vol. 193 (1974), pp. 171–180.CrossRefGoogle Scholar
[14]Meyer, R. K., Topics in modal and many-valued logic, Doctoral Dissertation, University of Pittsburgh, Pittsburgh, Pennsylvania, 1966.Google Scholar
[15]Meyer, R. K., Career induction ends here (and here = 2), Journal of Philosophical Logic, vol. 8 (1979), pp. 361–371.CrossRefGoogle Scholar
[16]Meyer, R. K. and Routley, R., Algebraic analysis of entailment. I, Logique et Analyse, vol. 15 (1972), pp. 407–428.Google Scholar
[17]Meyer, R. K. and Routley, R., An undecidable relevant logic, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 19 (1973), pp. 389–397.CrossRefGoogle Scholar
[18]von Neumann, J., Continuous geometry (Halperin, I., editor), Princeton University Press, Princeton, New Jersey, 1960.Google Scholar
[19]Routley, R. and Meyer, R. K., The semantics of entailment. III, Journal of Philosophical Logic, vol. 1 (1972), pp. 192–208.CrossRefGoogle Scholar
[20]Routley, R. and Meyer, R. K., The semantics of entailment. I, Truth, Syntax, Modality (Leblanc, H., editor), North-Holland, Amsterdam, 1973, pp. 199–243.CrossRefGoogle Scholar
[21]Urquhart, A., Semantics for relevant logics, this Journal, vol. 37 (1972), pp. 159–169.Google Scholar
[22]Veblen, O. and Young, J. W., Projective geometry. Vol. 1, Ginn, New York, 1910.Google Scholar